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

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

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

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

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

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

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

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

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

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