無線傳感器網絡中基于移動sink最優路徑的數據收集策略

【信息科學與控制工程】

無線傳感器網絡中基于移動sink最優路徑的數據收集策略

劉林鋒a，郭平b，趙娟a，李寧a

(后勤工程學院a.后勤信息系；b.訓練部，重慶401311)

摘要：針對無線傳感器網絡中節點能量受限，傳統的數據收集方法需要節點將數據經過多跳轉發出去，部分節點由于轉發其他節點的數據而使能量快速耗盡。提出了一種在無線傳感器網絡中引入移動sink，并讓其沿著規劃好的最優路徑移動從而進行數據收集的策略DCST。DCST利用蟻群算法尋找出連接所有簇頭的最優路徑，使移動sink沿著此路徑移動并進行數據收集。仿真結果表明，相比傳統的Leach算法，DCST能更好地擴張網絡的循環輪數，節省整個網絡的能耗。

關鍵詞：最優路徑；移動sink；無線傳感器網絡；數據收集

收稿日期：2014-08-20

作者簡介：劉林鋒(1989—)，男，碩士研究生，主要從事無線傳感器網絡研究。

doi:10.11809/scbgxb2015.01.033

中圖分類號：TP393

文章編號：1006-0707(2015)01-0118-04

本文引用格式：劉林鋒，郭平，趙娟，等.無線傳感器網絡中基于移動sink最優路徑的數據收集策略[J].四川兵工學報，2015(1):118-121.

Citationformat:LIULin-Feng,GUOPing,ZHAOJuan,etal.OptimalTrackofMobileSink-BasedDataCollectionStrategyinWirelessSensorNetworks[J].JournalofSichuanOrdnance,2015(1):118-121.

OptimalTrackofMobileSink-BasedDataCollectionStrategy

inWirelessSensorNetworks

LIULin-Fenga, GUO Pingb,ZHAOJuana,LINinga

(a.DepartmentofLogisticalInformation;b.DepartmentofTraining,

LogisticEngineeringUniversityofPLA,Chongqing401311,China)

Abstract:The nodes in wireless sensor networks(WSN) energy were constrained, and the nodes need to skip through multi hop to transmit data in traditional methods of collecting data, during which some of the nodes energy rapidly depleted due to transmitting data to other nodes. We proposed a new strategy DCST that leads in mobile sink in WSN, and lets it move along the planning optimal track to collect data. DCST uses the ant colony algorithm to find out the optimal path which will connect all the cluster head and let the mobile sink move along this path to collect data. Simulation results show that DCST can prolong the network life cycle more effectively and reduce the energy consumption of the whole network compared to the traditional Leach algorithm.

Keywords:topoptimaltrack;mobilesink;WSN;datacollection

隨著信息技術的高速發展，掌握即時有效的信息對人們有著至關重要的作用。因而收集信息與數據的手段和技術得到了廣泛的開發與應用，很多新興的收集收集技術與策略也隨之誕生。無線傳感器網絡(wirelesssensornetworks,WSN)[1,2]就是當前最為熱門的數據收集技術。并且無線傳感器網絡節點的諸多優點：能量消耗低、易于分布在任何環境中、造價成本低廉和可以自組織地形成無線網絡等特點，使無線信息感知與采集變得空前的簡單與方便。因此，其在當今的無線信息感知領域引起了一場變革，無線傳感器網絡中的數據收集也成為當下研究的熱門。無線傳感器網絡在現實生活中得到了廣泛的應用，如在氣溫、壓力、定位等方面對周圍環境的檢測有著很高的應用前景。LEACH(low-energyadaptiveclusterhierarchy)[3]協議，是人們最早提出與運用的一種基于多簇結構的運用于無線傳感器網絡中的分簇路由協議，許多LEACH協議后的分簇協議：如TEEN[4]，HEED[5]等都是在它的基礎上改進和發展起來的。

傳統的數據收集方法采用固定基站通信，數據經簇頭多跳轉發到基站，這樣容易導致靠近基站的簇頭節點由于轉發過多的數據而過早的死亡，大大縮短了網絡的生存時間。針對這個問題，本文采用在通過LEACH對傳感器網絡節點進行分簇后引入移動sink[6]的方案進行數據收集，讓sink進入到傳感器網絡中直接與簇頭進行通信，這樣簇頭就不需要將收集到的數據經過多跳轉發給基站。并且在節點分簇后利用蟻群算法尋找出連接簇頭的最優路徑，sink沿著計算出的最優路徑進行移動以及數據收集。經過模擬仿真表明，本文提出的結合移動sink與最優路徑的數據收集策略DCST(datacollectionschemewithtopoptimalizingtrack)與LEACH協議相比，DCST能更好地擴張網絡的循環輪數，節省整個網絡的能耗。

1Leach協議

LEACH協議對傳感器節點分簇是周期性的按輪循環。每一輪分簇主要包括2個階段：分簇選舉簇頭階段和簇頭選舉成功后數據穩定傳送的階段。在每一輪選舉簇頭過程中，LEACH協議規定首先讓每一個傳感器節點自動生成一個介于O～1之間的隨機數，此隨機數將用來與計算設定的閾值T( n )作比較。節點要想成功當選，其隨機值必須低于T( n )。其計算公式如下[7]

(1)

式(1)中:r是從第一輪開始到當前為止循環過的輪數；G為到目前r個循環為止，還沒有當選成為過簇頭的傳感器節點。記簇頭數目與網絡中全部節點的比值為P，為防止分簇過大或者過小，需要得出一個最優的簇頭數。以往有文獻[8]已經證明最優簇頭數為

(2)

式(2)中：N為網絡中總的節點數；M為網絡區域的邊長。分簇開始后，根據協議的算法，每個節點通過對比自己的隨機值與T(n)，便可判定自己是否成為簇頭。若節點成功競選，它會通知其他節點，聲明自己已經成功當選。其他節點收到該消息后，通過分析比較自己收到的所有消息，加入信息強度最為強的一個簇頭。節點加入自己的簇頭后需要反饋一個自己已經加入的消息給簇頭。這樣簇就已經分好了。分好簇之后，簇頭節點給每個成員節點劃分一個時隙，每個成員節點只能在自己的時隙內與簇頭通信，即運用TDMA機制，這樣就避免出現網絡的擁塞。時隙劃分好之后就可以進行數據的感知與傳送了，這被稱為穩定運行階段。LEACH協議的總流程如圖1所示。

圖1　LEACH協議流程

2系統模型與問題描述

考慮一個二維區域中的WSN網絡，做出以下假設：

1) 在監控區域內傳感器節點隨機的進行部署，初始能量相同且有限，且部署后位置固定不變；

2) 已知監控區域的大小、網絡中傳感器節點的總數量,移動sink擁有數據收/發、數據融合等功能，負責將收集到的簇頭數據進行融合并發送給外部信息處理中心，且自身可以隨機移動，能量不受限制；

3) 每個節點的功能一樣，數據的收發是全方位的。在假設的模型下，每個傳感器節點的能量消耗主要在一下2個方面：傳感器節點在向簇頭節點發送數據時和簇頭節點接收其他成員節點時所需要消耗的能量與簇頭節點在對其成員節點傳送過來的數據進行融合時所需要消耗的能量。若普通節點到簇頭節點的距離為d，則發送lbit的數據包的能耗為[9]

(3)

其中:Eelec是節點發送1bit數據包的能耗；ξfs為傳送距離d

(4)

簇頭節點接收數據包時，只負責接收而不需要考慮該數據包的傳送距離。其接收lbit的數據包，能量的消耗量為

ERx(l)=l×Eelec

(5)

簇頭結點融合lbit的數據包的能耗為

Eaggregation(l)=l×EDA

(6)

式(6)中，EDA為融合1 bit數據包的能耗。

2.1基于移動 Sink 的數據收集策略

由于以往的在WSN中數據收集都采用固定基站的模型，節點經過多跳傳送將數據傳送給基站，基站收集到數據后進行數據融合然后傳送給外部數據處理中心。這種數據收集方法需要節點將數據經過多跳轉發出去，部分節點由于轉發其他節點的數據而使能量快速耗盡，大大影響網絡的生存時間。為了彌補固定基站這方面的缺陷，本文采用移動sink的方案進行數據收集；具體措施是在講網絡中節點通過LEACH算法進行分簇后，將得到的簇頭節點通過蟻群算法形成一條最優路徑，移動sink沿著規劃好的路徑移動至簇頭附近進行數據收集，從而避免了簇頭節點需要經過多跳傳送將數據送給基站而帶來的過度的能量消耗。而采用移動sink的數據收集方案，讓sink移動到簇頭附近進行數據收集，根據相應的能耗公式可知這樣會大大節約簇頭的能量。

本文以傳統的leach算法為基礎對傳感器網絡節點進行分簇，然后通過蟻群算法搜尋連接所有簇頭的最優路徑，移動sink沿著此路徑進行移動與數據收集，這樣就避免了節點需要將數據多跳傳送給基站而導致能量的過度消耗。

2.2最優路徑的搜索

本文提出的數據收集方案是建立在移動sink與最優路徑相結合上的，最優路徑的搜尋與選擇采用蟻群算法。蟻群算法尋找最優路徑是根據每個螞蟻留下的信息素，然后后面的節點跟誰信息素最強的路徑前進，如此迭代最終得到最優路徑。由于需要記錄經過的節點等信息，所有會有一個專供存儲信息的表格，這個表格每個螞蟻都有。經過的節點記錄在表格中以后不再訪問，除了經過的節點外，表格中還需要記錄允許訪問的節點。每個螞蟻會根據自己角色的不同攜帶相應的報文以方便進行路徑搜尋，其所攜帶的報文格式如圖2～圖4所示。

TypeIDSrcAddVisitedNodeEsumSrcTime

圖2　前向螞蟻攜帶的報文格式

圖3　螞蟻經過簇頭建立的路由表

圖4后向螞蟻攜帶的報文格式

螞蟻攜帶的報文中每個參數代表的意義如表1所示。

(7)

其中：τij表示si，sj在t時刻的信息素濃度；ηi,j表示si，sj間鏈路狀態啟發信息，定義為si，sj間的鏈路帶寬bandwidthij與si，sj間鏈路時延delayij的比值，即

(8)

可用能量度φij(t)，定義為

(9)

在搜尋最優路徑的過程中，根據前向螞蟻攜帶的報文內容，可以計算出鏈路的時延。讓前向螞蟻在到達下一跳簇頭節點的同時更新自己的路由表，根據相應的公式計算得出螞蟻在搜尋當前路徑所消耗的能量并在路由表中更新，經過一些輪次的迭代后便可以得出想要尋找的最優路徑。

表1　螞蟻攜帶報文參數的含義

3DCST方案的具體步驟

1) 初始化：在監測區域中隨機部署固定數目的傳感器節點，部署后節點位置不再改變。

2) 利用LEACH協議對WSN中節點進行分簇，選出簇頭。

3) 利用蟻群算法尋找出連接所有簇頭的最優路徑。

4) 讓sink沿著搜尋出的路徑移動，使其移動到簇頭附近對簇頭存儲著的數據進行收集。

4仿真與分析

現對LEACh協議和本文的數據收集方案DCST通過Matlab進行仿真對比，并在能耗、網絡生存時間方面進行分析。實驗中所使用的參數如表2所示。

表2　仿真場景參數

實驗中，當節點的能量被用完時就標志該節點已經死亡。從圖5中可以看出LEACH協議在1 300輪時節點就全部死亡，而DCST則可以運作至1 700輪。網絡周期延長了400輪，從而可以印證DCST在延長網絡的生存周期上比LEACH協議有著更加明顯的優勢。

圖5　存活節點數對比

從網絡總能耗方面分析，如圖6所示，使用LEACH協議時，在1 250輪左右網絡的能量全部耗盡。而使用DCST時，網絡的總能量在1 650輪左右才消耗殆盡。可以看出DCST相比LEACH使網絡在能耗方面做得更加均衡，更加節約網絡的能量。從總體曲線趨勢上看，LEACH曲線的更加彎屈而DCST更加直一些，說明LEACH在能耗上有著不穩定性而DCST則更加均衡。

圖6　網絡總能耗對比

5結束語

本文用經典的LEACH協議對WSN進行分簇，然后利用蟻群算法尋找出連接所有簇頭的最優路徑。并讓移動sink沿此路徑進行數據收集，而不使用傳統的基站通信的方式，更好地節省了簇頭的能量開銷。該方案利用了LEACH協議在分簇上的優點，并引入了LEACh所不具備的移動sink，還規劃和搜尋出了移動sink的最優路徑。經仿真表面DCST在網絡生存周期與網絡能耗上比LEACH協議更加具有優勢。

參考文獻：

[1]YICK J,MUKHERJEE B,GHOSAL D.Wireless sensor network survey[J].Computer Networks,2008,52(12):2292-2330.

[2]POTDAR V,SHARIF A,CHANG E.Wireless sensor networks:a survey[C]// Proceedings of International Conference on Advanced In-formation Networking and Applications.Bradford,England,2009:636-641.

[3]Heinzelman W，Chandrakasan A，Balakrishnan H.Energy-Efficient Communication Protocol for Wirless Microsensor Networks[C]//Prc.Of the 33rdAnnual Hawaii Int’1 Conf.on System Sciences,Maui:IEEE Computer Society,2000:3000-3014.

[4]Manjeshwar A,Agrawal D P.TEEN:A Protocol for Enhanced Efficiency in Wireless Sensor Networks[C]//in the Proceedings of the 1stInternational Workshop on Paralled and Distributed Computing Issues in Wireless Networks and Mobile Computing.San Francisco,CA,2001.

[5]Younis O,Fahmy S.Heed:A hybrid,energy-efficient,distributed clustering approach for ad-hoc sensor networks[J].IEEE Trans.On Mobile computing,2004,3(4):660-669.

[6]Jaichandran R,Irudhayaraj A,Raja J.Effective strategies and optimal solutions for hot spot problem in wireless sensor networks(WSN)[C]//in Information Sciences Signal Processing and their Applications (ISSPA),2010 10th Int.Conf.on.[S.l.]:[s.n.],2010:389-392.

[7]孫利民,李建中,陳渝.無線傳感器網絡[M].北京:清華大學出版社,2005:94-97.

[8]李成岳,申鉉京,陳海鵬,等.無線傳感器網絡中LEACH路由算法的研究與改進[J]．傳感技術學報，2010，23(8):1163-1167．

[9]YEM,LI C F,CHEN G H,et al.EECS：an energy efficient cluster scheme in wireless sensor networks[C]//IPPCC 2005:Proceedings of the 2005 24thIEEE Performance,Computing,and Communications Conference.Piscataway:IEEE,2005:353-540.

[10]繆聰聰,陳慶奎.基于蟻群的無線傳感器網絡能量均衡非均勻分簇路由算法[J].計算機應用,2013,33(12)：3410-3414.

(責任編輯楊繼森)