考慮障礙的無線傳感器網絡連通性恢復策略

馬桂真, 于 平

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

?

考慮障礙的無線傳感器網絡連通性恢復策略

馬桂真1，2, 于 平1

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

布置在戰場、搜救現場的無線傳感器網絡往往會遭受大面積破壞，從而將無線傳感器網絡分割成多個不連通的分區，對網絡性能造成很大影響。在這種人工很難干預的場景，無線傳感器網絡的自主恢復非常重要。提出一種考慮障礙的無線傳感器網絡連通性恢復策略(OCRS)，利用可移動的無線傳感器節點(MDCs)在分區之間移動(收集網絡數據)形成暫時的連通線路，在節點移動過程中，考慮路徑上障礙。首先構建分區的基于障礙避免的最小生成樹，然后優化移動節點的移動路徑，最小化移動節點的最大移動距離和總的移動距離。仿真實驗結果證實了OCRS的有效性。

無線傳感器網絡; 連通性恢復； 障礙

0 引 言

在許多應用中，無線傳感器網絡都布置在條件艱苦、無人值守的環境，比如戰場、生命搜救現場等。在這些場景中，無線傳感器網絡極易受到大面積破壞，使得網絡被分割成多個不連通的分區。不同分區之間的節點無法協作，會大大影響無線傳感器網絡的性能，甚至無法完成任務。在這種情況下，無線傳感器網絡連通性的恢復就非常重要。

移動無線傳感器網絡連通性恢復問題研究成為近年來研究的熱點7〗。文獻中關于無線傳感器網絡分區連通性恢復方法的研究主要分為三種：一種是在分區之間布置靜止中繼節點，形成連通網絡，這種方法一般是在額外節點充足的情況下進行；一種是在可獲得額外節點個數小于分區個數的情況下，利用移動節點收集、交換分區之間數據；最后一種是采用靜止和移動節點結合的方法，當可獲得的額外節點個數小于形成穩固網絡拓撲需要的節點個數，又大于分區個數的時候，一部分額外節點保持靜止布置在分區之間，一部分作為移動數據收集者(MDCs)，在分區之間形成暫時的連通鏈路，進行數據交換。在戰場等緊急場景中，網絡遭受大面積破壞時，一時很難獲得足夠多的節點恢復網絡的連通性，利用移動節點構建暫時連通網絡成為一種解決辦法。本文研究移動節點在分區之間移動形成暫時的連通鏈路，恢復網絡的連通性。

利用移動節點構建暫時連通網絡成為近年來研究熱點，典型的方法有IDM-kMDC],MINDS]和FeSMoR\〗，這幾種方法都是利用MDCs在分區之間建立暫時的鏈路，進行分區之間數據交換，但是所有這些方法都假設節點沿直線移動，路線上不存在障礙，這是不現實的。本文提出一種考慮障礙的無線傳感器網絡連通性恢復策略(obstacle-aware connectivity restoratio strategy,OCRS)研究障礙情況下，無線傳感器網絡分區連通性恢復問題，并通過仿真實驗驗證算法的有效性。

1 系統模型與假設

問題可建模為求無向圖的連通性問題。無向圖G=(S,E,o)， 其中，S={s1,s2,s3…sn} 代表傳感器網絡分區集合，E={(si,sj)|si,sj∈S} ，o2={o1,o2,o3,…,om},代表障礙多邊形。Dis(si,sj) 表示分區si,sj之間的距離，R表示節點的最大通信范圍。為了簡單起見，網絡中每個分區用一個節點表示，假設網絡中至少存在一個障礙，障礙多邊形是凸多邊形。OCRS首先構建分區最小生成樹，在最小生成樹構建過程中考慮障礙，然后通過在最小生成樹的邊放置靜態或動態節點，恢復網絡連通性，考慮的性能指標是移動節點的最大移動距離和總移動距離。本文還有如下的假設和定義:

假設1：所有的中繼節點(用來恢復網絡連通性的額外的節點)都可以按需移動。

假設2：網絡中至少有一個障礙，每個障礙是一個凸多邊形。障礙與網絡分區不重合，且最小生成樹中至少一條分穿過障礙多邊形。

定義2：若M表示分區個數，Navailable表示可獲得的中繼節點個數，則滿足如下表達式Navailable>M且Navailable

2 構建考慮障礙的最小生成樹

本文將移動節點總的移動距離(total move length)和最大移動距離(maximum move length)作為算法性能指標，為了盡可能減少節點的總移動距離和最大移動距離，在分區之間構建最小生成樹，然后決定在最小生成樹的各邊布置靜止或移動節點。OCRS首先利用Prim算法構建分區之間的最小生成樹，然后檢測生成樹中哪條邊穿過障礙，如果邊si-sj穿過障礙多邊形，則改變該邊的線路，繞開障礙。如果有多條邊穿過障礙，則分別改變各邊的移動路徑，改變路徑后如果圖中不產生環，則算法完成;如果產生環，則將最長邊去除，去除圖中的環。

如圖1(a)，邊s2-s7穿過障礙多邊形(o1,o2,o3,o4),則比較兩條鏈路s2-o1-o4-s7和s2-o2-o3-s7的長度，選取較短的鏈路s2-o1-o4-s7代替邊s2-s8。而圖1(b)中，s2-s7和s2-s8兩條邊同時穿過障礙多邊形，按照圖1(a)中算法，分別選取較短的鏈代替最小生成樹中的兩條邊，樹中沒有生成環，則算法結束。而對于圖1(c)中，s2-s7和s3-s8兩條邊同時穿過障礙多邊形，利用圖1(a)中算法分別選取最短的鏈代替原來的邊，這時候，圖中產生了環s2-s3-o1-s2,這在最小生成樹中是不允許的，OCRS將環中的最長邊s2-s3去掉，形成考慮障礙的最小生成樹。

圖1 考慮障礙的最小生成樹構建Fig 1 Construction of obstacle-aware the minimum spanning tree

3 恢復網絡連通性

恢復網絡連通性的主要工作是在不連通的網絡分區之間構建連通鏈路，即如何布置靜止或移動節點在分區之間建立穩固或暫時的連通鏈路。本文研究的是在中繼節點個數不充分的情況下，如何構建連通鏈路。算法步驟如下：

1)確定中繼節點個數

假設最小生成樹中所有邊都放置靜止中繼節點，確定需要的中繼節點個數Ntotal。如圖2，如果最小生成樹全部放置靜止節點，需要21個靜止中繼節點，才能恢復網絡的連通性。

2)處理沿障礙多邊形的邊鏈

由于在障礙多邊形邊沿放置的無線傳感器節點可能受到障礙干擾而影響傳輸性能，故單獨處理邊鏈。在邊鏈上每個障礙多邊形頂點各放置一個靜止節點，若二個頂點oi,oj之間的距離滿足dis(oi,oj)>2R，則放置一個移動節點；若R

圖2 形成穩定網絡需要的靜止中繼節點個數Fig 2 Number of static relay node needed for formation of stable network

3)相臨邊構建三角形

OCRS旨在減少移動節點總的移動距離和最大移動距離，某些相鄰的三個節點構成的三角形周長可能比某些邊邊長要短，為了節省節點移動距離，在節點放置迭代算法開始之前，首先對最小生成樹的相臨邊構造三角形(沿障礙多邊形的邊鏈不參與構建三角形)。如圖2(b)所示，相臨邊s3-s4和s4-s5構成一個三角形。而o4-s7是邊鏈，所以,不與邊s7-s6構成三角形。

4)具體節點放置迭代算法

Tri表示三角形集合，Et代表最小生成樹中邊的集合。

若放置的額外節點個數大于Navailable，則執行如下步驟：

a.選擇最小生成樹中的最短邊si-sj，檢查三角形集合Tri中是否存在周長小于該邊邊長的三角形，若存在，則執行(i)，否則,執行(ii)。

(i)若不存在周長小于si-sj邊長的三角形，檢查邊si-sj需要靜止節點的個數。如果需要1個靜止中繼節點即可恢復兩個頂點分區之間的連通性，則放置一個靜止節點；若需要2個以上的靜止中繼節點才能恢復頂點分區之間連通性(假設需要N個，N≥2)，則二頂點之間只需放置一個移動節點，這樣就可節省N-1個節點。將該邊從集合Et中去除。如圖3中邊s9-s10，只需一個靜止節點即可連通s9和s10兩個分區，則只需在合適位置放一個靜止節點即可。對于邊s8-s9，需要兩個靜止節點才能形成穩固的連通網絡，則用一個移動節點代替原來的靜止節點，該移動節點在兩分區之間移動形成短暫連通線路，這樣會節省一個額外節點。

(ii)若存在周長小于邊長的三角形，則三角形的三條邊上放置一個移動節點，在三個分區之間形成短暫連通線路。如圖3中,三角形s3-s4-s5周長小于當前樹中最短邊s1-s2，則三角形的三條邊放置一個移動節點即可。

圖3 節點放置完成后的網絡拓樸Fig 3 Network topology after finishing node placement

b.對于需要處理的最后一個最短邊，比如圖3中邊s1-s2，若Navailable=18，即只需邊s1-s2節省1個節點即可完成網絡連通性恢復，在這種情況下，邊s1-s2上放置兩個靜止節點，一個移動節點。這樣其余沒處理的邊全部放置靜止中繼節點即可。算法結束。

4 仿真實驗

在1 200m×1 200m的正方形區域，隨機生成網絡分區和障礙多邊形。實驗中，設置傳感器網絡分區個數從3～13，節點個數變化時，通信范圍固定在100m；通信范圍變化時，分區個數保持在9個。可獲得額外節點個數設置為Navailable=Ntotal×p，其中,0

圖4 分區個數變化時最大移動距離Fig 4 Maximum moving distance vs number of segments

圖5 分區個數變化時總移動距離Fig 5 Total moving distance vs number of segments

圖6 通信范圍變化時最大移動距離Fig 6 The maximum moving distance vs communication range

圖7 通信范圍變化時總移動距離Fig 7 Total moving distance vs communication range

實驗結果表明:隨著分區個數的增大，節點最大移動距離整體呈下降趨勢，總移動距離整體持平；隨著節點通信范圍的增大，最大移動距離和總移動距離整體呈下降趨勢，和實驗預期吻合。由于文獻中相關方法都沒有考慮節點移動過程中遇到障礙的可能性，所以,本實驗數據與已有方法實驗數據沒有可比性。通過優化恢復算法，實驗發現在分區個數大于6時,OCRS的性能優于IDM-kMDC，這里由于篇幅限制，不再贅述。

5 結 論

本文提出一種考慮障礙的無線傳感器網絡連通性恢復策略，利用節點的移動性在網絡分區之間形成暫時連通鏈路。該策略首先構建分區之間的最小生成樹，最小生成樹的邊穿過障礙多邊形時，選取較短的邊鏈作為最小生成樹的邊。然后通過迭代算法確定最小生成樹的各邊中繼節點的放置，完成分區之間連通性的恢復。在后續的研究中，將進一步研究存在多個障礙多邊形時，無線傳感器網絡連通性恢復問題。

[1] Senel F,Younis M.Relay node placement in structurally damaged wireless sensor networks via triangular steiner tree approxima-tion].Computer Communications,2011,34(16):1932-1941.

[2] Akkaya K,Senel F,Thimmapuram A,et al.Distributed recovery from network partitioning in movable sensor/actor networks via controlled mobility].IEEE Transactions on Computers,2010,59(2):258-271.

[3] Younis M,Lee S,Gupta S,et al.A localized self-healing algorithm for networks of moveable sensor nodes]∥2008 IEEE GLOBECOM，2008 Global Telecommunications Conference,IEEE,2008:1-5.

[4] Tamboli N,Younis M.Coverage-aware connectivity restoration in mobile sensor networks].Journal of Network and Computer Applications,2010,33(4):363-374.

[5] Imran M,Younis M,Said A.M,et al.Partitioning detection and connectivity restoration algorithm for wireless sensor and actor networks]∥2010 IEEE/IFIP The 8th International Conference on Embedded and Ubiquitous Computing(EUC),IEEE,2010:200-207.

[6] Senturk I F,Akkaya K,Yilmaz S.Distributed relay node positioning for connectivity restoration in partitioned wireless sensor networks]∥2012 IEEE Symposium on Computers and Communications(ISCC),IEEE,2012:000301-000306.

[7] Stojmenovic I,Simplot-Ryl D,Nayak A.Toward scalable cut vertex and link detection with applications in wireless Ad Hoc networks].Network,IEEE,2011,25(1):44-48.

[8] Senel F,Younis M.Optimized interconnection of disjoint wireless sensor network segments using K mobile data collectors]∥Proc of the IEEE Int’l Conf on Communications,ICC’12,Ottawa,Canada,2012.

[9] Joshi Y K,Younis M.Mobility-based internetworking of disjoint segments]∥2014 The 27th Biennial Symposium on Communications,IEEE,2014:193-197.

[10] Stanislaus J L V M,Younis M.Delay conscious federation of multiple wireless sensor networks segments using mobile relays]∥Proc of the 76th IEEE Vehicular Technology Conference,VTC 2012—Fall,Québec City,Canada,2012.

于 平，通訊作者，E—mail：lytyuping@buu.edu.cn。

Obstacle-aware connectivity restoration strategy for WSNs

MA Gui-zhen1,2, YU Ping1

(1.Beijing Key Laboratory of Information Service Engineering,Beijing Union University,Beijing 100106,China;2.State Key Laboratory of Networking and Switching Technology,Beijing University of Posts and Telecommunications,Beijing 100876,China)

Wireless sensor networks(WSNs) in battle field,search and rescue scene are at increased risk of large scale damages and networks are partitioned into disjoint segments.Self-restoring of WSNs in such a case is crucial.Present an obstacle-aware connectivity restoration strategy(OCRS),which places mobile nodes acting as mobile data collectors(MDCs) among segments to provide intermittent communication links.During MDCs traveling,obstacles are taken into account.Construct obstacle-avoiding minimum spanning tree of segments,and optimize mobile node travel routers.Minimize the maximum moving distance and total moving distance of moving node.Effectiveness of OCRS is validated through simulation experiments.

wireless sensor networks(WSNs); connectivity restoration; obstacle

2015—11—13

10.13873/J.1000—9787(2016)10—0123—04

TP 212.9; TN 929.5

A

1000—9787(2016)10—0123—04

馬桂真(1979-)，女，山東單縣人，博士研究生，講師，主要研究方向為無線傳感器網絡故障管理。