無線傳感器網(wǎng)絡中基于移動sink最優(yōu)路徑的數(shù)據(jù)收集策略

【信息科學與控制工程】

無線傳感器網(wǎng)絡中基于移動sink最優(yōu)路徑的數(shù)據(jù)收集策略

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

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

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

關鍵詞：最優(yōu)路徑；移動sink；無線傳感器網(wǎng)絡；數(shù)據(jù)收集

收稿日期：2014-08-20

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

doi:10.11809/scbgxb2015.01.033

中圖分類號：TP393

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

本文引用格式：劉林鋒，郭平，趙娟，等.無線傳感器網(wǎng)絡中基于移動sink最優(yōu)路徑的數(shù)據(jù)收集策略[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

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

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

1Leach協(xié)議

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

(1)

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

(2)

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

圖1　LEACH協(xié)議流程

2系統(tǒng)模型與問題描述

考慮一個二維區(qū)域中的WSN網(wǎng)絡，做出以下假設：

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

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

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

(3)

其中:Eelec是節(jié)點發(fā)送1bit數(shù)據(jù)包的能耗；ξfs為傳送距離d

(4)

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

ERx(l)=l×Eelec

(5)

簇頭結點融合lbit的數(shù)據(jù)包的能耗為

Eaggregation(l)=l×EDA

(6)

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

2.1基于移動 Sink 的數(shù)據(jù)收集策略

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

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

2.2最優(yōu)路徑的搜索

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

TypeIDSrcAddVisitedNodeEsumSrcTime

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

圖3　螞蟻經(jīng)過簇頭建立的路由表

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

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

(7)

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

(8)

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

(9)

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

表1　螞蟻攜帶報文參數(shù)的含義

3DCST方案的具體步驟

1) 初始化：在監(jiān)測區(qū)域中隨機部署固定數(shù)目的傳感器節(jié)點，部署后節(jié)點位置不再改變。

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

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

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

4仿真與分析

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

表2　仿真場景參數(shù)

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

圖5　存活節(jié)點數(shù)對比

從網(wǎng)絡總能耗方面分析，如圖6所示，使用LEACH協(xié)議時，在1 250輪左右網(wǎng)絡的能量全部耗盡。而使用DCST時，網(wǎng)絡的總能量在1 650輪左右才消耗殆盡?？梢钥闯鯠CST相比LEACH使網(wǎng)絡在能耗方面做得更加均衡，更加節(jié)約網(wǎng)絡的能量。從總體曲線趨勢上看，LEACH曲線的更加彎屈而DCST更加直一些，說明LEACH在能耗上有著不穩(wěn)定性而DCST則更加均衡。

圖6　網(wǎng)絡總能耗對比

5結束語

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

參考文獻：

[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]孫利民,李建中,陳渝.無線傳感器網(wǎng)絡[M].北京:清華大學出版社,2005:94-97.

[8]李成岳,申鉉京,陳海鵬,等.無線傳感器網(wǎng)絡中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]繆聰聰,陳慶奎.基于蟻群的無線傳感器網(wǎng)絡能量均衡非均勻分簇路由算法[J].計算機應用,2013,33(12)：3410-3414.

(責任編輯楊繼森)