張穎 沈中 常義林

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

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

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

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

1 相關(guān)概念

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

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

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

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

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

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

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

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

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

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

3 基于接收信號(hào)功率的節(jié)點(diǎn)移動(dòng)算法

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

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

3.1 移動(dòng)節(jié)點(diǎn)及目標(biāo)連接節(jié)點(diǎn)的確定

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

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

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

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

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

3.2 移動(dòng)的目標(biāo)位置

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

3.3 節(jié)點(diǎn)的移動(dòng)

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

圖3 分割節(jié)點(diǎn)、目標(biāo)連接節(jié)點(diǎn)和移動(dòng)節(jié)點(diǎn)的位置Fig.3 Positions of cut node，target node and moving node

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

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

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

根據(jù)式(1)有

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

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

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

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

1)初始化參數(shù)i=0.移動(dòng)節(jié)點(diǎn)位置記作x i，如果節(jié)點(diǎn)此時(shí)接收分割節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的信號(hào)強(qiáng)度分別為Pnc(x i)和Pnt(x i)，則根據(jù)式(6)計(jì)算得到目標(biāo)節(jié)點(diǎn)經(jīng)移動(dòng)節(jié)點(diǎn)到達(dá)分割節(jié)點(diǎn)鏈路的代價(jià)為ξ(x i).節(jié)點(diǎn)選取移動(dòng)方向?yàn)棣萯+1.

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

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

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

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

圖4 節(jié)點(diǎn)的移動(dòng)軌跡Fig.4 Movement path of node

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

圖5 節(jié)點(diǎn)移動(dòng)后的網(wǎng)絡(luò)拓?fù)鋱DFig.5 Network topology after nodemovement

4 仿真實(shí)驗(yàn)

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

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

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

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

4.2 節(jié)點(diǎn)移動(dòng)的能耗

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

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

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

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

5 結(jié)語

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

［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ò)中實(shí)現(xiàn)傳輸功率均衡的移動(dòng)控制算法［J］.西安電子科技大學(xué)學(xué)報(bào):自然科學(xué)版，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.