基于移動協(xié)助方式的網(wǎng)絡(luò)連通性恢復(fù)技術(shù)研究

遲百川，曹江濤，張 一，趙 婧，牛曉棠，邵鵬飛

（遼寧石油化工大學(xué) 信息與控制工程學(xué)院，遼寧 撫順 113001）

0 引 言

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

為恢復(fù)網(wǎng)絡(luò)連通性，Cerpa等曾提出布置冗余節(jié)點的方案，其思想是采用斜坡算法，通過提高節(jié)點密度，來恢復(fù)無線傳感器網(wǎng)絡(luò)連通性并延長網(wǎng)絡(luò)使用壽命［2］；Abbasi等提出重新布置一些節(jié)點的方案，其思想是運用DARA 算法來恢復(fù)無線傳感器網(wǎng)絡(luò)連通性［3］.這兩種方案雖都能解決無線傳感器網(wǎng)絡(luò)連通性的問題，但卻不適用于極端環(huán)境下節(jié)點的大規(guī)模損壞.在這種情況下，用剩余節(jié)點建立無線傳感器網(wǎng)絡(luò)各集群的連通性顯得至關(guān)重要.

不同于固定中繼節(jié)點的方式來建立靜態(tài)通信鏈路［4］，本文運用移動數(shù)據(jù)收集器（mobile data collector，MDC）作為移動中繼節(jié)點建立間歇性的通信鏈路，以恢復(fù)各集群間的連接.當移動數(shù)據(jù)收集器移動到傳感器節(jié)點的傳輸范圍內(nèi)，將收集數(shù)據(jù)，然后沿著優(yōu)化的路徑移動并收集數(shù)據(jù)，最后將數(shù)據(jù)送往基站，以恢復(fù)網(wǎng)絡(luò)的連通性.

1 問題描述

無人值守的無線傳感器網(wǎng)絡(luò)在嚴酷環(huán)境中，傳感器節(jié)點易大規(guī)模損壞，網(wǎng)絡(luò)被分割成多個不連通的子網(wǎng)絡(luò)，節(jié)點數(shù)據(jù)無法傳輸給Sink節(jié)點，造成無線傳感器網(wǎng)絡(luò)不可用.而在無線傳感器網(wǎng)絡(luò)中引入移動元素可以有效地提升網(wǎng)絡(luò)性能，包括降低能量消耗［5］、延長網(wǎng)絡(luò)生存時間［6］等.所以本文采用移動數(shù)據(jù)收集器作為移動元素，其在能量存儲和通信能力方面是一個很強大的設(shè)備［7］，通過它移動和攜帶各節(jié)點的數(shù)據(jù)以建立各集群間的通信鏈路，進而恢復(fù)網(wǎng)絡(luò)連通性.

在無人值守的復(fù)雜環(huán)境下，移動數(shù)據(jù)收集器應(yīng)通過收集各傳感器節(jié)點數(shù)據(jù)，并以最小的路徑移動來恢復(fù)網(wǎng)絡(luò)的連通性，從而最小化緩沖要求和減少延遲.為解決上述問題，本文主要采取以下3個步驟：

（1）將剩余可用節(jié)點通過FCM 聚類算法大致分為K個集群，確保集群內(nèi)部節(jié)點間相互通信，并確定集群中心點.

（2）選取收集點.在數(shù)據(jù)收集環(huán)節(jié)中，最重要的就是最佳收集點（collection point，CP）的選取.因此將移動數(shù)據(jù)收集器送到集群的位置偵查環(huán)境，并進行數(shù)據(jù)收集，當移動數(shù)據(jù)收集器移動到收集點處，就可獲知該集群的信息.

（3）優(yōu)化路徑.尋找移動數(shù)據(jù)收集器移動的最短路徑等同于旅行商問題，被認為是一個NPHard問題.本文采用Dijkstra算法［8］優(yōu)化移動數(shù)據(jù)收集器的移動路徑來解決該問題.

2 收集點的選取

當移動數(shù)據(jù)收集器移動到一個傳感器的通信范圍內(nèi)時，它將收集數(shù)據(jù).因此，收集點的選取變得非常重要.

模糊C均值（fuzzyC－Means，F(xiàn)CM）聚類算法［9］是一種迭代優(yōu)化算法，其基本思想是將一組分布未知的數(shù)據(jù)進行分類，尋找隱藏在數(shù)據(jù)中的結(jié)構(gòu)，按照某種相似程度的度量，盡可能地使具有相同性質(zhì)的數(shù)據(jù)歸于同一類［10］，適用于本文所研究的內(nèi)容.因此，本文利用FCM 聚類算法首先將隨機分布的節(jié)點劃分為集群，并且確保集群內(nèi)部相互通信，然后通過該算法確定集群中心點，為收集點的選取做準備.該算法可描述為

式中：U為輸入空間X一個模糊C劃分，V為聚類中心點集合，c為數(shù)據(jù)樣本，n為形成聚類的個數(shù)，為加權(quán)指數(shù)［11］.

假設(shè)所有傳感器具有相同的傳輸范圍CR，做如下的定義：

定義1 通過FCM 聚類算法形成的K個集群S＝｛S1，S2，S3，…，SK－1，SK｝，各集群的中心點 集C＝ ｛C1，C2，C3，…，CK－1，CK｝，令Center1，2，…，K為中心點集C的中心點.

定義2 令rb為代表點（representative point，RP），滿足rb與Center1，2，…，K之間的歐式距離最短，即mindist（rb，Center1，2，…，K）.

定義3PKb定義為集群S的收集點，滿足dist（PKb，rb）≤CR.

然而，上述尋找收集點的方法只適合各集群所在位置的連線為凸形的情況.如圖1所示，以4個集群S＝｛S1，S2，S3，S4｝為例，通過FCM 聚類得 到 的 中 心 點 集C＝ ｛C1，C2，C3，C4｝，Center1，2，3，4為聚類中心點集C的中心 點，在集群S中選出與Center1，2，3，4距離最短和次短的兩個點作為代表點，然后分別與Center1，2，3，4連線，其與代表點傳輸范圍CR的交點即被選擇為收集點.

圖1 各集群位置呈凸形時收集點的選取Fig.1 The selection of CP when clusters present convex

當各集群所在位置的連線為凹形時，需要找出具有凹點的集群，運用FCM 聚類算法確定該集群中心點C4，如圖2所示，然后連接其他集群的收集點（此收集點的選取與凸形選取方式一致）.從C4向與之最近的邊作垂線，垂足為Q，則垂線與代表點傳輸范圍CR的交點P41即為該集群的收集點.

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

圖2 各集群位置呈凹形時收集點的選取Fig.2 The selection of CP when clusters present concave

3 最小化移動數(shù)據(jù)收集器移動路徑

部署移動數(shù)據(jù)收集器的主要目的是傳輸數(shù)據(jù)，可通過設(shè)置移動數(shù)據(jù)收集器的移動路徑來達到這個目的.假設(shè)移動數(shù)據(jù)收集器的移動路徑T是一個最短循環(huán)，每個集群至少包含一個收集點.尋找T路徑等同于旅行商問題，被認為是一個NP－Hard問題.由于移動數(shù)據(jù)收集器的移動路徑可能包含一個集群中的兩個收集點，需要挑選出每個集群的單收集點對路徑進一步優(yōu)化，來最小化移動路徑.

為處理該問題，本文采用Dijkstra算法，該算法用于計算一個源節(jié)點到所有其他節(jié)點的最短代價路徑.其基本思想是設(shè)置頂點集合S并不斷地作貪心算法來擴充這個集合，直到擴展到終點為止，尋找最短路徑的最優(yōu)解，符合本文解決該問題的基本思路.

然而針對本文的具體問題，需構(gòu)建選擇最優(yōu)路徑模擬圖，并且運用兩次Dijkstra算法.其最短路徑T可描述為

式（2）中上標表示收集點編號，下標代表集群編號，比如：CP｛1，2｝1表示P11、P12，即集群S1中的兩個收集點.其最優(yōu)路徑選擇分為以下3個步驟進行：

（1）求最短路徑T1

（2）求最短路徑T2

（3）T1與T2比較，選出最優(yōu)路徑Minroute

如圖3所示，虛線框代表集群.首先以CP11（S1中P11點）為起始點，尋找到CP｛1，2｝4（S4中P41或P42點）的最短路徑T1；然后再以CP21為起始點，尋找到CP｛1，2｝4的最短路徑T2，比較T1、T2，選出最優(yōu)路徑Minroute.

圖3 選擇最優(yōu)路徑模擬圖Fig.3 The simulation diagram of global optimal path selection

由上可知，由于集群所處位置的差異，收集點的選擇方式也會不同，使得移動數(shù)據(jù)收集器的移動路徑隨之發(fā)生變化.本文從以下兩種情況進行考慮：

（1）各集群所在位置連線為凸形

同樣以4個集群為例.首先從集群S＝｛S1，S2，S3，S4｝中分別選取兩個收集點：CP｛1，2｝1，CP｛1，2｝2，CP｛1，2｝3，CP｛1，2｝4，并對其進行路徑規(guī)劃，如圖4所示.

挑選出單一收集點對移動數(shù)據(jù)收集器的移動路徑進一步優(yōu)化，選出最優(yōu)路徑Minroute，此時：

如圖5所示，虛線即為移動數(shù)據(jù)收集器的最優(yōu)移動路徑，所經(jīng)過的點即為挑選出的單一收集點.

圖4 兩個收集點形成的最短移動路徑Fig.4 The shortest path formed by two CPs

圖5 運用Dijkstra算法形成的單收集點移動路徑Fig.5 Formation of single CP′s mobile path by using the Dijkstra algorithm

（2）各集群所在位置連線為凹形

這種情況比較復(fù)雜，需要考慮到具有凹點的集群.同樣以4個集群為例，首先確定各集群的收集點，然后再對其進行路徑優(yōu)化，尋找最優(yōu)路徑Minroute.此時：

其形成過程如圖6所示，虛線即為移動數(shù)據(jù)收集器的最優(yōu)移動路徑，所經(jīng)過的點即為挑選出的單一收集點.

圖6 各集群位置呈凹形時最優(yōu)路徑的形成過程Fig.6 The formation process of optimal path when clusters present concave

4 仿真測試及結(jié)果

本文運用Matlab2012a作為仿真平臺進行結(jié)果測試.在1 m×1 m 的范圍內(nèi)隨機布置100個節(jié)點，運用FCM 聚類算法將其聚類形成3～6個集群，并且保證其內(nèi)部正常通信.定義傳感器和移動數(shù)據(jù)收集器的傳輸范圍為0.1 m.以下是仿真中性能指標：

（1）移動總長度（total tour length，TTL）：因為移動能減少移動數(shù)據(jù)收集器的使用壽命，所以最小化移動數(shù)據(jù)收集器的移動路徑是該方案的一個設(shè)計目標.

（2）最大移動長度（maximum tour length，MTL）：反映移動數(shù)據(jù)收集器完成一個最短循環(huán)T所移動的最大長度L.如果L長度過大，將會導(dǎo)致數(shù)據(jù)收集的延遲增加，所以需要最小化L.

在已形成指定聚類數(shù)目的前提下，將本文方案與IDM－KMDC［12］進行比較.IDM－KMDC的主要思想是將節(jié)點形成指定數(shù)目集群后，在每個集群中選擇一個收集點，然后運用最小生成樹算法［13］進行路徑規(guī)劃，以達到移動數(shù)據(jù)收集器移動路徑的最小化.

從表1中的數(shù)據(jù)可知，本文方案優(yōu)于IDMKMDC，移動總長度較IDM－KMDC 平均減少了8.15%，即在移動數(shù)據(jù)收集器移動速度確定的情況下，能更好地恢復(fù)網(wǎng)絡(luò)的連通性，并且當傳感器節(jié)點形成6 個集群時，本文方案明顯優(yōu)于IDMKMDC.圖7為其仿真圖像.

表1 兩種方案下移動總長度的比較Tab.1 The comparison of total tour length for two schemes

圖7 兩種方案下的移動總長度Fig.7 Total tour length for two schemes

表2為兩種方案下最大移動長度的比較.由該表可知，本文方案的最大移動長度較IDMKMDC平均減少了17.20%，說明本文方案在數(shù)據(jù)收集的延遲上低于IDM－KMDC，網(wǎng)絡(luò)運行的速度更快.其仿真圖像如圖8所示.

表2 兩種方案下最大移動長度的比較Tab.2 The comparison of maximum tour length for two schemes

通過表1、2的實驗結(jié)果可以看出，在已形成指定聚類數(shù)目的前提下，與IDM－KMDC 方案相比，本文方案能更快地恢復(fù)無線傳感器網(wǎng)絡(luò)的連通性，更適合極端環(huán)境中無人值守的無線傳感器網(wǎng)絡(luò)節(jié)點大規(guī)模損壞的情況.

圖8 兩種方案下的最大移動長度Fig.8 Maximum tour length for two schemes

5 結(jié) 語

本文針對嚴酷環(huán)境中，無線傳感器網(wǎng)絡(luò)的大規(guī)模損壞，許多節(jié)點同時失效，造成網(wǎng)絡(luò)通信中斷的問題，提出了一種運用移動協(xié)助的方式來恢復(fù)網(wǎng)絡(luò)連通性的方案.首先將剩余可用的節(jié)點進行聚類，然后尋找數(shù)據(jù)收集點，進行路徑優(yōu)化，以確保移動數(shù)據(jù)收集器移動路徑的最小化，從而最小化緩沖要求，減少延遲.經(jīng)過仿真測試，證明了該方案的可行性，并最小化了移動路徑.建立實驗系統(tǒng)模型，并將其運用到工業(yè)生產(chǎn)中，將是下一步研究的內(nèi)容.

［1］ Estrin D，Girod L，Pottie G，etal.Instrumenting the world with wireless sensor networks ［J］.ICASSP，IEEE International Conference on Acoustics，Speech and Signal Processing －Proceedings，2001，4：2033－2036.

［2］ Cerpa A，Estrin D.ASCENT：Adaptive selfconfiguring sensor networks topologies［J］.IEEE Transactions on Mobile Computing，2004，3（3）：272－285.

［3］ Abbasi A A，Akkaya K，Younis M.A distributed connectivity restoration algorithm in wireless sensor and actor networks［C］／／Proceedings of the 32nd IEEE Conference on Local Computer Networks，LCN 2007.Los Alamitos：IEEE Computer Society，2007：496－503.

［4］ 傅菊平，王東方，齊小剛.放置中繼節(jié)點解決無線傳感器網(wǎng)絡(luò)能量空洞問題［J］.微型機與應(yīng)用，2011，30（2）：72－74.FU Ju－ping，WANG Dong－fang，QI Xiao－gang.Using relay－nodes to solve energy hole in wireless sensor networks ［J］.Microcomputer ＆ Its Application，2011，30（2）：72－74.（in Chinese）

［5］ Jain S，Shah R C，Brunette W，etal.Exploiting mobility for energy efficient data collection in wireless sensor networks［J］.Mobile Networks and Applications，2006，11（3）：327－339.

［6］ Luo J，Hubaux J P.Joint mobility and routing for lifetime elongation in wireless sensor networks［J］.Proceedings－IEEE INFOCOM，2005，3：1735－1746.

［7］ Kalyanasundaram B，Younis M.Using mobile data collectors to federate clusters of disjoint sensor network segments［C］／／2013IEEE International Conference on Communications，ICC 2013.Piscataway：IEEE，2013：1496－1500.

［8］ 蔚 潔，楊懷雷，成汝震.基于Dijkstra算法的最優(yōu)路徑搜索方法［J］.河北師范大學(xué)學(xué)報：自然科學(xué)版，2008，32（5）：590－593，598.YU Jie，YANG Huai－lei，CHENG Ru－zhen.Optimal path searching method based on Dijkstra algorithm［J］.Journal of Hebei Normal University：Natural Science Edition，2008，32（5）：590－593，598.（in Chinese）

［9］ 高新波.模糊聚類分析及其應(yīng)用［M］.西安：西安電子科技大學(xué)出版社，2004.GAO Xin－bo.Fuzzy Cluster Analysis and Its Application［M］.Xi′an：Xidian University Press，2004.（in Chinese）

［10］ 朱 林，王士同，鄧趙紅.改進模糊劃分的FCM 聚類算法的一般化研究［J］.計算機研究與發(fā)展，2009，46（5）：814－822.ZHU Lin，WANG Shi－tong，DENG Zhao－h(huán)ong.Research on generalized fuzzyC－means clustering algorithm with improved fuzzy partitions ［J］.Journal of Computer Research ＆ Development，2009，46（5）：814－822.（in Chinese）

［11］ 姜 倫，丁華福.關(guān)于模糊C－均值（FCM）聚類算法的改進［J］.計算機與數(shù)字工程，2010，38（2）：4－6.JIANG Lun，DING Hua－fu.Improvement of the fuzzyC－means clustering algorithm ［J］.Computer＆ Digital Engineering，2010，38（2）：4－6.（in Chinese）

［12］ Senel F，Younis M.Optimized interconnection of disjoint wireless sensor network segments usingKmobile data collectors ［C］ ／／ 2012 IEEE International Conference on Communications，ICC 2012.Piscataway：IEEE，2012：492－496.

［13］ 王化宇.最小生成樹算法及其應(yīng)用［J］.內(nèi)蒙古科技與經(jīng)濟，2011（6）：72－73.WANG Hua－yu.Minimum spanning tree algorithm and its application ［J］.Inner Mongolia Science Technology ＆ Economy，2011（6）：72－73.（in Chinese）