移動無線傳感器網絡連通性自主恢復算法

馬桂真，于 平

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

0 引 言

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

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

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

1 系統模型與假設

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

2 確定關鍵節點

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

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

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

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

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

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

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

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

3 單個關鍵節點故障

3.1 備用節點確定

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

Algorithm 1 Backupselect(S)

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

1)if critical(S)=true then

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

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

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

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

11) Backup(S)=i

備用節點確定以后，持續檢測相應關鍵節點的狀態。一旦發現關鍵節點故障，備用節點觸發連通性恢復算法。

3.2 連通性恢復算法

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

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

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

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

圖2 連通性恢復Fig 2 Connectivity recovery

4 相鄰兩個節點同時故障的情況

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

4.1 第二備用節點選擇

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

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

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

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

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

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

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

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

4.2 連通性恢復

針對網絡中兩個節點同時發生故障的情況，有以下幾種場景:

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

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

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

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

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

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

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

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

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

5 仿真實驗

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

圖4 網絡節點數變化時移動節點數的變化Fig 4 Number change of mobile nodes with varying number of nodes in network

圖5 網絡通信范圍變化時移動節點數變化Fig 5 Number change of mobile nodes with varying communication range of network

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

圖6 網絡節點個數變化時總移動距離變化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 結 論

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

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