移動(dòng)無線傳感器網(wǎng)絡(luò)連通性自主恢復(fù)算法

馬桂真，于 平

(1.北京聯(lián)合大學(xué) 北京市信息服務(wù)工程重點(diǎn)實(shí)驗(yàn)室，北京100106;2.北京郵電大學(xué) 網(wǎng)絡(luò)與交換技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，北京100876)

0 引 言

無線傳感器網(wǎng)絡(luò)(WSNs)往往布置在無人值守的惡劣環(huán)境，節(jié)點(diǎn)容易發(fā)生故障，同時(shí)節(jié)點(diǎn)可能因電量耗盡而無法工作。網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)的故障會(huì)將無線傳感器網(wǎng)絡(luò)分割成多個(gè)不連通的分區(qū)，不同分區(qū)之間的節(jié)點(diǎn)無法協(xié)作完成任務(wù)，對網(wǎng)絡(luò)性能產(chǎn)生嚴(yán)重影響。特別在戰(zhàn)場和搜救應(yīng)用中，人工很難干預(yù)，網(wǎng)絡(luò)連通性的自主恢復(fù)非常重要。

移動(dòng)無線傳感器網(wǎng)絡(luò)連通性恢復(fù)問題研究成為近年來研究的熱點(diǎn)［1～8］，典型方法有PADRA［3］和DCR［7］。但是PDARA 方法中關(guān)鍵節(jié)點(diǎn)的確定需要確定網(wǎng)絡(luò)的連通支配集(CDS)，能源消耗過大，且在連通性恢復(fù)過程中，可能會(huì)出現(xiàn)搜索路徑過長的情況。DCR 方法出現(xiàn)過多不必要的“故障恢復(fù)”操作，造成無謂的能量消耗。

針對現(xiàn)存的問題，本文提出一種無線傳感器網(wǎng)絡(luò)連通性自主恢復(fù)策略，同時(shí)將算法進(jìn)行了擴(kuò)充，處理兩個(gè)相鄰節(jié)點(diǎn)同時(shí)故障的情況。

1 系統(tǒng)模型與假設(shè)

本文研究無線傳感器網(wǎng)絡(luò)的連通性自主恢復(fù)，問題可建模為求無向圖的連通性問題。無向圖G=(S，E)，其中，S={s1，s2，s3，…，sn}代表傳感器節(jié)點(diǎn)集，E={(si，sj)|dis(si，sj)＜R}，dis(si，sj)表示節(jié)點(diǎn)si，sj之間的距離，R 表示節(jié)點(diǎn)的最大通信范圍。網(wǎng)絡(luò)中節(jié)點(diǎn)可按需移動(dòng)，各節(jié)點(diǎn)之間通信范圍都為R。本文還有如下的定義:

定 義1 1跳鄰居:對于?si∈S，?sj∈S，若si和sj之間距離小于通信范圍R，則sj是si的一跳鄰居，記為N1(si)。

定義2 2 跳鄰居:?si，sj，Sk∈S，sj∈N1(si)，若sj和sk之間的距離小于R，且sk?N1(Si)，則sk是si的2 跳鄰居。

定義3 k 關(guān)鍵節(jié)點(diǎn):?si∈S，若去掉si其所有的k 跳鄰居組成的子圖是不連通的，則節(jié)點(diǎn)si是k 跳關(guān)鍵節(jié)點(diǎn)。

2 確定關(guān)鍵節(jié)點(diǎn)

獲取本地信息多少與關(guān)鍵節(jié)點(diǎn)的確定存在一定的關(guān)系［9］，本文規(guī)定“2 關(guān)鍵節(jié)點(diǎn)”為關(guān)鍵節(jié)點(diǎn)。關(guān)鍵節(jié)點(diǎn)確定算法描述如下:

1)若節(jié)點(diǎn)n 是葉子節(jié)點(diǎn)，則n 是非關(guān)鍵節(jié)點(diǎn)。

2)若節(jié)點(diǎn)n 不是葉子節(jié)點(diǎn)，則將n 的1 跳鄰居基于位置順時(shí)針排列{ns1，ns2，…，nsn}。

3)對于節(jié)點(diǎn)n 的任意兩個(gè)相鄰的1 跳鄰居nsi，ns(i+1)，若dis(nsi，ns(i+1))≤R，則2 節(jié)點(diǎn)可直接通信。若所有相鄰1 跳鄰居節(jié)點(diǎn)之間是可直接通信，則節(jié)點(diǎn)n 是非關(guān)鍵節(jié)點(diǎn)，如圖1 中節(jié)點(diǎn)G，F(xiàn) 和D。

4)若dis(nsi，ns(i+1))＞R，則n 的1 跳鄰居之間可能會(huì)形成不連通的分區(qū)D1，D2，…，Dn，Di={nsi，ns(i+1)，…，ns(i+k)}，則算法檢測任意兩個(gè)分區(qū)是否可以合并成一個(gè)分區(qū)。如圖1 中節(jié)點(diǎn)M 的1 跳鄰居形成兩個(gè)分區(qū){H，N}和{L，I}，但是兩分區(qū)中N 和L 可直接通信，所以，兩個(gè)分區(qū)可以合成一個(gè)分區(qū)，節(jié)點(diǎn)M 是非關(guān)鍵節(jié)點(diǎn)。

5)若步驟(4)執(zhí)行完后至少有兩個(gè)分區(qū)不能合并，則節(jié)點(diǎn)n 是1 跳關(guān)鍵節(jié)點(diǎn)。如圖1 中節(jié)點(diǎn)A，1 跳鄰居分布在{C，E}和{D，B}，且兩分區(qū)之間沒有節(jié)點(diǎn)可直達(dá)，則A 是1 跳關(guān)鍵節(jié)點(diǎn)。

6)若節(jié)點(diǎn)n 是1 跳關(guān)鍵節(jié)點(diǎn)，則檢測任意兩個(gè)分區(qū)中節(jié)點(diǎn)是否有相同的1 跳鄰居(n 的2 跳鄰居)，若存在，則這個(gè)二分區(qū)也合并為一個(gè)分區(qū)。若所有分區(qū)都合并為一個(gè)分區(qū)，則節(jié)點(diǎn)n 是非關(guān)鍵節(jié)點(diǎn)，否則，是關(guān)鍵節(jié)點(diǎn)。如圖1 中節(jié)點(diǎn)A 的鄰居形成的兩個(gè)分區(qū){E，C}和{D，B}中若任意兩個(gè)節(jié)點(diǎn)B 和C 有相同的1 跳鄰居L(L 是A 的2 跳鄰居)，則節(jié)點(diǎn)A 是非關(guān)鍵節(jié)點(diǎn)。若節(jié)點(diǎn)L 與C 不可直接通信，則節(jié)點(diǎn)A 是關(guān)鍵節(jié)點(diǎn)。

圖1 關(guān)鍵節(jié)點(diǎn)識別算法Fig 1 Algorithm for critical nodes recognition

3 單個(gè)關(guān)鍵節(jié)點(diǎn)故障

3.1 備用節(jié)點(diǎn)確定

提前選取備用節(jié)點(diǎn)可以減少故障響應(yīng)延遲，在時(shí)間要求嚴(yán)格的應(yīng)用中尤其重要。本算法檢測各級關(guān)鍵節(jié)點(diǎn)是否有非關(guān)鍵節(jié)點(diǎn)鄰居，減少連通性恢復(fù)過程中的長搜索路徑出現(xiàn)的幾率。單個(gè)節(jié)點(diǎn)故障時(shí)備用節(jié)點(diǎn)選取算法如下:

Algorithm 1 Backupselect(S)

∥Backup(S)節(jié)點(diǎn)S 備用節(jié)點(diǎn)。

1)if critical(S)=true then

3) i=close(S，ileaf))∥最近的葉子節(jié)點(diǎn)

5) i=close(S，inon－critical)∥最近的非關(guān)鍵節(jié)點(diǎn)

8) i=close(S，ik)∥關(guān)鍵節(jié)點(diǎn)i 的最近的具有非關(guān)鍵節(jié)點(diǎn)鄰居的關(guān)鍵節(jié)點(diǎn)鄰居

10) i=close(S，i)∥最近的關(guān)鍵節(jié)點(diǎn)鄰居

11) Backup(S)=i

備用節(jié)點(diǎn)確定以后，持續(xù)檢測相應(yīng)關(guān)鍵節(jié)點(diǎn)的狀態(tài)。一旦發(fā)現(xiàn)關(guān)鍵節(jié)點(diǎn)故障，備用節(jié)點(diǎn)觸發(fā)連通性恢復(fù)算法。

3.2 連通性恢復(fù)算法

關(guān)鍵節(jié)點(diǎn)n 的備用節(jié)點(diǎn)檢測到n 故障，則觸發(fā)連通性恢復(fù)過程，該過程包括非關(guān)鍵節(jié)點(diǎn)搜索和級聯(lián)移動(dòng)。搜索算法流程如下:

1)若備用節(jié)點(diǎn)是非關(guān)鍵節(jié)點(diǎn)，則搜索過程結(jié)束。

2)若備用節(jié)點(diǎn)不是非關(guān)鍵節(jié)點(diǎn)，則檢查其備用節(jié)點(diǎn)是否非關(guān)鍵節(jié)點(diǎn)，若是，搜索過程結(jié)束;否則，重復(fù)步驟(1)，步驟(2)，直到找到非關(guān)鍵節(jié)點(diǎn)。

級聯(lián)移動(dòng):搜索到非關(guān)鍵節(jié)點(diǎn)后，各節(jié)點(diǎn)級聯(lián)向故障節(jié)點(diǎn)移動(dòng)。如圖2 中，若關(guān)鍵節(jié)點(diǎn)F 故障，其備用節(jié)點(diǎn)L 是非關(guān)鍵節(jié)點(diǎn)，則L 直接移動(dòng)到F，即可恢復(fù)連通性。若K 故障，其備用節(jié)點(diǎn)E 也是關(guān)鍵節(jié)點(diǎn)，E 執(zhí)行搜索算法，找到非關(guān)鍵節(jié)點(diǎn)G，節(jié)點(diǎn)G，E 向K 級聯(lián)移動(dòng)，恢復(fù)網(wǎng)絡(luò)連通性。

圖2 連通性恢復(fù)Fig 2 Connectivity recovery

4 相鄰兩個(gè)節(jié)點(diǎn)同時(shí)故障的情況

本文將APDCR 擴(kuò)充，提出2—APDCR 處理兩個(gè)相鄰節(jié)點(diǎn)同時(shí)故障造成的網(wǎng)絡(luò)不連通問題，僅考慮至少一個(gè)節(jié)點(diǎn)是關(guān)鍵節(jié)點(diǎn)的情況。

4.1 第二備用節(jié)點(diǎn)選擇

針對兩個(gè)相鄰節(jié)點(diǎn)同時(shí)故障，備用節(jié)點(diǎn)選取標(biāo)準(zhǔn)如下:

1)兩個(gè)關(guān)鍵節(jié)點(diǎn)不能相互為備用節(jié)點(diǎn)。

2)兩個(gè)相鄰的節(jié)點(diǎn)一個(gè)是關(guān)鍵節(jié)點(diǎn)，一個(gè)是非關(guān)鍵節(jié)點(diǎn)時(shí):

a.若非關(guān)鍵節(jié)點(diǎn)不是關(guān)鍵節(jié)點(diǎn)的備用節(jié)點(diǎn)，則不需選擇第二備用節(jié)點(diǎn)

b.若非關(guān)鍵節(jié)點(diǎn)是關(guān)鍵節(jié)點(diǎn)的備用節(jié)點(diǎn)，則從二者共同的鄰居中選擇第二備用節(jié)點(diǎn)，若沒有共同鄰居，則從關(guān)鍵節(jié)點(diǎn)的其他1 跳鄰居中選擇。選擇標(biāo)準(zhǔn)同3.1 Algorithm 1。

3)兩個(gè)相鄰的節(jié)點(diǎn)都是關(guān)鍵節(jié)點(diǎn)時(shí):

a.若二者有各自獨(dú)立的備用節(jié)點(diǎn)，則不需選擇第二備用節(jié)點(diǎn):

b.若兩相鄰的關(guān)鍵節(jié)點(diǎn)中一個(gè)是另一個(gè)的備用節(jié)點(diǎn)，則需要選擇第二備用節(jié)點(diǎn)，選擇方法同步驟(2)中b。

4.2 連通性恢復(fù)

針對網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)同時(shí)發(fā)生故障的情況，有以下幾種場景:

1)故障的兩個(gè)相鄰節(jié)點(diǎn)n1是關(guān)鍵節(jié)點(diǎn)，n2是非關(guān)鍵節(jié)點(diǎn):

a.若n2不是n1的備用節(jié)點(diǎn)，則n1的備用節(jié)點(diǎn)直接移動(dòng)到n1的位置即可恢復(fù)連通性。如圖3 中關(guān)鍵節(jié)點(diǎn)M 和非關(guān)鍵節(jié)點(diǎn)N 同時(shí)故障，M 的備用節(jié)點(diǎn)I 移動(dòng)到M 位置即可恢復(fù)網(wǎng)絡(luò)連通性。

b.若n2是n1的備用節(jié)點(diǎn)，則第二備用節(jié)點(diǎn)檢測到二者故障，開始連通性恢復(fù)過程。如圖3 中關(guān)鍵節(jié)點(diǎn)L 及其備用節(jié)點(diǎn)R 同時(shí)故障，則第二備用節(jié)點(diǎn)X 開始非關(guān)鍵節(jié)點(diǎn)的搜索過程。找到非關(guān)鍵節(jié)點(diǎn)C，則X，C 向L 級聯(lián)移動(dòng)。

2)故障的兩個(gè)節(jié)點(diǎn)n1，n2都是關(guān)鍵節(jié)點(diǎn):

a.若n1，n2有各自獨(dú)立的備用節(jié)點(diǎn)，且備用節(jié)點(diǎn)都是非關(guān)鍵節(jié)點(diǎn)，則各自平行移動(dòng)到相應(yīng)的故障節(jié)點(diǎn)即可恢復(fù)連通性。

b.若n1，n2有各自的備用節(jié)點(diǎn)，且備用節(jié)點(diǎn)一個(gè)是關(guān)鍵節(jié)點(diǎn)，一個(gè)是非關(guān)鍵節(jié)點(diǎn)，則非關(guān)鍵節(jié)點(diǎn)直接移動(dòng)到關(guān)鍵節(jié)點(diǎn)位置。關(guān)鍵備用節(jié)點(diǎn)執(zhí)行3.2 中非關(guān)鍵節(jié)點(diǎn)搜索算法找到非關(guān)鍵節(jié)點(diǎn)，然后向故障節(jié)點(diǎn)執(zhí)行級聯(lián)移動(dòng)恢復(fù)網(wǎng)絡(luò)連通性。

c.若n1，n2有各自的備用節(jié)點(diǎn)，且備用節(jié)點(diǎn)全部是關(guān)鍵節(jié)點(diǎn)，則兩個(gè)備用節(jié)點(diǎn)都需要執(zhí)行非關(guān)鍵節(jié)點(diǎn)搜索過程。借助文獻(xiàn)［3］中防止沖突方式，搜索過程結(jié)束之前，搜索路徑上所有節(jié)點(diǎn)先鎖定，直到整個(gè)搜索過程結(jié)束。

d.若n2是n1的備用節(jié)點(diǎn)，則n2的備用節(jié)點(diǎn)和第二備用節(jié)點(diǎn)檢測到故障發(fā)生，觸發(fā)非關(guān)鍵節(jié)點(diǎn)搜索過程。如圖3關(guān)鍵節(jié)點(diǎn)L 和其備用節(jié)點(diǎn)R 同時(shí)故障，R 的備用節(jié)點(diǎn)S 檢測到R 故障，因?yàn)镾 是非關(guān)鍵節(jié)點(diǎn)，則直接移動(dòng)到R 位置即可;第二備用節(jié)點(diǎn)B 檢測到節(jié)點(diǎn)R，X 檢測到L 故障，搜索到非關(guān)鍵節(jié)點(diǎn)Q，然后Q，C，X 向L 級聯(lián)移動(dòng)。

圖3 2 節(jié)點(diǎn)故障連通性恢復(fù)Fig 3 Connectivity recovery for 2-node failure

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

本文通過一系列仿真實(shí)驗(yàn)驗(yàn)證算法的性能，在600 m×600 m 的正方形區(qū)域，隨機(jī)生成連通網(wǎng)絡(luò)。實(shí)驗(yàn)中設(shè)置網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)個(gè)數(shù)分別為20，40，60，80 和100，節(jié)點(diǎn)通信范圍從50，100，150 m 到200 m 變化。節(jié)點(diǎn)個(gè)數(shù)變化時(shí)，通信范圍保持在100 m;通信范圍變化時(shí)，網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)保持在60 個(gè)。對于相鄰兩節(jié)點(diǎn)同時(shí)故障情況，設(shè)置故障節(jié)點(diǎn)的任意一個(gè)1 跳鄰居故障。每個(gè)拓?fù)鋱?zhí)行30 次，取平均值作為實(shí)驗(yàn)結(jié)果。取移動(dòng)節(jié)點(diǎn)個(gè)數(shù)和節(jié)點(diǎn)移動(dòng)總距離作為性能指標(biāo)，并與DCR 策略做比較，實(shí)驗(yàn)結(jié)果如圖4～圖7 中各圖所示。

圖4 網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)變化時(shí)移動(dòng)節(jié)點(diǎn)數(shù)的變化Fig 4 Number change of mobile nodes with varying number of nodes in network

圖5 網(wǎng)絡(luò)通信范圍變化時(shí)移動(dòng)節(jié)點(diǎn)數(shù)變化Fig 5 Number change of mobile nodes with varying communication range of network

實(shí)驗(yàn)結(jié)果表明:1—APDCR 性能明顯優(yōu)于DCR(單節(jié)點(diǎn)故障)。這是因?yàn)?—APDCR 以2 跳關(guān)鍵節(jié)點(diǎn)作為關(guān)鍵節(jié)點(diǎn)，避免了處理過多“冗余”關(guān)鍵節(jié)點(diǎn)的可能，同時(shí)，1—APDCR 在選取備用節(jié)點(diǎn)時(shí)，限制了備用節(jié)點(diǎn)選取范圍，從而降低了長搜索路徑發(fā)生的幾率，減少了移動(dòng)節(jié)點(diǎn)的個(gè)數(shù)和節(jié)點(diǎn)總的移動(dòng)距離，從而節(jié)省了節(jié)點(diǎn)能耗，延長了網(wǎng)絡(luò)壽命。同時(shí)實(shí)驗(yàn)驗(yàn)證了2—APDCR 的可行性。

圖6 網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)變化時(shí)總移動(dòng)距離變化Fig 6 Total change of moving distance with varying number of nodes

圖7 通信范圍改變時(shí)總移動(dòng)距離Fig 7 Total change of moving distance with varying communication range

6 結(jié) 論

本文提出一種移動(dòng)無線傳感器網(wǎng)絡(luò)連通性自主恢復(fù)策略，在保證網(wǎng)絡(luò)連通性恢復(fù)的同時(shí)，算法設(shè)計(jì)重點(diǎn)考慮了算法的能耗。提出基于節(jié)點(diǎn)位置信息判別關(guān)鍵節(jié)點(diǎn)的算法，選取合適的備用節(jié)點(diǎn)，減少恢復(fù)過程中非關(guān)鍵節(jié)點(diǎn)的搜索范圍。另外，算法可以處理兩個(gè)相鄰節(jié)點(diǎn)同時(shí)故障的情況。在后續(xù)的研究中，將進(jìn)一步研究多節(jié)點(diǎn)同時(shí)故障時(shí)無線傳感器網(wǎng)絡(luò)連通性恢復(fù)問題。

［1］ Youns M，Senturk I F，Akkaya K，et al.Topology management techniques for tolerating node failures in wireless sensor networks:A survey［J］.Computer Networks，2014，58:254－283.

［2］ Senel F，Younis M.Relay node placement in structurally damaged wireless sensor networks via triangular steiner tree approximation［J］.Computer Communications，2011，34(16):1932－1941.

［3］ Akkaya K，Senel F，Thimmapuram A，et al.Distributed recovery from network partitioning in movable sensor/actor networks via controlled mobility［J］.IEEE Transactions on Computers，2010，59(2):258－271.

［4］ Younis M，Lee S，Gupta S，et al.A localized self－h(huán)ealing algorithm for networks of moveable sensor nodes［C］∥2008 IEEE Global Telecommunications Conference，2008 GLOBECOM，2008:1－5.

［5］ Tamboli N，Younis M.Coverage－aware connectivity restoration in mobile sensor networks［J］.Journal of Network and Computer Applications，2010，33(4):363－374.

［6］ Imran M，Younis M，Said A M，et al.Partitioning detection and connectivity restoration algorithm for wireless sensor and actor networks［C］∥2010 IEEE/IFIP 8th International Conference on Embedded and Ubiquitous Computing(EUC)，IEEE，2010:200－207.

［7］ Imran M，Younis M，Mdsaid A，et al.Localized motion－based connectivity restoration algorithms for wireless sensor and actor networks［J］.Journal of Network and Computer Applications，2012，35(2):844－856.

［8］ Senturk I F，Akkaya K，Yilmaz S.Distributed relay node positioning for connectivity restoration in partitioned wireless sensor networks［C］∥2012 IEEE Symposium on Computers and Communications(ISCC)，IEEE，2012:000301－000306.

［9］ Stojmenovic I，Simplotryl D，Nayak A.Toward scalable cut vertex and link detection with applications in wireless Ad Hoc networks［J］.Network，IEEE，2011，25(1):44－48.