【信息科學(xué)與控制工程】

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

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

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

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

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

收稿日期：2014-08-20

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

doi:10.11809/scbgxb2015.01.033

中圖分類號(hào)：TP393

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

本文引用格式：劉林鋒，郭平，趙娟，等.無線傳感器網(wǎng)絡(luò)中基于移動(dòng)sink最優(yōu)路徑的數(shù)據(jù)收集策略[J].四川兵工學(xué)報(bào)，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

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

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

1Leach協(xié)議

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

(1)

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

(2)

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

圖1　LEACH協(xié)議流程

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

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

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

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

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

(3)

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

(4)

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

ERx(l)=l×Eelec

(5)

簇頭結(jié)點(diǎn)融合lbit的數(shù)據(jù)包的能耗為

Eaggregation(l)=l×EDA

(6)

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

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

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

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

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

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

TypeIDSrcAddVisitedNodeEsumSrcTime

圖2　前向螞蟻攜帶的報(bào)文格式

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

圖4后向螞蟻攜帶的報(bào)文格式

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

(7)

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

(8)

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

(9)

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

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

3DCST方案的具體步驟

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

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

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

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

4仿真與分析

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

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

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

圖5　存活節(jié)點(diǎn)數(shù)對(duì)比

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

圖6　網(wǎng)絡(luò)總能耗對(duì)比

5結(jié)束語

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

參考文獻(xiàn)：

[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)絡(luò)[M].北京:清華大學(xué)出版社,2005:94-97.

[8]李成岳,申鉉京,陳海鵬,等.無線傳感器網(wǎng)絡(luò)中LEACH路由算法的研究與改進(jìn)[J]．傳感技術(shù)學(xué)報(bào)，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)絡(luò)能量均衡非均勻分簇路由算法[J].計(jì)算機(jī)應(yīng)用,2013,33(12)：3410-3414.

(責(zé)任編輯楊繼森)