馬桂真, 于 平

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

?

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

馬桂真1，2, 于 平1

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

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

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

0 引 言

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

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

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

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

問(wèn)題可建模為求無(wú)向圖的連通性問(wèn)題。無(wú)向圖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é)點(diǎn)的最大通信范圍。為了簡(jiǎn)單起見(jiàn)，網(wǎng)絡(luò)中每個(gè)分區(qū)用一個(gè)節(jié)點(diǎn)表示，假設(shè)網(wǎng)絡(luò)中至少存在一個(gè)障礙，障礙多邊形是凸多邊形。OCRS首先構(gòu)建分區(qū)最小生成樹(shù)，在最小生成樹(shù)構(gòu)建過(guò)程中考慮障礙，然后通過(guò)在最小生成樹(shù)的邊放置靜態(tài)或動(dòng)態(tài)節(jié)點(diǎn)，恢復(fù)網(wǎng)絡(luò)連通性，考慮的性能指標(biāo)是移動(dòng)節(jié)點(diǎn)的最大移動(dòng)距離和總移動(dòng)距離。本文還有如下的假設(shè)和定義:

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

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

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

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

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

如圖1(a)，邊s2-s7穿過(guò)障礙多邊形(o1,o2,o3,o4),則比較兩條鏈路s2-o1-o4-s7和s2-o2-o3-s7的長(zhǎng)度，選取較短的鏈路s2-o1-o4-s7代替邊s2-s8。而圖1(b)中，s2-s7和s2-s8兩條邊同時(shí)穿過(guò)障礙多邊形，按照?qǐng)D1(a)中算法，分別選取較短的鏈代替最小生成樹(shù)中的兩條邊，樹(shù)中沒(méi)有生成環(huán)，則算法結(jié)束。而對(duì)于圖1(c)中，s2-s7和s3-s8兩條邊同時(shí)穿過(guò)障礙多邊形，利用圖1(a)中算法分別選取最短的鏈代替原來(lái)的邊，這時(shí)候，圖中產(chǎn)生了環(huán)s2-s3-o1-s2,這在最小生成樹(shù)中是不允許的，OCRS將環(huán)中的最長(zhǎng)邊s2-s3去掉，形成考慮障礙的最小生成樹(shù)。

圖1 考慮障礙的最小生成樹(shù)構(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)建連通鏈路，即如何布置靜止或移動(dòng)節(jié)點(diǎn)在分區(qū)之間建立穩(wěn)固或暫時(shí)的連通鏈路。本文研究的是在中繼節(jié)點(diǎn)個(gè)數(shù)不充分的情況下，如何構(gòu)建連通鏈路。算法步驟如下：

1)確定中繼節(jié)點(diǎn)個(gè)數(shù)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖5 分區(qū)個(gè)數(shù)變化時(shí)總移動(dòng)距離Fig 5 Total moving distance vs number of segments

圖6 通信范圍變化時(shí)最大移動(dòng)距離Fig 6 The maximum moving distance vs communication range

圖7 通信范圍變化時(shí)總移動(dòng)距離Fig 7 Total moving distance vs communication range

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

5 結(jié) 論

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

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