WSNs斷網(wǎng)情況下匯聚點(diǎn)選取與優(yōu)化研究*

遲百川, 曹江濤, 張 一, 耿立群

(1.遼寧石油化工大學(xué) 信息與控制工程學(xué)院，遼寧 撫順 113001； 2.空軍航空大學(xué) 飛行訓(xùn)練基地二團(tuán)，黑龍江 哈爾濱 150111)

WSNs斷網(wǎng)情況下匯聚點(diǎn)選取與優(yōu)化研究*

遲百川1, 曹江濤1, 張 一1, 耿立群2

(1.遼寧石油化工大學(xué) 信息與控制工程學(xué)院，遼寧 撫順 113001； 2.空軍航空大學(xué) 飛行訓(xùn)練基地二團(tuán)，黑龍江 哈爾濱 150111)

無人值守的無線傳感器網(wǎng)絡(luò)(WSNs)在嚴(yán)酷環(huán)境中易出現(xiàn)斷網(wǎng)情況，數(shù)據(jù)的傳輸受到限制，造成網(wǎng)絡(luò)不可用。利用移動(dòng)Sink訪問匯聚點(diǎn)(CP)收集數(shù)據(jù)是一種有效的解決方案。但現(xiàn)有的研究中沒有明確給出最佳CP的存在區(qū)域和CP 的選取對(duì)Sink節(jié)點(diǎn)移動(dòng)路徑的影響。為此，提出了最佳CP存在區(qū)域的劃分方法，并確定了該區(qū)域大小。在含有100個(gè)節(jié)點(diǎn)的WSNs上進(jìn)行仿真驗(yàn)證，結(jié)果表明:該劃分方法下Sink節(jié)點(diǎn)最優(yōu)移動(dòng)路徑的變化呈單調(diào)遞減，并最終趨于穩(wěn)定。

無線傳感器網(wǎng)絡(luò)；移動(dòng)Sink；區(qū)域劃分；最優(yōu)路徑

0 引 言

近年來，無線傳感器網(wǎng)絡(luò)(WSNs)的廣泛應(yīng)用引起了研究界和工程機(jī)構(gòu)的高度關(guān)注[1]，其最引人注目的是應(yīng)用在無人值守的嚴(yán)酷環(huán)境(如戰(zhàn)場監(jiān)測、邊境保護(hù)、太空探索等)中，避免生命危險(xiǎn)，減少工作成本，并且提供一個(gè)完全自動(dòng)化的數(shù)據(jù)收集系統(tǒng)。在WSNs的應(yīng)用中，傳感器節(jié)點(diǎn)處理能力有限，所以,期望部署的傳感器形成一個(gè)連通的網(wǎng)絡(luò)，在執(zhí)行任務(wù)時(shí)，相互協(xié)調(diào)工作，將收集的數(shù)據(jù)傳送到基站；由于傳感器節(jié)點(diǎn)是電池供電設(shè)備，它們面臨能源耗盡、設(shè)備不工作的風(fēng)險(xiǎn)；另外，惡劣環(huán)境和惡意攻擊也使節(jié)點(diǎn)容易大規(guī)模損壞；在這些情況下，網(wǎng)絡(luò)的通信鏈路斷開，數(shù)據(jù)傳輸受到限制。

為恢復(fù)網(wǎng)絡(luò)連通性，Cerpa A等人曾提出布置冗余節(jié)點(diǎn)的方案，通過提高節(jié)點(diǎn)密度來恢復(fù)WSNs連通性并延長網(wǎng)絡(luò)使用壽命[2]；Abbasi A等人提出重新布置一些節(jié)點(diǎn)的方案，其思想是運(yùn)用DARA算法來恢復(fù)WSNs連通性[3]。雖都解決了WSNs連通性問題，但卻不適合極端環(huán)境下節(jié)點(diǎn)的大規(guī)模損壞。因此，用剩余節(jié)點(diǎn)建立WSNs各集群的連通性顯得至關(guān)重要。

在WSNs中引入移動(dòng)Sink[4]可有效的提升網(wǎng)絡(luò)性能，包括降低能量消耗[5]、延長網(wǎng)絡(luò)生存時(shí)間[6]等。因此，本文采用移動(dòng)數(shù)據(jù)收集器(mobile data collector, MDC)作為移動(dòng)Sink來恢復(fù)斷開WSNs的連通性。

匯聚點(diǎn)(CP)的選取決定MDC的移動(dòng)路徑。所以，集群中CP可停留的位置不同，MDC的移動(dòng)路徑也會(huì)隨之發(fā)生相應(yīng)的變化?，F(xiàn)有的研究結(jié)果中，如文獻(xiàn)[7]，將各集群的中心點(diǎn)與選取的單一代表點(diǎn)(representative point, RP)連線，其與傳輸半徑的交點(diǎn)作為單一CP，再進(jìn)行數(shù)據(jù)收集。而文獻(xiàn)[8]對(duì)其進(jìn)行了改進(jìn)，首先采用CURE算法[9]將剩余可用節(jié)點(diǎn)劃分為集群，然后在每個(gè)集群中選取2個(gè)CP，再對(duì)其進(jìn)行路徑規(guī)劃，從而縮短了MDC的移動(dòng)距離，減少了能量消耗和網(wǎng)絡(luò)延遲。雖然都解決了嚴(yán)酷環(huán)境中的斷網(wǎng)問題，但沒有考慮CP的選取對(duì)整個(gè)移動(dòng)路徑的影響，形成最優(yōu)路徑時(shí)最佳CP的存在區(qū)域。

為此，本文從以上2個(gè)問題入手，在解決極端環(huán)境中WSNs不可用的基礎(chǔ)上，提出了最佳CP存在區(qū)域的劃分方法，分析了集群中CP的選取,即CP在集群中可停留的位置對(duì)整個(gè)移動(dòng)路徑的影響。

1 網(wǎng)絡(luò)模型與連通性

首先，定義一個(gè)由N個(gè)靜態(tài)傳感器節(jié)點(diǎn)和一個(gè)MDC組成的WSNs。通過聚類算法將N個(gè)靜態(tài)節(jié)點(diǎn)大致分為n個(gè)集群，集群內(nèi)部節(jié)點(diǎn)通過多跳的方式相互通信，集群間通信受阻。每個(gè)傳感器節(jié)點(diǎn)可以通過GPS或其它定位算法知道各自的位置信息，并且MDC的移動(dòng)方式可控。

設(shè)MDC可以從任意集群出發(fā)收集數(shù)據(jù)，并最終回到始發(fā)集群，使得MDC的移動(dòng)路徑形成一個(gè)回路。用np和nm來表示CP節(jié)點(diǎn)的數(shù)量和成員節(jié)點(diǎn)的數(shù)量,即

N=nP+nm.

(1)

將剩余可用節(jié)點(diǎn)進(jìn)行聚類可有效的減少M(fèi)DC能量的消耗。本文利用模糊C均值(fuzzy C-means, FCM)聚類算法[10]首先將隨機(jī)分布的節(jié)點(diǎn)劃分為集群，并且確保集群內(nèi)部相互通信，然后通過該算法確定集群中心點(diǎn)，為CP的選取做準(zhǔn)備。

假設(shè)所有傳感器具有相同的傳輸范圍“CR”，為尋找CP在集群中可能停留的位置，做如下定義：

定義一：通過FCM聚類算法形成的n個(gè)集群S={S1,S2,S3,…,Sn-1,Sn}，各集群的中心點(diǎn)集合C={C1,C2,C3,…,Cn-1,Cn}，令O為中心點(diǎn)集C的中心點(diǎn)。

定義二：令rb為RP，一個(gè)集群中存在多個(gè)RP，且滿足rb與O之間的歐氏距離比該集群中其余點(diǎn)與O之間的歐氏距離短。

然而，上述尋找CP的方法只適合各集群所在位置的連線呈凸邊形的情況。如圖1 所示，以4個(gè)集群S={S1,S2,S3,S4},每個(gè)集群選取2個(gè)CP為例。

圖1 各集群位置呈凸邊形時(shí)CP的選取方式

當(dāng)為凹邊形時(shí)，需要找出具有凹點(diǎn)的集群，如圖2所示。運(yùn)用FCM算法確定該集群的中心點(diǎn)M,然后連接其余集群的CP。從M向與之最近的邊作垂線，令垂線與RP傳輸范圍“CR”的交點(diǎn)為該集群CP的可停留位置(具有凹點(diǎn)的集群取一個(gè)CP)。

圖2 各集群位置呈凹邊形時(shí)CP的選取方式

實(shí)際上，各集群的位置不僅僅呈現(xiàn)凸邊形或凹邊形，也可能出現(xiàn)更為復(fù)雜的網(wǎng)狀結(jié)構(gòu)，但網(wǎng)狀結(jié)構(gòu)可分解為若干個(gè)凸邊形和凹邊形的情況。為此，本文只專注于集群位置呈凸邊形和凹邊形的情況。

部署MDC的主要目的是傳輸數(shù)據(jù)，通過設(shè)置MDC的移動(dòng)路徑來達(dá)到這個(gè)目的。假設(shè)MDC的移動(dòng)路徑“T”是一個(gè)最短循環(huán)，每個(gè)集群至少包含一個(gè)CP。尋找“T”路徑等同于旅行商問題，被認(rèn)為是一個(gè)NP-Hard問題[11]。本文采用Dijkstra算法[12]，該算法用于計(jì)算一個(gè)源節(jié)點(diǎn)到其它所有節(jié)點(diǎn)的最短代價(jià)路徑。因此，本文的最短路徑T可描述為

(2)

1)分別求最短路徑T1,T2,…,Tm;

2)T1,T2,…,Tm之間進(jìn)行比較，選出最優(yōu)路徑

minroute=min{T1,T2,…,Tm}.

(3)

圖3所示為全局最優(yōu)路徑模擬圖。圖中，虛線框代表集群。

圖3 全局最優(yōu)路徑模擬圖

同樣以4個(gè)集群，如圖4所示，當(dāng)各集群位置呈凸邊形時(shí)，其最短路徑T可描述為

(4)

圖4 各集群位置呈凸邊形時(shí)最優(yōu)路徑的形成過程

圖5 各集群位置呈凹邊形時(shí)最優(yōu)路徑的形成過程

2 區(qū)域劃分

為確定最佳CP的可能存在區(qū)域，還需要做如下的定義：

定義四：令lxy為以x為圓心，|xy|為半徑的圓弧。

定義五：⊙x定義為以x為圓心的圓；⊙xy定義為以x為圓心，|xy|為半徑的圓。

由于集群的位置不同，其最佳CP的存在區(qū)域也會(huì)隨之發(fā)生變化。為方便區(qū)域劃分，假設(shè)各集群形狀呈圓形，且傳感器節(jié)點(diǎn)的傳輸范圍被認(rèn)為是一個(gè)點(diǎn)，分以下兩種情況進(jìn)行區(qū)域劃分:

1)當(dāng)各集群位置呈凸邊形時(shí)

如圖6所示，圖中陰影部分即為最佳CP的選取區(qū)域。

圖6 凸邊形時(shí)最佳CP存在區(qū)域的劃分

SAi=

(5)

2)當(dāng)各集群位置呈凹邊形時(shí)

這種情況下，首先需要確定各個(gè)集群的CP。區(qū)域的劃分方法及原理與凸邊形的情況一致，這里不在進(jìn)行贅述。圖7中陰影部分即為凹邊形時(shí)最佳CP的可能存在區(qū)域。

圖7 凹邊形時(shí)最佳CP存在區(qū)域的劃分

3 仿真測試與結(jié)果

本文運(yùn)用Matlab_R2012a作為仿真平臺(tái)進(jìn)行結(jié)果測試。在100m×100m的范圍內(nèi)隨機(jī)布置100個(gè)節(jié)點(diǎn)，運(yùn)用FCM聚類算法將其聚類形成3～8個(gè)集群，并且保證其內(nèi)部正常通信。定義傳感器和MDC的傳輸范圍為10m。

在已形成指定聚類數(shù)目的前提下，將每個(gè)集群中取2個(gè)CP(CTCP)的方式與IDM-KMDC[8]進(jìn)行比較。IDM-KMDC的主要思想是將節(jié)點(diǎn)形成指定數(shù)目集群后，在每個(gè)集群中選擇一個(gè)CP，然后運(yùn)用最小生成樹算法[13]進(jìn)行路徑規(guī)劃，以達(dá)到MDC移動(dòng)路徑的最小化。通過以下2個(gè)性能指標(biāo)進(jìn)行比較：

1)移動(dòng)總長度(totaltourlength,TTL)：因?yàn)橐苿?dòng)能減少M(fèi)DC的使用壽命，所以,最小化MDC的移動(dòng)路徑是該方案的一個(gè)設(shè)計(jì)目標(biāo)。

2)最大移動(dòng)長度(maximumtourlength,MTL)：反映MDC完成一個(gè)最短循環(huán)“T”所移動(dòng)的最大長度“L”。如果“L”長度過大，將會(huì)導(dǎo)致數(shù)據(jù)收集的延遲增加，所以，需要最小化“L”。

如圖8所示，為兩種方案下MDC的移動(dòng)總長度，從圖中可知，CTCP方案優(yōu)于IDM-KMDC。在MDC移動(dòng)速度確定的情況下，能更好地恢復(fù)網(wǎng)絡(luò)的連通性。圖9為兩種方案下MDC的MTL，可以看出：CTCP在數(shù)據(jù)收集的延遲上更低，網(wǎng)絡(luò)的運(yùn)行速度更快。

圖8 不同方案下TTL的比較

圖9 兩種方案下的MTL

通過兩種方案的比較，可以得知，在已形成指定聚類數(shù)目的前提下，CTCP能更快的恢復(fù)WSNs的連通性，更適合極端環(huán)境中無人值守的WSNs網(wǎng)絡(luò)節(jié)點(diǎn)大規(guī)模損壞的情況。證明了集群中選擇2個(gè)CP時(shí)，其形成的路徑優(yōu)于單CP的情況。

表1為仿真測試所得到數(shù)據(jù)。當(dāng)每個(gè)集群取多個(gè)CP時(shí)，MDC的TTL隨著集群中CP數(shù)量的單調(diào)增加而單調(diào)減少，并最終穩(wěn)定,即，由于集群中CP數(shù)量的增加，隱藏的較優(yōu)路徑逐漸被發(fā)現(xiàn)，直到形成最優(yōu)路徑，即MDC的TTL達(dá)到穩(wěn)定。同時(shí)，可根據(jù)具體的集群數(shù)目選擇合適的CP進(jìn)行路徑規(guī)劃，可以避免不必要的計(jì)算量。其仿真圖如圖10所示。

表1 不同集群數(shù)目下對(duì)應(yīng)不同CP的TTL

圖10 TTL的變化規(guī)律

4 結(jié)束語

本文利用MDC作為移動(dòng)Sink來解決嚴(yán)酷環(huán)境中無人值守的WSNs的斷網(wǎng)問題。提出了最佳CP可能存在區(qū)域的劃分方法，并在此基礎(chǔ)上證明了CP停留在集群的不同位置，對(duì)整個(gè)移動(dòng)路徑的影響。通過仿真測試，驗(yàn)證了所得結(jié)論的正確性。

[1] Estrin D,Girod L,Pottie G,et al. Instrument the world with wireless sensor networks[C]∥Proc of the Int’l Conf on Acoustics,Speech,and Signal Processing,Prague,Czech Republic,2001:2033-2036.

[2] Cerpa A,Estrin D. ASCENT:Adaptive self-configuring sensor networks topologies[C]∥Proc of the INFOCOM’02,New York,NY,2004::272-285.

[3] Abbasi A ,Akkaya K,Younis M. A distributed connectivity restoration algorithm in wireless sensor and actor networks[C]∥Proc of IEEE LCN’07,Dublin,Ireland,2007:496-503.

[4] 梁俊斌,鄧雨榮,郭麗娟,等. 無線傳感網(wǎng)中移動(dòng)數(shù)據(jù)收集研究綜述[J]. 計(jì)算機(jī)應(yīng)用與軟件,2013,30(5):25-28.

[5] Jain S,Shah R C,Brunette W,et al. Exploiting mobility for energy efficient data collection in wireless sensor networks[J]. Mobile Networks & Applications,2006,11(3):327-339.

[6] Luo J,Hubaux J P. Joint mobility and routing for lifetime elongation in wireless sensor networks[C]∥Proc of the IEEE Int’l Conf on Computer Communications,Hingham,USA,2005:1735-1746.

[7] Senel F,Younis M. Optimized interconnection of disjoint wireless sensor network segments using K mobile data collectors[C]∥Proc of the IEEE Int’l Conf on Comm (ICC’12),Ottawa,Canada,2012:492-496.

[8] Kalyanasundaram B,Younis M. Using mobile data collectors to federate clusters of disjoint sensor network segments[C]∥Proc of the IEEE Int’l Conf on Comm (ICC’13),Maryland,American,2013:1496-1500.

[9] 趙 妍,趙學(xué)民. 基于 CURE 的用戶聚類算法研究[J]. 計(jì)算機(jī)工程與應(yīng)用,2012,48(11):97-101.

[10] 李 雷,羅紅旗,丁亞麗. 一種改進(jìn)的模糊 C 均值聚類算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2009,19(12):71-73.

[11] 郭靖楊. 旅行商問題概述[J]. 大眾科技，2006 (8):229-230.

[12] Deng Y,Chen Y,Zhang Y,et al. Fuzzy dijkstra algorithm for shortest path problem under uncertain environment[J]. Applied Soft Computing,2012,12(3):1231-1237.

[13] 徐建軍,沙力妮,張 艷,等. 一種新的最小生成樹算法[J]. 電力系統(tǒng)保護(hù)與控制,2011,39(14):107-112.

Research on selection and optimization of collection points

in WSNs under condition of broken network*CHI Bai-chuan1, CAO Jiang-tao1, ZHANG Yi1,GENG Li-qun2

(1.School of Information and Control Engineering, Liaoning Shihua University, Fushun 113001, China； 2.Training Base Group 2, Aviation University of Air Force,Harbin 150111, China)

Wireless sensor networks (WSNs) that operates unattended in extreme environmental conditions may off the Internet and data transmission is restricted, which make WSNs unavailable. Use mobile sink visit collection points(CP) and collect datas is an effective solution. However, the existing studies do not give solution of how to select the optimum CP and its impact on moving routes are not given. So, present a partition method to find the area where optimal CP placed and ascertain that area size. Simulation test on WSNs that contains 100 nodes is carried out and its results indicate variation of the optimal moving route of sink node is monotone decreasing until stable by this partition method.

wireless sensor networks(WSNs); mobile sink; regional division; optimal path

10.13873/J.1000—9787(2015)04—0034—04

2014—09—11

遼寧省自然科學(xué)基金資助項(xiàng)目(2013020024)；國家自然科學(xué)基金資助項(xiàng)目(61203021)

TP 393

A

1000—9787(2015)04—0034—04

遲百川(1990-)，男，滿族，遼寧本溪人，碩士研究生，研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)。