增強Ad hoc網(wǎng)絡(luò)連通性的單節(jié)點移動算法*

張穎 沈中 常義林

(西安電子科技大學綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國家重點實驗室，陜西西安710071)

相對于常規(guī)通信網(wǎng)絡(luò)而言，Ad hoc網(wǎng)絡(luò)最大的特點就是可以在無基礎(chǔ)設(shè)施支持的情況下，于任意時刻、任意地點快速地構(gòu)建一個移動通信網(wǎng)絡(luò).一旦網(wǎng)絡(luò)中某個或某些節(jié)點發(fā)生故障，網(wǎng)絡(luò)中其它節(jié)點經(jīng)過自組織仍然能夠保證網(wǎng)絡(luò)的正常工作.由于這樣的網(wǎng)絡(luò)具有一定的獨立性，因而在戰(zhàn)場通信、緊急救援、偏遠地區(qū)通信及其它一些特殊商業(yè)領(lǐng)域中具有極大的吸引力和應(yīng)用價值.

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

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

1 相關(guān)概念

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

圖1 某一Ad hoc網(wǎng)絡(luò)的分割節(jié)點Fig.1 Cut nodes in an Ad hoc network

2 網(wǎng)絡(luò)模型

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

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

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

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

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

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

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

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

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

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

3.1 移動節(jié)點及目標連接節(jié)點的確定

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

相應(yīng)地，ncm的目標連接節(jié)點nct為另一個群內(nèi)ncm的最大呼叫信號節(jié)點，即

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

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

圖2 圖1所示網(wǎng)絡(luò)的可移動節(jié)點和目標連接節(jié)點Fig.2 Moving node and target node of network in Fig.1

3.2 移動的目標位置

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

3.3 節(jié)點的移動

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

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

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

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

由圖3所示可知節(jié)點間的位置關(guān)系如下:

根據(jù)式(1)有

將式(10)－(15)代入式(9)，然后對式(9)求關(guān)于δi+1的導(dǎo)數(shù)，得

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

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

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

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

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

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

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

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

圖4 節(jié)點的移動軌跡Fig.4 Movement path of node

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

圖5 節(jié)點移動后的網(wǎng)絡(luò)拓撲圖Fig.5 Network topology after nodemovement

4 仿真實驗

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

4.1 網(wǎng)絡(luò)連通性能的改善

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

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

4.2 節(jié)點移動的能耗

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

圖7 節(jié)點移動平均距離與網(wǎng)絡(luò)中節(jié)點數(shù)的關(guān)系Fig.7 Averagemoving distance of node versus number of nodes in network

4.3 節(jié)點移動對網(wǎng)絡(luò)覆蓋面積的影響

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

5 結(jié)語

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

［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］公維賓，沈中，常義林.傳感器網(wǎng)絡(luò)中實現(xiàn)傳輸功率均衡的移動控制算法［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.