考慮障礙的無線傳感器網(wǎng)絡(luò)連通性恢復(fù)策略

馬桂真, 于 平

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

?

考慮障礙的無線傳感器網(wǎng)絡(luò)連通性恢復(fù)策略

馬桂真1，2, 于 平1

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

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

無線傳感器網(wǎng)絡(luò); 連通性恢復(fù)； 障礙

0 引 言

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

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

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

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

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

假設(shè)1：所有的中繼節(jié)點(用來恢復(fù)網(wǎng)絡(luò)連通性的額外的節(jié)點)都可以按需移動。

假設(shè)2：網(wǎng)絡(luò)中至少有一個障礙，每個障礙是一個凸多邊形。障礙與網(wǎng)絡(luò)分區(qū)不重合，且最小生成樹中至少一條分穿過障礙多邊形。

定義2：若M表示分區(qū)個數(shù)，Navailable表示可獲得的中繼節(jié)點個數(shù)，則滿足如下表達式Navailable>M且Navailable

2 構(gòu)建考慮障礙的最小生成樹

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

如圖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)中算法，分別選取較短的鏈代替最小生成樹中的兩條邊，樹中沒有生成環(huán)，則算法結(jié)束。而對于圖1(c)中，s2-s7和s3-s8兩條邊同時穿過障礙多邊形，利用圖1(a)中算法分別選取最短的鏈代替原來的邊，這時候，圖中產(chǎn)生了環(huán)s2-s3-o1-s2,這在最小生成樹中是不允許的，OCRS將環(huán)中的最長邊s2-s3去掉，形成考慮障礙的最小生成樹。

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

3 恢復(fù)網(wǎng)絡(luò)連通性

恢復(fù)網(wǎng)絡(luò)連通性的主要工作是在不連通的網(wǎng)絡(luò)分區(qū)之間構(gòu)建連通鏈路，即如何布置靜止或移動節(jié)點在分區(qū)之間建立穩(wěn)固或暫時的連通鏈路。本文研究的是在中繼節(jié)點個數(shù)不充分的情況下，如何構(gòu)建連通鏈路。算法步驟如下：

1)確定中繼節(jié)點個數(shù)

假設(shè)最小生成樹中所有邊都放置靜止中繼節(jié)點，確定需要的中繼節(jié)點個數(shù)Ntotal。如圖2，如果最小生成樹全部放置靜止節(jié)點，需要21個靜止中繼節(jié)點，才能恢復(fù)網(wǎng)絡(luò)的連通性。

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

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

圖2 形成穩(wěn)定網(wǎng)絡(luò)需要的靜止中繼節(jié)點個數(shù)Fig 2 Number of static relay node needed for formation of stable network

3)相臨邊構(gòu)建三角形

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

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

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

若放置的額外節(jié)點個數(shù)大于Navailable，則執(zhí)行如下步驟：

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

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

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

圖3 節(jié)點放置完成后的網(wǎng)絡(luò)拓樸Fig 3 Network topology after finishing node placement

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

4 仿真實驗

在1 200m×1 200m的正方形區(qū)域，隨機生成網(wǎng)絡(luò)分區(qū)和障礙多邊形。實驗中，設(shè)置傳感器網(wǎng)絡(luò)分區(qū)個數(shù)從3～13，節(jié)點個數(shù)變化時，通信范圍固定在100m；通信范圍變化時，分區(qū)個數(shù)保持在9個?？色@得額外節(jié)點個數(shù)設(shè)置為Navailable=Ntotal×p，其中,0

圖4 分區(qū)個數(shù)變化時最大移動距離Fig 4 Maximum moving distance vs number of segments

圖5 分區(qū)個數(shù)變化時總移動距離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

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

5 結(jié) 論

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

[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-)，女，山東單縣人，博士研究生，講師，主要研究方向為無線傳感器網(wǎng)絡(luò)故障管理。