增強Ad hoc網絡連通性的單節點移動算法*

張穎 沈中 常義林

(西安電子科技大學綜合業務網理論及關鍵技術國家重點實驗室，陜西西安710071)

相對于常規通信網絡而言，Ad hoc網絡最大的特點就是可以在無基礎設施支持的情況下，于任意時刻、任意地點快速地構建一個移動通信網絡.一旦網絡中某個或某些節點發生故障，網絡中其它節點經過自組織仍然能夠保證網絡的正常工作.由于這樣的網絡具有一定的獨立性，因而在戰場通信、緊急救援、偏遠地區通信及其它一些特殊商業領域中具有極大的吸引力和應用價值.

Ad hoc網絡中，當某個節點因移動或故障而導致網絡分割時，信息只限在網絡局部傳遞而不能到達整個網絡，這樣的節點被稱為網絡分割點.如果網絡中存在分割節點，那么網絡的通信能力將受到極大的影響.因此，節點之間可靠的連通是保證網絡通信的基礎.為了增強網絡的連通性，通常構造至少具有2-連通的網絡拓撲，以保證在一個節點失效的情況下整個網絡的連通.以往構造2-連通網絡拓撲的研究主要集中在拓撲控制算法上，即通過動態調節各節點的傳輸功率來達到減少能量消耗的目的［1］.然而，在節點分布較為稀疏的區域，拓撲控制算法不能有效地降低節點的傳輸功率.因此，以提高網絡連通性、降低能量消耗等為目的的節點移動機制成為了研究熱點［2-11］.文獻［3］中提出了一種節點聚集算法的理論框架，該算法在同步模式或異步模式下移動節點時不會破壞該節點與其鄰節點之間的連通性.文獻［4］中根據網絡拓撲生成塊圖，即不包含分割節點的極大連通子圖，將網絡中包含節點數最少的塊圖內的節點整體向另一個塊圖中與該塊圖距離最近的節點移動.考慮到大量節點參與移動會消耗較多的能量，文獻［5-6］中提出的LMC算法要求分割節點的鄰節點中非同塊圖內且相距最近的兩個節點相向移動，使這兩個節點之間的距離減小到最大通信半徑.與塊移動算法不同的是，LMC算法中節點不需要收集全網絡信息，因而更適合于大規模的網絡.

上述算法均依賴于全球定位系統(GPS)定位.然而，GPS信號易受建筑物、地形的影響而存在無信號覆蓋的盲區.在戰場網絡中，當某些系統受到GPS費用、功耗等限制而無法使用GPS時，節點將無法獲取相關的位置信息.更為嚴格的是，一些資源有限的Ad hoc網絡通常要求在不增加節點的情況下提高網絡連通性，此時，如何移動節點是一項值得研究和解決的課題.BRN算法根據分割節點在8個不同方向上接收同一個鄰節點信號值的變化來確定其鄰節點的方向并移動分割節點的鄰節點中屬于不同塊圖且坐標夾角最小的兩個節點［7］，由于分割節點為了確定鄰節點方向參與移動而消耗能量，因此加快了網絡分割.據此，文中提出了一種基于接收信號強度的節點移動算法，該算法在不破壞網絡原有連接關系的條件下只移動一個節點到新位置以改善網絡的連通性.由于只是單個節點移動，因此節點的移動對網絡覆蓋的影響較小.

1 相關概念

如果無線Ad hoc網絡G中任意兩個節點nτ和nω之間通過無線鏈路可達，則稱G是連通的.若刪除連通網絡G中任一節點nν及其關聯的所有鏈路后所形成的網絡G'依然保持連通，那么網絡G至少是2-連通的，即2-連通的網絡中，任意兩個節點之間至少存在2條不相交的路徑.然而刪除節點nν及其關聯的鏈路后，G將被分割為多個2-連通分支，nν為網絡的分割節點.如果將每個2-連通分支中的節點集合稱為一個群，則群之間通過分割節點連接.如圖1(a)所示的網絡拓撲圖中，節點nc0為分割節點并將網絡分割成兩個群C1和C2，C1={n1，n2，n3，n6}，C2={n4，n5}.網絡中還會出現兩個分割節點相連而形成分割節點對的情況.如圖1(b)所示，節點nc1和nc2構成分割節點對，而群C1={n1，n2，n3}和C2={n4，n5}通過nc1和nc2連接.由于2-連通的網絡中不存在分割節點，因此可通過探測網絡中是否存在分割節點來判斷該網絡拓撲是否2-連通.目前，探測網絡分割節點的方法主要是基于圖論的構造深度優先遍歷(DFS)生成樹［8］.文中算法采用DFS生成樹的方法來探測網絡分割節點.

圖1 某一Ad hoc網絡的分割節點Fig.1 Cut nodes in an Ad hoc network

2 網絡模型

考慮m個同質節點分布在二維平面上構成的Ad hoc網絡.假設每個節點具有唯一ID號并用nτ(τ=1，2，…，m)表示.節點通過全向天線收、發信號，并通過相關的收、發設備指示信號強度.假設無線信道采用相同的傳播模型，即無線信號的功率按照節點之間距離d的σ(σ≥2)次方衰減.對于給定的發送功率Pt及反映收、發設備工作特性的常數μ，接收功率Pr可以表示為

不同傳輸模型的σ取值不同，如自由空間模型中σ=2，而雙線模型中σ=4.根據接收節點能否接收到信號及接收信號的強度作如下定義.

定義1當網絡中任意節點nτ以一定功率發射信號時，如果節點nω(ω=1，2，…，m;ω≠τ)能夠檢測到nτ的信號，則稱nτ是nω的呼叫節點.

定義2節點根據接收信號強度與接收門限PRT之間的關系，可以判斷其與相應發射節點之間的距離關系.當節點nω接收到發射節點nτ的信號，即Pr(nω，nτ)≥PRT時，nτ和nω之間的距離沒有超過節點的最大通信半徑Rmax，nτ是nω的1-跳鄰節點并且nτ和nω之間可直接通信;當Pr(nω，nτ)＜PRT時，nτ是nω的非1-跳呼叫節點.

定義3在節點nτ的1-跳鄰節點中，存在節點nν(ν=1，2，…，m－1)，nτ接收到nν的信號強度為Pr(nτ，nν).根據式(1)可知，節點之間的距離越遠，接收信號越弱.因此令nτ接收到的最小1-跳鄰節點信號強度為Pr，min(nτ)=minPr(nτ，nν).為了不破壞nτ與其1-跳鄰節點之間的鏈路，節點的移動需保證Pr，min(nτ)不小于PRT.因此，節點nτ可移動的最大距離與其最大自由度ρ(nτ)相關.ρ(nτ)定義為

從式(2)可以看出，ρ(nτ)≥0.ρ(nτ)越大則nτ可移動的距離越大.當Pr，min(nτ)=PRT，ρ(nτ)=0時，nτ可移動的距離為0.

定義4因為節點nτ與非1-跳呼叫節點之間的距離均大于Rmax，因此，為了建立nτ與非1-跳呼叫節點之間的直接通信，可通過移動nτ使nτ與這些節點之間的距離最大為Rmax.根據式(1)可知，當nτ接收到的呼叫信號越強時，nτ需向該呼叫節點移動的距離越小;相反，則需移動的距離越大.令nτ的最大呼叫連接信號強度為Ps，max(nτ)=maxPr(nτ，nω)，則nτ的最小趨向度φ(nτ)定義為從式(3)可知，0＜φ(nτ)＜1;φ(nτ)越小，nτ移動的距離越小，反之nτ移動的距離越大.

3 基于接收信號功率的節點移動算法

增加網絡連通性最簡單的方法就是減少分割節點數，該方法通過移動節點來增加與分割節點相連接的兩個群之間的鏈路.為了節約能量，移動節點的選擇應遵循以最少的能量消耗建立鏈路的原則.由于分割節點與其1-跳鄰節點相距最近，因此選擇與分割節點相連的任意群內分割節點的1-跳鄰節點，作為移動節點向著另一個群移動.然而在節點從一個群向另一個群的移動過程中，會出現因移動而破壞該節點與本群內其它節點之間鏈路的情況;同時希望節點移動盡量少的距離即可與另一個群內的節點建立鏈路.因此，節點移動時應滿足以下2個原則:(1)節點建立新鏈路的移動不應破壞網絡原有的連通性;(2)節點移動的能量消耗最小.

考慮到節點無法獲取位置信息，文中算法根據節點的接收信號強度在不同的兩個群內各選一個節點，然后只移動其中一個節點而將另一個作為目標連接節點保持位置不變.

3.1 移動節點及目標連接節點的確定

為簡明起見，以圖1(a)為例進行分析.將分割節點nc0在群Ca(a=1，2)內的第i個1-跳鄰節點表示為表示的第j個1-跳鄰節點(除分割節點外)表示群Cb內的第k個呼叫節點.如表示節點n2表示節點表示n2的第2個1-跳鄰節點表示在C2內n2的呼叫節點表示節點為n5的1-跳鄰節點表示C1內n5的呼叫節點n3.

相應地，ncm的目標連接節點nct為另一個群內ncm的最大呼叫信號節點，即

根據上述方法，可以確定圖1(a)所示網絡中n2為移動節點，n4為n2的目標連接節點.這兩個節點在圖2(a)中分別用實、虛線圈標出.同時，圖2(a)還標出了節點n1的最大通信范圍以及節點n2與n4之間的呼叫鏈路.

對于圖1(b)所示的分割節點對，可將兩個分割節點nc1和nc2合并為一個新的分割節點nc12.同時，原分割節點的1-跳鄰節點歸并為nc12的1-跳鄰節點，如圖2(b)所示.然后，按照與單分割節點相同的方法在nc12的1-跳鄰節點中確定移動節點n4和目標連接節點n2，圖2(b)中分別以實、虛線圈標出.

圖2 圖1所示網絡的可移動節點和目標連接節點Fig.2 Moving node and target node of network in Fig.1

3.2 移動的目標位置

與其它節點相比，分割節點是連通網絡中較為特殊的節點，同時連接兩個甚至多個群，因而這樣的節點消耗能量更快.為了避免分割節點過快地消耗能量，移動節點作為增強網絡連通性的重要節點在移動到新位置后，所形成從目標節點經移動節點到達分割節點的鏈路應具有最小代價.這一代價主要體現在節點之間用于通信的能耗.針對這類問題，文獻［9-11］中提出的中繼節點移動算法可以最小化源、宿節點之間數據流傳輸的能耗.考慮到實際的能耗包括信號傳輸的能耗和因其它因素產生的能耗，因此文中將接收信號強度的倒數作為鏈路的代價［12］.當移動節點位于平面上任意點x時，設接收到目標節點和分割節點的信號強度分別為Pnc(x)和Pnt(x)，則目標節點經移動節點到達分割節點這條鏈路的代價為因此，移動節點的目標位置x*是使得從目標節點通過移動節點到達分割節點所構成的鏈路上傳輸能耗最小的位置，即

3.3 節點的移動

由于無法獲取節點位置信息，只能通過節點移動并測量某些點上的鏈路代價值，然后根據這些值再逐步移動的方法來確定目標位置.假設分割節點和目標節點在二維平面上的坐標分別為(unc，vnc)和(unt，vnt)，且在移動節點移動的過程中保持不變.當移動節點在i時刻的位置為x i(ui，vi)時，它與分割節點和目標連接節點之間的距離為dnc(x i)和dnt(x i)，接收到這兩個節點的信號強度分別為Pnc(x i)和Pnt(x i)，且信號傳輸方向與u坐標的夾角分別為α和β，如圖3所示.

圖3 分割節點、目標連接節點和移動節點的位置Fig.3 Positions of cut node，target node and moving node

節點從x i出發沿著θi+1方向直線移動δi+1到達x i+1(ui+1，vi+1)，則

如果無線信道采用自由空間模型，那么根據式(1)、(6)和(8)，ξ(x i+1)可表示為

由圖3所示可知節點間的位置關系如下:

根據式(1)有

將式(10)－(15)代入式(9)，然后對式(9)求關于δi+1的導數，得

由式(17)得到的δi+1為在搜索δ(x)最小值的過程中，節點從x i沿著θi+1方向到達x i+1所需移動的距離.由于－1≤cosα，sinα，cosβ，sinβ≤1，于是有

式(18)表明，根據位于x i時節點的Pnc(x i)和Pnt(x i)可計算得到在θi+1方向上節點移動距離δi+1的上限Δi+1.當節點沿著θi+1方向從x i到達x i+1時，在下一個ξ(x)減小的方向θi+2上移動距離δi+2.如此重復，直到節點搜索到ξ(x)的最小值點.然而為避免因移動而破壞網絡原有的連通性，節點往往不能完全到達x*，文中給出算法停止的條件:

從而確保節點的移動不超出其1-跳鄰節點的通信范圍.算法具體步驟如下:

1)初始化參數i=0.移動節點位置記作x i，如果節點此時接收分割節點和目標節點的信號強度分別為Pnc(x i)和Pnt(x i)，則根據式(6)計算得到目標節點經移動節點到達分割節點鏈路的代價為ξ(x i).節點選取移動方向為θi+1.

2)節點從x i出發，沿θi+1方向直線移動單位距離δ0后到達若ξ(x i)，轉步驟4).如果，說明θi+1為鏈路代價減小的方向，于是令，轉步驟3).如果，節點將沿－θi+1方向移動到關于x i的對稱點，并令，轉步驟3).

3)以x i為起點，節點沿θi+1方向繼續移動，根據式(18)計算節點在θi+1方向上的移動上限Δi+1.選取移動步長δi+1=Δi+1/2，節點從點x i沿θi+1方向直線移動δi+1到達x i+1.若ρ(ncm(x i+1))≤0，則算法結束;否則節點判斷鏈路代價.若ξ(x i+1)≤ξ(x i)，則轉步驟4);否則節點轉向相反方向.根據在位置x i+1時節點的接收信號Pnc(x i+1)和Pnt(x i+1)，由式(18)計算出節點從x i+1沿－θi+1方向移動的上限，得到移動步長然后，節點沿－θi+1方向移動若，則算法結束;否則節點判斷鏈路代價是否減小.若，令轉步驟4).否則節點再次反方向并按照同樣的方法移動，直到確定該方向上鏈路代價最小的位置為止.

4)節點從位置x i+1選擇與θi+1垂直的方向θi+2，令x i=x i+1，θi+1=θi+2，轉步驟2).

該算法首先保證了不破壞原有網絡的連通性，并最大程度地移動節點至目標位置以增加移動節點與目標連接節點之間的通信鏈路.圖4給出了節點移動的軌跡.從圖4中可知，節點從x0搜索到x*，經過位置序列{x1，x2，…，x i，x i+1，…}.實際情況下，節點無法到達x*而是停留在該序列的某一位置點上.

圖4 節點的移動軌跡Fig.4 Movement path of node

圖5給出了圖1中節點移動后的網絡拓撲圖.從圖5可以看出，節點經過移動，構成了與目標連接節點之間的新鏈路且網絡中任意兩個節點之間至少存在兩條互不相交的鏈路，因而該網絡是2-連通的.由于網絡中已不存在分割節點，將圖1中分割節點的標識分別更換為圖5(a)中的n7和圖5(b)中的n6、n7.

圖5 節點移動后的網絡拓撲圖Fig.5 Network topology after nodemovement

4 仿真實驗

為驗證所提算法的有效性，采用Microsoft VC 6.0仿真平臺對隨機部署的無線Ad hoc網絡進行仿真.在800m×800m的平坦區域內，節點獨立且隨機分布.每個節點的最大通信半徑為150m.為了取得較為合理的結果，相同節點數的網絡在實驗中均隨機產生300個不同的場景，實驗結果取平均值;節點在移動過程中，其它節點保持位置不變.首先考察節點移動后網絡連通性能的改善和能量消耗情況，然后比較節點移動對網絡覆蓋面積的影響.

4.1 網絡連通性能的改善

圖6 兩種算法對網絡連通性能改善的比較Fig.6 Comparison of improvement of network connectivity by two algorithms

網絡連通性能的改善是指在節點數相同的300個不同的網絡場景中，能在不破壞網絡原有連通性基礎上通過移動節點來建立與目標節點之間的直接鏈路，從而構成具有2-連通性能的網絡拓撲結構的場景數.圖6給出了節點數從30～120變化且節點隨機分布時文中算法和BRN算法的網絡連通性能的改善情況.從圖6可知，對于文中算法，原為單分割節點的網絡連通性能的改善程度隨節點數的增加而增大:當網絡中節點數為30時，網絡連通性能的改善值為9.33%，即只通過一個節點的移動，約28個場景達到2-連通;當網絡節點數達到120時，網絡連通性能的改善值為92.50%.這是因為當節點分布密集時，節點之間的距離相對較小，因而通過節點移動建立目標鏈路的成功率較高.對于原為分割節點對的網絡，文中算法也取得了類似的結果:當網絡中分布30個節點時，網絡連通性能改善的均值為4.33%;當網絡中分布120個節點時，網絡連通性能改善的均值為61.67%.由于移動節點和目標節點之間的距離增大，因而需要移動更多的距離以建立目標鏈路.然而，為了確保網絡原有鏈路不發生改變，原為分割節點對的網絡連通性能的改善程度低于原為單分割節點的網絡.在BRN算法中，由于分割節點也要參與移動以確定鄰節點方位，因而影響了網絡的原有連接關系，故其對網絡連通性能的改善略低于文中算法.

4.2 節點移動的能耗

由于節點的移動需要消耗一定的能量，算法是否有效需要考慮節點移動過程中的能量消耗，具體體現為節點移動的距離.當網絡節點數從30增加到100時，相同節點數的300個不同場景的節點移動距離的平均值如圖7所示.在原為單分割節點的網絡中，當節點數為100時，節點移動的平均距離為32.8943m，而節點數為60時，節點移動的平均距離最大為41.2677m.在原為分割節點對的網絡中，當節點數為30時，節點移動的平均距離最小為28.3300m，節點數為70時節點移動的平均距離最大.可以看出，節點移動的距離隨著網絡中節點數的增加呈現出先增加后減小的趨勢.這是因為節點的移動首先需要保證網絡原有連通性不變，在節點分布較為稀疏的網絡中，節點的可移動范圍較小，因而節點的實際移動距離較小.隨著網絡中節點數的增加，節點之間的距離減小，移動節點的可移動范圍變大，因而需要消耗更多的能量進行優化位置搜索.

圖7 節點移動平均距離與網絡中節點數的關系Fig.7 Averagemoving distance of node versus number of nodes in network

4.3 節點移動對網絡覆蓋面積的影響

節點移動改變了節點在網絡中的分布，從而影響網絡的覆蓋面積.若節點移動前的網絡覆蓋面積為A0，它是將每個節點的覆蓋面積累加、重疊的部分不重復計算得到的.同理可計算節點移動后的網絡覆蓋面積A.通過比較A/A0的值，可得到節點移動前后網絡覆蓋面積的變化.圖8給出了文中算法和BRN算法在不同節點分布的網絡中節點移動對網絡覆蓋面積的影響.從圖8可知，當網絡中有30個節點時，兩種算法的A/A0均值分別為0.904和0.886;當網絡中的節點數增加到100時，兩種算法的A/A0均值均可達到0.997，可以說基本上保持了網絡覆蓋面積不變.這是因為節點趨向于目標節點的移動將產生與目標節點重疊的網絡覆蓋區域，從而減小了整個網絡的覆蓋面積，特別是在節點分布較為稀疏的網絡中.另外，文中算法只允許移動一個節點且不改變網絡原有的連通性，因此相對于BRN算法來說，覆蓋面積的改變更小.然而，不論是文中算法還是BRN算法，節點的移動對網絡覆蓋面積的影響都隨著網絡中節點數的增加而減小.

5 結語

在節點位置信息未知的情況下，文中提出了一種基于接收信號功率的節點移動算法，用于對網絡拓撲進行優化配置.根據接收信號強度，在分割節點的1-跳鄰節點中分別確定移動節點和目標連接節點，并根據接收信號強度逐步移動節點，在不破壞網絡原有連通性的同時建立這兩個節點之間的直接鏈路.實驗結果表明，該算法可以通過移動單個節點來改善網絡拓撲的連通性，同時最小化節點移動對網絡覆蓋面積的影響.當然，移動一個節點并不能保證所有網絡具有2-連通性.因此，今后將進一步探討如何移動節點以構造具有抗毀性的網絡拓撲.

［1］Li Ning，Hou J.FLSS:a fault-tolerant topology control algorithm forwireless networks［C］∥Proceedings of ACM/IEEE Annual International Conference on Mobile Computing and Networking.Cologne:ACM/IEEE，2005:275-286.

［2］公維賓，沈中，常義林.傳感器網絡中實現傳輸功率均衡的移動控制算法［J］.西安電子科技大學學報:自然科學版，2008，35(5):816-822.Gong Wei-bin，Shen Zhong，Chang Yi-lin.Movement control algorithms for realizing the balance of transmission power for sensor networks［J］.Journal of Xidian University，2008，35(5):816-822.

［3］Lin Jie.Distributed mobility control for fault-tolerantmobile networks［C］∥Proceedings of Systems Communications.New York:IEEE，2005:61-66.

［4］Basu P，Redi J.Movement control algorithms for realization of fault-tolerant Ad hoc robot networks［J］.IEEE Network，2004，18(4):36-44.

［5］Das S，Liu Hai，Kamath A，etal.Localizedmovement control for fault tolerance of mobile robot networks［C］∥Proceedings of InternationalWorkshop on Energy Optimization in Wireless Sensor Networks.Albacete:IEEE，2007:24-26.

［6］Das S，Liu Hai，Nayak A，et al.A localized algorithm for bi-connectivity of connected mobile robots［J］.Telecommunication System，2009，40(2/3):129-140.

［7］Butterfield J，Dantu K，Gerkey B，et al.Autonomous biconnected networks ofmobile robots［C］∥Proceedings of the 6th International Symposium on Modeling and Optimization in Mobile，Ad Hoc，and Wireless Networks and Workshops.Berlin:IEEE，2008:640-646.

［8］Kim H.Articulation points detection algorithm［EB/OL］.［2008-05-15］.http:∥www.ibluemojo.com/school/articul_algorithm.html.

［9］Goldenberg D，Lin Jie，Morse A，etal.Towardsmobility as a network control primitive［C］∥Proceedings of ACM International Symposium on Mobile Ad Hoc Networking and Computing.Tokyo:ACM，2004:163-174.

［10］Jiang Zhen，Wu Jie，Kline R.Mobility control with local views of neighborhood in mobile networks［C］∥Proceedings of International Workshop on Networking，Architecture，and Storages.Shenyang:IEEE，2006:9-14.

［11］Kashyap A，Shayman M.Relay placement and movement control for realization of fault-tolerant Ad hoc networks［C］∥Proceedings of the 41st Annual Conference on Information Sciences and Systems.Baltimore:IEEE，2007:783-788.

［12］Zhang Ying，Shen Zhong，Chang Yilin，et al.A signal awaremovement control algorithm for GPS-free Ad hoc networks［J］.Journal of Convergence Information Technology，2010，5(9):238-224.