無線移動網(wǎng)絡(luò)中網(wǎng)絡(luò)連通算法設(shè)計(jì)與分析.pdf

1、在任意有線和無線網(wǎng)絡(luò)中，連通性是保障網(wǎng)絡(luò)通信最基本的要求.與有線網(wǎng)絡(luò)相比，由于無線用戶移動、節(jié)點(diǎn)電量耗盡、網(wǎng)絡(luò)受到惡意攻擊等因素，使得網(wǎng)絡(luò)連通具有動態(tài)性，因此，與有線網(wǎng)絡(luò)相比研究無線移動網(wǎng)絡(luò)中的連通性具有更大挑戰(zhàn).作為無線移動網(wǎng)絡(luò)獨(dú)有的特點(diǎn)之一，移動性在給無線用戶帶來諸多便利的同時，也給增強(qiáng)網(wǎng)絡(luò)連通帶來了極大的機(jī)遇.比如在不連通的車輛網(wǎng)絡(luò)中，過往的車輛可作為信息傳遞的載體；在連通的蜂窩網(wǎng)絡(luò)中，可移動的通信車可用于改善局部網(wǎng)絡(luò)的無線通信質(zhì)

2、量.本文主要研究了如何利用無線用戶的移動性增強(qiáng)現(xiàn)有網(wǎng)絡(luò)的連通性，研究了無線定位問題、網(wǎng)絡(luò)拓?fù)湫迯?fù)問題、網(wǎng)絡(luò)抗毀性問題、和網(wǎng)絡(luò)k-連通分析等，即論文從研究前提、被動修復(fù)、主動預(yù)防、和擴(kuò)展分析等方面，系統(tǒng)的對無線移動網(wǎng)絡(luò)中的網(wǎng)絡(luò)連通性進(jìn)行了研究.論文的主要研究成果和內(nèi)容如下：
　　 1)定位
　　 準(zhǔn)確的實(shí)現(xiàn)節(jié)點(diǎn)定位是研究網(wǎng)絡(luò)連通的先提條件之一.提出了一種基于網(wǎng)格掃描的無線傳感器網(wǎng)絡(luò)定位算法，該算法在每一個未知節(jié)點(diǎn)處(已知位

3、置的節(jié)點(diǎn)稱為錨節(jié)點(diǎn))分布式運(yùn)行.利用1跳和2跳鄰錨節(jié)點(diǎn)的位置信息，所提出的算法通過網(wǎng)格掃描的方式確定自己位于每一個網(wǎng)格的概率.最后，將所有概率不為0的網(wǎng)格的平均位置作為自己的估計(jì)位置.仿真結(jié)果表明，與現(xiàn)有的DLE算法相比，所提出的算法具有更高的定位精度。
　　 2)網(wǎng)絡(luò)分區(qū)修復(fù)
　　 針對不連通的網(wǎng)絡(luò)分區(qū)，為修復(fù)網(wǎng)絡(luò)連通提出了兩種基于Steiner樹和最小連通支配集(MCDS)的移動控制算法，分別稱為SMC和Steine

4、rMcds。
　　 ·SMC首先調(diào)用3近似最少Steiner點(diǎn)算法建立一棵包含所有網(wǎng)絡(luò)節(jié)點(diǎn)和Steiner點(diǎn)的Steiner樹，然后將引入的Steiner點(diǎn)作為節(jié)點(diǎn)移動的目的點(diǎn)，選擇并調(diào)度一些節(jié)點(diǎn)移動到引入的Steiner點(diǎn)上，SMC算法迭代執(zhí)行直到網(wǎng)絡(luò)拓?fù)浠謴?fù)連通。
　　 ·與SMC算法不同，SteienrMcds算法則首先計(jì)算當(dāng)前各個網(wǎng)絡(luò)分區(qū)的MCDS，然后建立一棵連接所有MCDS節(jié)點(diǎn)集合的Steiner樹.最后，將

5、所有不在MCDS集合中的節(jié)點(diǎn)與引入的Steiner點(diǎn)進(jìn)行匹配，并將被匹配的節(jié)點(diǎn)移動到相應(yīng)的Steiner點(diǎn)處.SteinerMcds算法迭代執(zhí)行直到網(wǎng)絡(luò)連通。
　　 仿真結(jié)果表明，所提出的SMC和SteinerMcds算法，在算法迭代次數(shù)、節(jié)點(diǎn)總移動距離、節(jié)點(diǎn)平均和最大移動距離等方面，均優(yōu)于基于分區(qū)最小生成樹的PMST-UV算法；此外，兩種算法中，SMC算法具有較高的算法成功率和較少的移動節(jié)點(diǎn)總個數(shù)；而SteinerMcds算法

6、則具有較少的迭代次數(shù)和較小的節(jié)點(diǎn)最大移動距離。
　　 3)網(wǎng)絡(luò)抗毀性研究
　　 為增強(qiáng)1-連通網(wǎng)絡(luò)的抗毀性，提出了一種基于可刪除節(jié)點(diǎn)的移動控制算法，通過調(diào)度節(jié)點(diǎn)移動使得1-連通的網(wǎng)絡(luò)變?yōu)?-連通.該研究的主要內(nèi)容和成果有：
　　 ·在圖論中，第一次提出可刪除節(jié)點(diǎn)的概念.可刪除節(jié)點(diǎn)有下述優(yōu)點(diǎn)：當(dāng)可刪除節(jié)點(diǎn)u被從連通圖G中移除之后，圖G既不會分割(不連通)，也不會有新的割點(diǎn)出現(xiàn).進(jìn)一步的，提出了一種分布式的可刪除節(jié)點(diǎn)

7、判定算法。
　　 ·提出獨(dú)立可刪除節(jié)點(diǎn)集的概念，當(dāng)所有獨(dú)立可刪除節(jié)點(diǎn)集中的節(jié)點(diǎn)同時移動時，圖G既不會分割(不連通)，也不會有新的割點(diǎn)出現(xiàn)；并找到了一種判定獨(dú)立可刪除節(jié)點(diǎn)集的充分條件。
　　 ·基于獨(dú)立可刪除節(jié)點(diǎn)集及其判定條件，提出了一種分布式的移動控制算法，調(diào)度可刪除節(jié)點(diǎn)向割點(diǎn)移動，從而使得最終的網(wǎng)絡(luò)拓?fù)?-連通，并同時最小化移動節(jié)點(diǎn)總個數(shù)和節(jié)點(diǎn)移動總距離。
　　 ·為最小化每個被移動的可刪除節(jié)點(diǎn)的移動距離，將可

8、刪除節(jié)點(diǎn)移動到指定割點(diǎn)的問題，建模為最小化可刪除節(jié)點(diǎn)移動開銷的凸優(yōu)化問題.通過求解該凸問題，可以得到可刪除節(jié)點(diǎn)最終的移動位置。
　　 ·仿真結(jié)果表明，1-連通網(wǎng)絡(luò)中平均至少有40％的節(jié)點(diǎn)為可刪除節(jié)點(diǎn)，且所提出的可刪除節(jié)點(diǎn)判定算法能夠判定出大部分可刪除節(jié)點(diǎn)(87％～100％).所提出的上述移動控制算法有下述優(yōu)點(diǎn)：高成功率(通過調(diào)度節(jié)點(diǎn)移動可達(dá)到最終的網(wǎng)絡(luò)2-連通)、被移動的節(jié)點(diǎn)個數(shù)少、總的節(jié)點(diǎn)移動距離短等.此外，仿真結(jié)果還表明，在

9、同時含有移動節(jié)點(diǎn)和不可移動節(jié)點(diǎn)的混合網(wǎng)絡(luò)中，所提出的算法同樣有效。
　　 4)網(wǎng)絡(luò)k-連通分析
　　 從網(wǎng)絡(luò)連通角度，研究了車輛網(wǎng)絡(luò)的特有性質(zhì)：車輛的離開將導(dǎo)致車輛網(wǎng)絡(luò)的不連通.由于在k-連通網(wǎng)絡(luò)中任意(k-1)個節(jié)點(diǎn)失效均不會導(dǎo)致網(wǎng)絡(luò)分割，因此本文將主要分析計(jì)算網(wǎng)絡(luò)k-連通的概率.論文提出了一種新的準(zhǔn)確計(jì)算網(wǎng)絡(luò)k-連通概率的方法；由所得的網(wǎng)絡(luò)k-連通概率，可計(jì)算出給定車輛網(wǎng)絡(luò)所能接受的最多離開車輛的期望值.主要研究結(jié)果

10、包括以下幾個方面：
　　 ·推導(dǎo)出一維車輛網(wǎng)絡(luò)k-連通的充分必要條件：當(dāng)且僅當(dāng)任意k個連續(xù)的車輛間距之和不大于車輛的無線傳輸半徑時，該車輛網(wǎng)絡(luò)達(dá)到k-連通。
　　 ·基于所得到的充分必要條件，推導(dǎo)出了網(wǎng)絡(luò)k-連通概率的表達(dá)式。
　　 ·為準(zhǔn)確計(jì)算所得的網(wǎng)絡(luò)k-連通概率的表達(dá)式，引入了排序統(tǒng)計(jì)學(xué)(orderstatistics)中的標(biāo)記算法(Marking Algorithm)，準(zhǔn)確計(jì)算出網(wǎng)絡(luò)k-連通概率，并舉例說