梁久禎，李軍飛

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院,江蘇 無錫 214122)

?

·信息科學(xué)·

基于Steiner點的移動傳感網(wǎng)絡(luò)匯聚節(jié)點選址

梁久禎，李軍飛

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院,江蘇 無錫 214122)

匯聚節(jié)點;移動傳感網(wǎng)絡(luò);Steiner中心;結(jié)構(gòu)意識自適應(yīng)

無線傳感器網(wǎng)絡(luò)(WSN)是一個非常有前景的技術(shù),有著廣闊的應(yīng)用潛力,如戰(zhàn)場監(jiān)視、事件檢測、敵情監(jiān)視和動物行為發(fā)現(xiàn)等。隨著無線通信和微系統(tǒng)技術(shù)進步,使得各種低功耗和低成本效益的傳感器平臺廣泛地應(yīng)用在軍事、民用、醫(yī)療等領(lǐng)域,旨在讓人們更好地與物理世界溝通。

近幾年,移動傳感網(wǎng)絡(luò)(mWSNs)應(yīng)用和研究越來越廣泛。像水下傳感網(wǎng)絡(luò)[1],節(jié)點都是伴隨水流、潮汐不停地發(fā)生位置移動,文獻(xiàn)[2]研究野生斑馬生活習(xí)性,根據(jù)斑馬生活運動習(xí)性將斑馬網(wǎng)絡(luò)(ZebraNet)分為放牧,放牧行走和快速奔跑三層移動模型;斑馬網(wǎng)絡(luò)和水下網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)時刻都在發(fā)生變化,這種群體移動網(wǎng)絡(luò)都需要有動態(tài)實時的匯聚選址策略來滿足網(wǎng)絡(luò)動態(tài)變化。

目前,國內(nèi)外學(xué)者對匯聚節(jié)點的選址的研究中做了一定的工作。文獻(xiàn)[3]使用蟻群路由算法,在面向壽命的策略上實現(xiàn)了網(wǎng)絡(luò)壽命的大幅提高; 文獻(xiàn)[4]提出了4種匯聚節(jié)點移動模式,通過充分利用匯聚節(jié)點的移動特征來實現(xiàn)數(shù)據(jù)包高效分發(fā),將任務(wù)轉(zhuǎn)移到能量多的匯聚節(jié)點處提升網(wǎng)絡(luò)性能?？梢钥闯瞿壳敖^大多數(shù)算法是基于靜態(tài)的網(wǎng)絡(luò)或缺乏自適應(yīng)能力。

在無線傳感網(wǎng)絡(luò)中,邊緣檢測常用來發(fā)現(xiàn)目標(biāo)是非常有效的。文獻(xiàn)[5]設(shè)計了結(jié)構(gòu)意識自適應(yīng)算法(SASA),通過在井下天頂上均勻部署傳感器節(jié)點,當(dāng)塌方發(fā)生時,塌方會帶走部分節(jié)點,塌方邊緣的節(jié)點會形成一個凸多邊形結(jié)構(gòu),從而來預(yù)報塌方的大小和具體位置。文獻(xiàn)[6]提出了一種本地事件邊界檢測算法,實現(xiàn)了錯誤節(jié)點有效檢測。以上表明邊結(jié)構(gòu)是群體網(wǎng)絡(luò)的一個非常有價值的特征。

針對以上問題,本文提出了一種在移動傳感網(wǎng)絡(luò)中使用Steiner點作為匯聚節(jié)點位置的SCSN模型,該模型是基于邊結(jié)構(gòu)的設(shè)計,并結(jié)合增強型自意識自適應(yīng)算法(ASASA);能夠適用于群體特征的移動傳感器網(wǎng)絡(luò)。解決了移動網(wǎng)絡(luò)匯聚節(jié)點選址難問題。

1 SCSN系統(tǒng)模型

SCSN主要是針對一個擁有大規(guī)模傳感器節(jié)點的移動傳感器網(wǎng)絡(luò),如圖1,所有的節(jié)點整體以一個結(jié)構(gòu)不斷變化的凸多邊形群體以非直線的軌跡發(fā)生移動;網(wǎng)絡(luò)采用單個可移動中心匯聚節(jié)點,負(fù)責(zé)全網(wǎng)感知數(shù)據(jù)的匯聚外,還要負(fù)責(zé)SCSN移動網(wǎng)絡(luò)邊結(jié)構(gòu)的構(gòu)造和動態(tài)維護。傳感器節(jié)點的定位都采用被動定位,像安裝GPS模塊或是基于錨節(jié)點的定位算法,節(jié)點每次SCSN更新負(fù)責(zé)上傳自己新的位置信息。

圖1 群居野生斑馬活動的移動網(wǎng)絡(luò)實例Fig.1 Mobile network of wild zebra

SCSN模型網(wǎng)絡(luò)節(jié)點分為中心匯聚節(jié)點、邊節(jié)點和內(nèi)部節(jié)點(如圖2)。

1.1 SCSN算法

SCSN算法運行在中心匯聚節(jié)點,主要負(fù)責(zé)算法的具體實現(xiàn),偽代碼算法如下。

1. Absolute position convert to relative position

2. if initialed == false

3.S=E; initialed = true(Erepresent all nodes)

4. end if

5. broadcast request As for Convex nodesSposition

6. do receive packagesPS

while all requested nodes′ positon received

7. Construct new convex polygonS

8. BroadcastS

9. # calculate the steiner pointP

10.P= Steiner(S)

11. Sink node move toP

12. sleep (T)

13. Continue

系統(tǒng)初始化時,設(shè)置凸頂點集合S為所有節(jié)點集E(S=E)(第2-3行),凸殼重構(gòu)周期為T。SCSN系統(tǒng)每一周期更新時,首先匯聚節(jié)點廣播請求邊節(jié)點凸集S返回當(dāng)前位置數(shù)據(jù)(第5行),邊節(jié)點收到廣播后,通過自身定位模塊計算自己當(dāng)前位置并將最新的位置信息上傳給匯聚節(jié)點; 匯聚節(jié)點收到所有請求邊節(jié)點的位置數(shù)據(jù)包時(第6行),構(gòu)造出網(wǎng)絡(luò)的凸多邊形頂點新集合S(第7行),如圖3(t1),然后廣播邊結(jié)構(gòu)頂點集合S(第8行);普通節(jié)點收到廣播后,保存當(dāng)前網(wǎng)絡(luò)邊結(jié)構(gòu)頂點集合S位置信息,如發(fā)現(xiàn)自己坐標(biāo)Pi∈S,就將自己設(shè)置為邊節(jié)點(圖2深色點);這時每個節(jié)點都有最新網(wǎng)絡(luò)凸多邊形的位置信息;同時匯聚節(jié)點計算出新的Steiner中心P(第10行,圖2五角星),并移動到新P處(第11行)。

圖2 連續(xù)時間凸殼的動態(tài)更新Fig.2 Convex hull dynamic updates continuously

在移動網(wǎng)絡(luò)中,圖2分別表示連續(xù)時刻t1,t2,…,tn網(wǎng)絡(luò)節(jié)點移動拓?fù)浣Y(jié)構(gòu)圖,節(jié)點的自由移動使得移動網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不斷發(fā)生變化,Steiner中心需要實時的更新邊結(jié)構(gòu)才能滿足實際的需求。在每個重構(gòu)周期T到達(dá)后(第12行),匯聚節(jié)點廣播請求所有邊節(jié)點Pi(Pi∈S)位置數(shù)據(jù)包As(第5行),重復(fù)步驟(5-12),周期性的更新凸結(jié)構(gòu)和Steiner中心P,讓匯聚節(jié)點實時的保持在Steiner中心位置,如圖2匯聚節(jié)點不斷的移動到新的位置。圖3表示移動網(wǎng)絡(luò)在連續(xù)變化時間內(nèi),通過周期性的更新凸殼來保持匯聚節(jié)點在Steiner中心處的SCSN系統(tǒng)模型圖。

圖3 SCSN系統(tǒng)模型變化圖Fig.3 SCSN model

1.2 ASASA算法

ASASA(Advanced Structure-Aware self-adaptive)是一種基于邊界意識自適應(yīng)的算法。SCSN算法在周期性的更新邊結(jié)構(gòu)時,每次只請求凸殼頂點節(jié)點集合S的位置信息,無法判斷內(nèi)部節(jié)點是否移出凸殼。如圖5節(jié)點A,需要A自身意思判斷和上報違規(guī)情況。按破換邊結(jié)構(gòu)類型分為以下3種情況,如圖4。

Case 1 凸殼邊節(jié)點移動到內(nèi)部節(jié)點以內(nèi)(圖4a);

Case 2 內(nèi)部節(jié)點移動到凸殼以外(圖4b);

Case 3 邊節(jié)點向內(nèi)和內(nèi)部節(jié)點向外移動(圖4c)。

圖4 3種凸殼變換違規(guī)情況Fig.4 Three cases of violations

以上都會造成邊結(jié)構(gòu)受到非頂點節(jié)點的破壞,但是，SCSN算法匯聚節(jié)點自身只能獲取頂點集合的位置信息,無法判斷非頂點節(jié)點的位置是否越界。不會將外圍非頂點節(jié)點添加到頂點集合S中。為了維護正確的邊結(jié)構(gòu),設(shè)計了增強型結(jié)構(gòu)意識自適應(yīng)(ASASA)算法來解決以上問題。

ASASA算法實現(xiàn):

第一步 內(nèi)部節(jié)點Pi接收最新廣播凸頂點集S。

第二步 比較自己位置Pi和S的關(guān)系,如果Pi(圖4A點)發(fā)現(xiàn)自身的相對位置移動到了凸殼的外部(Pi?Vs),意識到自己破壞了現(xiàn)有的邊結(jié)構(gòu),為了適應(yīng)SCSN邊結(jié)構(gòu)算法,Pi就向匯聚節(jié)點發(fā)送自己的新位置并請求添加到頂點集合S中。

第三步 匯聚節(jié)點接收到破壞邊界的請求后,將請求節(jié)點Pi添加到集合S中,重新構(gòu)造凸殼。

第四步 廣播新凸頂點集S。

圖5 違規(guī)節(jié)點請求重構(gòu)凸殼Fig.5 Violated node request reconstruct new convex hull

在運行網(wǎng)絡(luò)有節(jié)點破壞邊結(jié)構(gòu)情況下,通過以上步驟就可以將3種違規(guī)情況邊結(jié)構(gòu)及時糾正過來了,恢復(fù)SCSN系統(tǒng)的正常運行。以上只需內(nèi)部節(jié)點的自意識來實現(xiàn)凸多邊形邊結(jié)構(gòu)的動態(tài)維護。平時內(nèi)部節(jié)點的任意移動都不會影響到SCSN。SCSN和ASASA的結(jié)合使得網(wǎng)絡(luò)只需周期性獲取凸頂點節(jié)點Pi(其中Pi∈S)位置信息就可以動態(tài)維護好整個網(wǎng)絡(luò)結(jié)構(gòu)及匯聚節(jié)點位置。

2 Steiner移動應(yīng)用高穩(wěn)定低偏心性

定義 1[8]設(shè)P是空間Rn上的d-維的凸多面體,那么Steiner點的函數(shù)離散定義

(1)

圖6 Steiner點的幾何定義Fig.6 Definition of Steiner

表1 R2上中心函數(shù)的對比[7]Tab.1 Compared different centre functions in R2

文獻(xiàn)[7]中Durocher 在題目中指出Steiner中心在移動應(yīng)用中具有高穩(wěn)定和低偏心的特征。文中強調(diào)偏心性和穩(wěn)定性是一個相對的性質(zhì),偏心性越小穩(wěn)定性越強,反之亦然。表1是Durocher通過理論推導(dǎo)得出Steiner中心和其他4種函數(shù)中心的λ-偏心性和k-穩(wěn)定性值。Durocher強調(diào)λ-偏心性值越小表示偏心性越低,k-穩(wěn)定性值越大表示穩(wěn)定性越高,Steiner的k-穩(wěn)定性為0.785 4、λ-偏心性為1.115 3。通過表中數(shù)據(jù)對比可以看出, Steiner中心相比其他中心有低偏心性和高穩(wěn)定性的優(yōu)勢。低偏心可使匯聚節(jié)點位置周期更新的中心位置移動的偏移量較小;高穩(wěn)定可使中心每次更新移動距離穩(wěn)定,不會出現(xiàn)忽遠(yuǎn)忽近。這對提升移動網(wǎng)絡(luò)的整體性能來說是非常關(guān)鍵的。

3 性能分析與評價

無線傳感器網(wǎng)絡(luò)是一門綜合性非常強的技術(shù),作為物聯(lián)網(wǎng)的感知神經(jīng)末梢,對物理世界感知數(shù)據(jù),其部署環(huán)境惡劣、能量和傳輸距離有限、應(yīng)用場景復(fù)雜多樣,對網(wǎng)絡(luò)性能多方面提出嚴(yán)格的要求。參照移動傳感器網(wǎng)絡(luò)運行特點,做出以下部分性能對比分析。

3.1 動態(tài)自適應(yīng)

移動傳感器網(wǎng)絡(luò)中節(jié)點的自由移動對算法的動態(tài)實時性提出了非常高的要求,節(jié)點的移動使得下一時刻網(wǎng)絡(luò)的整體拓?fù)浣Y(jié)構(gòu)和路由鏈路發(fā)生改變,基于位置或者鏈路信息的算法需重新獲取整個網(wǎng)絡(luò)的結(jié)構(gòu)才能重新計算新位置。傳統(tǒng)的算法缺乏動態(tài)自適應(yīng)和自意識,一旦網(wǎng)絡(luò)結(jié)構(gòu)發(fā)生變化,算法就失效了。

從圖3SCSN的運動的模型可以看出。SCSN通過周期性的更新頂點節(jié)點位置信息表來維護實時的網(wǎng)絡(luò)邊結(jié)構(gòu)和維持匯聚節(jié)點在Steiner中心處。并結(jié)合ASASA算法,使用邊界意識來動態(tài)維護好整個網(wǎng)絡(luò)的凸多邊形結(jié)構(gòu),頂點的添加和刪除都能夠通過ASASA及時的修正過來。動態(tài)變化的網(wǎng)絡(luò)始終保障匯聚節(jié)點在整個過程中動態(tài)實時的處于Steiner處。以上可以看出SCSN具有非常好的動態(tài)自意識、自適應(yīng)能力。

3.2 低時延

文獻(xiàn)[10],Akkaya等人認(rèn)為時延在實時性的應(yīng)用場景中(如軍事檢測、野生動物發(fā)現(xiàn)、目標(biāo)跟蹤)是一個非常關(guān)鍵的指標(biāo),并定義時延和邊界節(jié)點到匯聚節(jié)點的最大跳數(shù)(K-hops)有關(guān)。移動網(wǎng)絡(luò)對數(shù)據(jù)的實時性要求是非常高的,數(shù)據(jù)傳輸中的每經(jīng)過一跳需要消耗上百毫秒的時間,跳數(shù)(K)越小實時性越高。

圖7是隨機測試的一個不均勻傳感器網(wǎng)絡(luò),其中節(jié)點最大傳輸半徑為15m,,測試比較了Steiner中心、最小距離和文獻(xiàn)[3]的基于壽命算法選取匯聚節(jié)點位置時K-hops的值,根據(jù)文獻(xiàn)[3]算法的能量公式和距離的平方相關(guān),中心位置偏向密集一方。圖8顯示測試網(wǎng)絡(luò)不同跳數(shù)內(nèi)的節(jié)點所占的百分比?？梢园l(fā)現(xiàn)基于Steiner算法在A點時(K=5)所有節(jié)點都可以到達(dá)匯聚節(jié)點,同樣從B，C兩點是最小距離和和基于壽命算法的K值點分別為K=7，K=6。從圖7各中心點的位置和圖8對比實驗分析可以得到,最小距離和和Chen算法有偏向密集一邊,使得中心偏密集一方,從而稀疏一側(cè)的跳數(shù)會加大。Steiner中心處于凸多邊形的區(qū)域中心,使得中心到凸殼的邊距離比較平均,降低了網(wǎng)絡(luò)最大傳輸距離，從而減少網(wǎng)絡(luò)的最大跳數(shù),加快網(wǎng)絡(luò)收斂速度。

圖7 隨機不均勻網(wǎng)絡(luò)節(jié)點分布圖Fig.7 A test case of random distribution network

圖8 K-hops節(jié)點所占的百分比Fig.8 The percentage of K-hops nodes

3.3 低復(fù)雜度

圖9 節(jié)點個數(shù)復(fù)雜度Fig.9 Complexity of the number of nodes

3.4 強魯棒性

圖10為在100個節(jié)點的測試網(wǎng)絡(luò)中,算法在一次更新匯聚節(jié)點位置時,離匯聚節(jié)點不同跳數(shù)(K-hops)節(jié)點的平均轉(zhuǎn)發(fā)包的個數(shù)。從圖中很容易發(fā)現(xiàn)基于全局的算法獲取所有節(jié)點位置請求后,越靠近匯聚節(jié)點,轉(zhuǎn)發(fā)數(shù)據(jù)包的個數(shù)越多,網(wǎng)絡(luò)的負(fù)載越重,會造成網(wǎng)絡(luò)擁塞、延時甚至網(wǎng)絡(luò)的癱瘓,給網(wǎng)絡(luò)的運行帶來極大的挑戰(zhàn)。SCSN基于邊結(jié)構(gòu)的算法,每次只要求獲取凸殼頂點位置信息,減少了占絕對大數(shù)的內(nèi)部節(jié)點數(shù)據(jù)包,對匯聚節(jié)點及其鄰近的節(jié)點來說,傳輸數(shù)據(jù)包的個數(shù)大大地減少,比較發(fā)現(xiàn)基于邊結(jié)構(gòu)的算法魯棒性明顯優(yōu)于基于全局的算法。

圖10 不同跳數(shù)節(jié)點平均轉(zhuǎn)發(fā)包個數(shù)Fig.10 Average forwarding packets of different hops

4 實 驗

在這部分內(nèi)容中,我們使用Matlab-2011b仿真工具。實驗對比了凸多邊形的Steiner中心、質(zhì)心、歐幾里得和最小包圍圓4個幾何函數(shù)中心,分別對比在移動網(wǎng)絡(luò)的連續(xù)更新周期內(nèi)中心位置的偏移量來驗證SCSN使用Steiner中心作為匯聚節(jié)點是否具有高穩(wěn)定低偏心的性質(zhì)。仿真參數(shù)如表2。

表2 仿真參數(shù)Tab.2 Simulation parameters

圖11 偏移量隨時間分布圖Fig.11 Distribution of offset

圖11顯示了在移動變化的網(wǎng)絡(luò)中,實驗了4種不同函數(shù)中心在連續(xù)的20個更新周期內(nèi)匯聚節(jié)點位置的偏心量。通過圖可以發(fā)現(xiàn)最小包圍圓圓心構(gòu)成的3個點任意小的移動都會造成非常大的中心偏移。說明圓心的偏移量是非常大而且是極不穩(wěn)定的;歐幾里得中心的λ-偏心性為1，k-穩(wěn)定性為0;在正常的情況下,它的更新偏移量都小于1m,表明其偏心性非常小。但是，在T=5，10，16時刻,由于SCSN的ASASA算法檢測到凸殼有邊節(jié)點的加入或刪除,造成非常大的偏移,說明在有邊節(jié)點加入或刪除的情況下,歐幾里得中心是不穩(wěn)定的。質(zhì)心的λ-偏心性為2，k-穩(wěn)定性為1,圖中顯示其有非常好的穩(wěn)定性,但偏心量要比Steiner大。Steiner中心的k-穩(wěn)定性為0.785 4，λ-偏心性為1.115 3。圖表顯示正常情況下Steiner中心的周期更新偏移量要比質(zhì)心小,比歐幾里得要大。但是，在有邊節(jié)點加入和移除時,Steiner中心要比歐幾里得中心穩(wěn)定得多。由此可得出結(jié)論,Steiner中心相比其他凸多邊形中心作為移動傳感器網(wǎng)絡(luò)匯聚節(jié)點位置具有高穩(wěn)定和低偏心的特性。

5 結(jié) 語

[1] 呂超, 王碩, 譚民. 水下移動無線傳感器網(wǎng)絡(luò)研究綜述[J]. 控制與決策, 2009, 24(6): 801-807.

[2] JUANG P, OKI H, WANG Y, et al. Energy-efficient computing for wildlife tracking: Design tradeoffs and early experiences with ZebraNet[C]//ACM Sigplan Notices. ACM, 2002, 37(10): 96-107.

[3] CHEN F, LI R. Sink Node Placement Strategies for Wireless Sensor Networks[J]. Wireless personal communications, 2013, 68(2): 303-319.

[4] CHATZIGIANNAKIS I, KINALIS A, NIKOLETSEAS S. Efficient data propagation strategies in wireless sensor networks using a single mobile sink[J]. Computer Communications, 2008, 31(5): 896-914.

[5] LI M, LIU Y. Underground structure monitoring with wireless sensor networks[J].ACM Transations on Sensor Networks, 2009,5(2):10-15.

[6] DING M, CHEN D, XING K, et al. Localized fault-tolerant event boundary detection in sensor networks[C]//INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies, Miami:IEEE, 2005, 2: 902-913.

[7] DUROCHER S, KIRKPATRICK D. The Steiner centre of a set of points: Stability, eccentricity, and applications to mobile facility location[J]. International Journal of Computational Geometry & Applications, 2006, 16(04): 345-371.

[8] 王德江.支撐函數(shù)及其在圖像特征表示中的應(yīng)用[D].無錫:江南大學(xué),2014,7

[9] NOWAK R, MITRA U. Boundary estimation in sensor networks: Theory and methods[C]//Information Processing in Sensor Networks. Berlin Heidelberg: Springer, 2003: 80-95.

[10] KIM D, WANG W, SOHAEE N, et al. Minimum data-latency-bound k-sink placement problem in wireless sensor networks[J]. IEEE/ACM Transactions on Networking (TON), 2011, 19(5): 1344-1353.

(編 輯曹大剛)

Steiner centre as sink node position for mobile wireless sensor network

LIANG Jiu-zhen, LI Jun-fei

(School of Internet of Things,Jiangnan University, Wuxi 214122， China)

sink; mobile wireless sensor network; Steiner centre; structure-aware self-adaptive

2014-07-21

國家自然科學(xué)基金資助項目(61170121)

梁久禎，男，山東泰安人，江南大學(xué)教授，從事人工智能，機器學(xué)習(xí)，無線傳感器網(wǎng)絡(luò)。

TP301

：ADOI：10.16152/j.cnki.xdxbzr.2015-02-007