WSNs斷網情況下匯聚點選取與優化研究*

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

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

WSNs斷網情況下匯聚點選取與優化研究*

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

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

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

無線傳感器網絡；移動Sink；區域劃分；最優路徑

0 引 言

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

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

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

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

為此，本文從以上2個問題入手，在解決極端環境中WSNs不可用的基礎上，提出了最佳CP存在區域的劃分方法，分析了集群中CP的選取,即CP在集群中可停留的位置對整個移動路徑的影響。

1 網絡模型與連通性

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

設MDC可以從任意集群出發收集數據，并最終回到始發集群，使得MDC的移動路徑形成一個回路。用np和nm來表示CP節點的數量和成員節點的數量,即

N=nP+nm.

(1)

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

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

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

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

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

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

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

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

實際上，各集群的位置不僅僅呈現凸邊形或凹邊形，也可能出現更為復雜的網狀結構，但網狀結構可分解為若干個凸邊形和凹邊形的情況。為此，本文只專注于集群位置呈凸邊形和凹邊形的情況。

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

(2)

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

2)T1,T2,…,Tm之間進行比較，選出最優路徑

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

(3)

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

圖3 全局最優路徑模擬圖

同樣以4個集群，如圖4所示，當各集群位置呈凸邊形時，其最短路徑T可描述為

(4)

圖4 各集群位置呈凸邊形時最優路徑的形成過程

圖5 各集群位置呈凹邊形時最優路徑的形成過程

2 區域劃分

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

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

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

由于集群的位置不同，其最佳CP的存在區域也會隨之發生變化。為方便區域劃分，假設各集群形狀呈圓形，且傳感器節點的傳輸范圍被認為是一個點，分以下兩種情況進行區域劃分:

1)當各集群位置呈凸邊形時

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

圖6 凸邊形時最佳CP存在區域的劃分

SAi=

(5)

2)當各集群位置呈凹邊形時

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

圖7 凹邊形時最佳CP存在區域的劃分

3 仿真測試與結果

本文運用Matlab_R2012a作為仿真平臺進行結果測試。在100m×100m的范圍內隨機布置100個節點，運用FCM聚類算法將其聚類形成3～8個集群，并且保證其內部正常通信。定義傳感器和MDC的傳輸范圍為10m。

在已形成指定聚類數目的前提下，將每個集群中取2個CP(CTCP)的方式與IDM-KMDC[8]進行比較。IDM-KMDC的主要思想是將節點形成指定數目集群后，在每個集群中選擇一個CP，然后運用最小生成樹算法[13]進行路徑規劃，以達到MDC移動路徑的最小化。通過以下2個性能指標進行比較：

1)移動總長度(totaltourlength,TTL)：因為移動能減少MDC的使用壽命，所以,最小化MDC的移動路徑是該方案的一個設計目標。

2)最大移動長度(maximumtourlength,MTL)：反映MDC完成一個最短循環“T”所移動的最大長度“L”。如果“L”長度過大，將會導致數據收集的延遲增加，所以，需要最小化“L”。

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

圖8 不同方案下TTL的比較

圖9 兩種方案下的MTL

通過兩種方案的比較，可以得知，在已形成指定聚類數目的前提下，CTCP能更快的恢復WSNs的連通性，更適合極端環境中無人值守的WSNs網絡節點大規模損壞的情況。證明了集群中選擇2個CP時，其形成的路徑優于單CP的情況。

表1為仿真測試所得到數據。當每個集群取多個CP時，MDC的TTL隨著集群中CP數量的單調增加而單調減少，并最終穩定,即，由于集群中CP數量的增加，隱藏的較優路徑逐漸被發現，直到形成最優路徑，即MDC的TTL達到穩定。同時，可根據具體的集群數目選擇合適的CP進行路徑規劃，可以避免不必要的計算量。其仿真圖如圖10所示。

表1 不同集群數目下對應不同CP的TTL

圖10 TTL的變化規律

4 結束語

本文利用MDC作為移動Sink來解決嚴酷環境中無人值守的WSNs的斷網問題。提出了最佳CP可能存在區域的劃分方法，并在此基礎上證明了CP停留在集群的不同位置，對整個移動路徑的影響。通過仿真測試，驗證了所得結論的正確性。

[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] 梁俊斌,鄧雨榮,郭麗娟,等. 無線傳感網中移動數據收集研究綜述[J]. 計算機應用與軟件,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] 趙 妍,趙學民. 基于 CURE 的用戶聚類算法研究[J]. 計算機工程與應用,2012,48(11):97-101.

[10] 李 雷,羅紅旗,丁亞麗. 一種改進的模糊 C 均值聚類算法[J].計算機技術與發展,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]. 電力系統保護與控制,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

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

TP 393

A

1000—9787(2015)04—0034—04

遲百川(1990-)，男，滿族，遼寧本溪人，碩士研究生，研究方向為無線傳感器網絡。