馬桂真，于 平

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

0 引 言

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

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

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

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

本文研究無線傳感器網(wǎng)絡的連通性自主恢復，問題可建模為求無向圖的連通性問題。無向圖G=(S，E)，其中，S={s1，s2，s3，…，sn}代表傳感器節(jié)點集，E={(si，sj)|dis(si，sj)＜R}，dis(si，sj)表示節(jié)點si，sj之間的距離，R 表示節(jié)點的最大通信范圍。網(wǎng)絡中節(jié)點可按需移動，各節(jié)點之間通信范圍都為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 關鍵節(jié)點:?si∈S，若去掉si其所有的k 跳鄰居組成的子圖是不連通的，則節(jié)點si是k 跳關鍵節(jié)點。

2 確定關鍵節(jié)點

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

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

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

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

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

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

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

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

3 單個關鍵節(jié)點故障

3.1 備用節(jié)點確定

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

Algorithm 1 Backupselect(S)

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

1)if critical(S)=true then

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

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

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

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

11) Backup(S)=i

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

3.2 連通性恢復算法

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

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

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

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

圖2 連通性恢復Fig 2 Connectivity recovery

4 相鄰兩個節(jié)點同時故障的情況

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

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

針對兩個相鄰節(jié)點同時故障，備用節(jié)點選取標準如下:

1)兩個關鍵節(jié)點不能相互為備用節(jié)點。

2)兩個相鄰的節(jié)點一個是關鍵節(jié)點，一個是非關鍵節(jié)點時:

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

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

3)兩個相鄰的節(jié)點都是關鍵節(jié)點時:

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

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

4.2 連通性恢復

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

1)故障的兩個相鄰節(jié)點n1是關鍵節(jié)點，n2是非關鍵節(jié)點:

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

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

2)故障的兩個節(jié)點n1，n2都是關鍵節(jié)點:

a.若n1，n2有各自獨立的備用節(jié)點，且備用節(jié)點都是非關鍵節(jié)點，則各自平行移動到相應的故障節(jié)點即可恢復連通性。

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

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

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

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

5 仿真實驗

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

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

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

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

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

圖7 通信范圍改變時總移動距離Fig 7 Total change of moving distance with varying communication range

6 結 論

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

［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.