田 樂

(北京建筑大學(xué)電氣與信息工程學(xué)院,北京100044)

低工作周期無線傳感器網(wǎng)絡(luò)中的多重洪泛機(jī)制

田 樂

(北京建筑大學(xué)電氣與信息工程學(xué)院,北京100044)

針對(duì)低工作周期的無線傳感器網(wǎng)絡(luò)存在數(shù)據(jù)成功傳輸率低的問題,提出一種基于洪泛的數(shù)據(jù)傳輸機(jī)制,即多重洪泛機(jī)制(MF)。使用MF時(shí)網(wǎng)絡(luò)中節(jié)點(diǎn)在有數(shù)據(jù)需要發(fā)送時(shí),會(huì)嘗試洪泛K次數(shù)據(jù),洪泛次數(shù)K由網(wǎng)絡(luò)需要的成功傳輸概率決定。仿真實(shí)驗(yàn)結(jié)果表明,引入多重洪泛未大量增加網(wǎng)絡(luò)中傳輸數(shù)據(jù)分組的數(shù)量,節(jié)點(diǎn)能耗相比傳統(tǒng)的路由算法沒有明顯增加,同時(shí)減少分組的傳輸時(shí)延,提高了分組成功傳輸?shù)母怕省?/p>

多重洪泛;低工作周期;無線傳感器網(wǎng)絡(luò);洪泛次數(shù);節(jié)點(diǎn)能耗

1 概述

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network, WSN)是由大量微小低成本的傳感器節(jié)點(diǎn)組成的網(wǎng)絡(luò),這種網(wǎng)絡(luò)普遍應(yīng)用于危險(xiǎn)、環(huán)境惡劣、沒有固定基礎(chǔ)設(shè)施并需要長(zhǎng)期應(yīng)用的極端環(huán)境,如戰(zhàn)場(chǎng)姿態(tài)監(jiān)測(cè)、建筑物的長(zhǎng)期監(jiān)護(hù)和環(huán)境保護(hù)中的長(zhǎng)期參數(shù)監(jiān)控［1］。無線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)成本非常低廉,體積很小,這些節(jié)點(diǎn)的能量供給能力和計(jì)算資源都非常有限,當(dāng)節(jié)點(diǎn)的能源消耗完畢后,節(jié)點(diǎn)只能被廢棄。節(jié)點(diǎn)的能源消耗主要用于傳輸數(shù)據(jù)和監(jiān)聽信道,為了減少網(wǎng)絡(luò)的部署和維護(hù)成本,盡量延長(zhǎng)網(wǎng)絡(luò)的運(yùn)行時(shí)間,保持長(zhǎng)壽命的工作周期,無線傳感器網(wǎng)絡(luò)普遍采用低工作周期的應(yīng)用方式,即節(jié)點(diǎn)會(huì)周期性或隨機(jī)地進(jìn)入長(zhǎng)時(shí)間的休眠狀態(tài),關(guān)閉無線傳輸信道,節(jié)省能量消耗,只在蘇醒后才會(huì)短期參與數(shù)據(jù)的采集或轉(zhuǎn)發(fā)中,這即是低工作周期狀態(tài)。

雖然低工作周期可以顯著延長(zhǎng)的網(wǎng)絡(luò)工作壽命,但引入該種工作方式后,需要轉(zhuǎn)發(fā)數(shù)據(jù)的節(jié)點(diǎn)只能等到通信對(duì)端的鄰居節(jié)點(diǎn)蘇醒后才能把數(shù)據(jù)轉(zhuǎn)發(fā)出去,因此會(huì)增加分組的數(shù)據(jù)發(fā)送時(shí)延,這種時(shí)延稱為休眠時(shí)延［2］。休眠時(shí)延惡化了網(wǎng)絡(luò)的性能,不適用于對(duì)時(shí)間敏感的應(yīng)用,如戰(zhàn)場(chǎng)和應(yīng)急救助。除了會(huì)引起休眠時(shí)延外,由于節(jié)點(diǎn)數(shù)據(jù)的轉(zhuǎn)發(fā)依賴于鄰居是否處于工作狀態(tài),這會(huì)大大降低數(shù)據(jù)成功發(fā)送的概率。

洪泛是一種在無線傳感器網(wǎng)絡(luò)中普遍采用的數(shù)據(jù)傳輸機(jī)制,廣泛應(yīng)用于可靠傳輸網(wǎng)絡(luò)控制命令、告警信息、節(jié)點(diǎn)代碼等關(guān)鍵數(shù)據(jù)的傳輸中,但很少直接應(yīng)用于節(jié)點(diǎn)感知數(shù)據(jù)的傳輸,因?yàn)槿藗兤毡檎J(rèn)為洪泛會(huì)造成網(wǎng)絡(luò)中大量冗余數(shù)據(jù)的傳輸,引起廣播風(fēng)暴的情況。本文中當(dāng)無線傳感器網(wǎng)絡(luò)工作于低工作周期狀態(tài)時(shí),洪泛并沒有引發(fā)需要傳輸大量數(shù)據(jù)的廣播風(fēng)暴,因?yàn)樵诤榉簳r(shí),大部分鄰居節(jié)點(diǎn)處于休眠狀態(tài),限制了洪泛分組的數(shù)量。為了增大數(shù)據(jù)成功發(fā)送的概率,洪泛節(jié)點(diǎn)會(huì)嘗試發(fā)起K次洪泛,這就是多重洪泛(Multi-flooding,MF)。

MF協(xié)議非常易于在傳感器節(jié)點(diǎn)上實(shí)現(xiàn)。由于受到嚴(yán)重的能源、存儲(chǔ)和計(jì)算能力的制約,無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)不便于應(yīng)用復(fù)雜的協(xié)議,而當(dāng)采用MF協(xié)議時(shí),傳感器節(jié)點(diǎn)無需計(jì)算通向不同節(jié)點(diǎn)的路由和維護(hù)鄰居節(jié)點(diǎn)狀態(tài),不需要存儲(chǔ)節(jié)點(diǎn)的鏈路狀態(tài),當(dāng)有數(shù)據(jù)需要發(fā)送時(shí),節(jié)點(diǎn)僅簡(jiǎn)單計(jì)算需要洪泛的次數(shù),就可以向外發(fā)送數(shù)據(jù)。這種簡(jiǎn)單易行的協(xié)議特別適應(yīng)于資源嚴(yán)重受限的傳感器節(jié)點(diǎn)。為減少網(wǎng)絡(luò)傳輸?shù)男菝邥r(shí)延,同時(shí)增加網(wǎng)絡(luò)中分組的成功傳輸概率,本文提出了一種多重洪泛機(jī)制。

2 相關(guān)工作

在無線傳感器網(wǎng)絡(luò)中,洪泛常用來傳輸一些重要的數(shù)據(jù),如鄰居信息、路由建立信息、節(jié)點(diǎn)的二進(jìn)制代碼等。一些經(jīng)典的路由協(xié)議,如Directed Diffusion,LEACH［3-6］,使用洪泛發(fā)起路由的建立過程。由于擔(dān)心洪泛會(huì)引起類似于Ad Hoc網(wǎng)絡(luò)中的廣播風(fēng)暴問題,一些不同的洪泛改進(jìn)措施被設(shè)計(jì)出來減少洪泛分組的數(shù)量,這些方法可以歸類于基于洪泛概率的方法、基于洪泛區(qū)域的方法、基于鄰居信息的方法。

為了更為有效地應(yīng)用洪泛方式,RBP［7］,RBS［8］, Deluge［9］和Trickle［10］也提出了在無線傳感器網(wǎng)絡(luò)中應(yīng)用洪泛的技術(shù),不過所有這些技術(shù)都需要節(jié)點(diǎn)間周期性地交換鄰居信息,維護(hù)鄰居列表,這在低工作周期的傳感器網(wǎng)絡(luò)中比較困難。ADB［11］針對(duì)低工作周期的無線傳感器網(wǎng)絡(luò)提出了一種低功耗、低傳輸時(shí)延的廣播算法,但這種算法是建立在全新設(shè)計(jì)的MAC協(xié)議基礎(chǔ)之上的,不具有通用性。

3 算法分析

MF算法的詳細(xì)規(guī)則如下:當(dāng)節(jié)點(diǎn)處于蘇醒狀態(tài)并有數(shù)據(jù)需要發(fā)送或轉(zhuǎn)發(fā)時(shí),它將以洪泛的方式把數(shù)據(jù)向它的鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)K次,而K決定于預(yù)先設(shè)置的分組成功被目的節(jié)點(diǎn)接收的概率P,因此MF算法的關(guān)鍵在于,如何在給定P的條件下,計(jì)算出節(jié)點(diǎn)洪泛分組的次數(shù)K。

如圖1所示,當(dāng)網(wǎng)絡(luò)中的某一個(gè)節(jié)點(diǎn)需要把數(shù)據(jù)發(fā)送到目的節(jié)點(diǎn)或Sink,由于每個(gè)節(jié)點(diǎn)的傳輸能力有限,數(shù)據(jù)需要以多跳的方式逐跳轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)。

圖1 無線傳感器網(wǎng)絡(luò)中的多跳傳輸

當(dāng)網(wǎng)絡(luò)采用低工作周期模式后,假設(shè)每個(gè)節(jié)點(diǎn)的休眠間隔都符合強(qiáng)度為λsleep的點(diǎn)泊松過程［12］,在某一個(gè)時(shí)刻t有X個(gè)節(jié)點(diǎn)進(jìn)入休眠狀態(tài)的概率為:

因?yàn)樵谀骋粭l從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的數(shù)據(jù)傳輸路徑上,只有當(dāng)所有的節(jié)點(diǎn)都維持蘇醒狀態(tài)時(shí),該條路徑才是連通的,數(shù)據(jù)才能正確地被目的節(jié)點(diǎn)接收到,所以該路徑保持連通的概率為X=0時(shí),即數(shù)據(jù)被成功發(fā)送的概率Psuccess為:

那么K次洪泛,能夠保證數(shù)據(jù)被正確傳輸?shù)母怕蔖為:

因此,當(dāng)給定P時(shí),洪泛次數(shù)K為:

為了保證數(shù)據(jù)能夠正確傳輸給Sink節(jié)點(diǎn),無線傳感器網(wǎng)絡(luò)通常采取密集部署、多重覆蓋的機(jī)制,在多重覆蓋的情況下,MF算法所需的洪泛次數(shù)K將會(huì)更小。假設(shè)網(wǎng)絡(luò)目前是N重覆蓋,由于節(jié)點(diǎn)的部署和休眠都服從點(diǎn)泊松分布,因此每條路徑都是獨(dú)立的,在K次洪泛的條件下,數(shù)據(jù)被正確傳輸?shù)母怕蔖N為:

因此,為了保證數(shù)據(jù)被正確傳輸?shù)母怕蔖N,洪泛次數(shù)K為:

4 仿真與性能分析

本文用NS2仿真工具評(píng)估MF算法的性能。表1列出了部分仿真場(chǎng)景的參數(shù),在實(shí)際進(jìn)行仿真時(shí),針對(duì)不同的評(píng)估性能指標(biāo),可能會(huì)有個(gè)別的參數(shù)進(jìn)行了調(diào)整。所有的節(jié)點(diǎn)的部署都是隨機(jī)地,每種

場(chǎng)景都至少進(jìn)行50次不同拓?fù)涞姆抡?并取平均值作為網(wǎng)絡(luò)的性能指標(biāo)。

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

圖2顯示了在不同的網(wǎng)絡(luò)規(guī)模情況下(網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量從400增加到900),網(wǎng)絡(luò)中傳輸?shù)目偟姆纸M數(shù)。從圖中可以看出,MF僅比Directed Diffusion增加了大概11%左右,說明MF并沒有大規(guī)模增加廣播分組的數(shù)量,尤其是網(wǎng)絡(luò)中產(chǎn)生的有效分組數(shù)總量較小的情況下更是如此。圖3更加清晰地展示了該結(jié)論,圖3顯示的網(wǎng)絡(luò)中產(chǎn)生的洪泛和控制分組數(shù)量的詳細(xì)信息,從中可以看出MF中洪泛分組的數(shù)量是Directed Diffusion的1.23倍,這是因?yàn)镸F中所有的源數(shù)據(jù)也是洪泛分組,而Directed Diffusion中源數(shù)據(jù)是以單播的形式傳輸?shù)摹?/p>

圖2 不同網(wǎng)絡(luò)規(guī)模情況下的分組數(shù)量

圖3 洪泛和控制分組的數(shù)量

圖4對(duì)比了MF和Directed Diffusion 2種數(shù)據(jù)傳輸協(xié)議中的傳輸時(shí)延。從中可以非常明顯地看出,MF的數(shù)據(jù)傳輸時(shí)延要大大低于Directed Diffusion。這是因?yàn)樵贒irected Diffusion中,因?yàn)楣?jié)點(diǎn)要隨機(jī)進(jìn)入休眠狀態(tài),需要傳輸分組的節(jié)點(diǎn)不得不等待它的鄰居節(jié)點(diǎn)的蘇醒,從而增加了很多休眠時(shí)延。而在MF中,節(jié)點(diǎn)需要傳輸數(shù)據(jù)時(shí)直接發(fā)送,根本不需要等待鄰居節(jié)點(diǎn)的相應(yīng),因此沒有休眠時(shí)延。對(duì)于時(shí)間敏感性的應(yīng)用來說,MF是一個(gè)更合適的選擇。

圖4 數(shù)據(jù)平均傳輸時(shí)延

圖5顯示了MF、Directed Diffusion和AODV的數(shù)據(jù)成功傳輸概率,從中可以看出MF能夠成功傳輸數(shù)據(jù)的概率要遠(yuǎn)遠(yuǎn)大于Directed Diffusion和AODV協(xié)議。

圖5 數(shù)據(jù)成功傳輸概率

圖6顯示了經(jīng)過100次分組轉(zhuǎn)發(fā)后,網(wǎng)絡(luò)中節(jié)點(diǎn)平均的剩余能量值,從中可以看出雖然MF使用洪泛機(jī)制傳輸數(shù)據(jù),但相對(duì)于Directed Diffusion并沒有造成節(jié)點(diǎn)能量的大量消耗,這是因?yàn)樵贛F中洪泛的次數(shù)是收到嚴(yán)格控制的,當(dāng)滿足了用戶期望的數(shù)據(jù)成功傳輸概率后,每次數(shù)據(jù)傳輸?shù)暮榉壕蜁?huì)被取消,而Directed Diffusion在每次建立傳輸路徑和維護(hù)路由時(shí),也需要產(chǎn)生大量的洪泛數(shù)據(jù)包,因此兩者的能量消耗并沒有明顯的差距。

圖6 節(jié)點(diǎn)平均剩余能量

經(jīng)過仿真發(fā)現(xiàn),MF數(shù)據(jù)傳輸機(jī)制在數(shù)據(jù)成功傳輸概率、數(shù)據(jù)傳輸時(shí)延方面大大優(yōu)于傳統(tǒng)的以Directed Diffusion,AODV為代表的預(yù)設(shè)路由的數(shù)據(jù)傳輸機(jī)制,同時(shí)在節(jié)點(diǎn)能耗方面并沒有顯著的浪費(fèi),因此,MF是一種非常適合應(yīng)用于低工作周期、低數(shù)據(jù)傳輸量的無線傳感器網(wǎng)絡(luò)的數(shù)據(jù)傳遞機(jī)制。

5 結(jié)束語

在低工作周期的無線傳感器網(wǎng)絡(luò)中,因?yàn)楣?jié)點(diǎn)會(huì)周期性或隨機(jī)進(jìn)入休眠狀態(tài),造成數(shù)據(jù)傳輸時(shí)延和數(shù)據(jù)丟失情況的增加。當(dāng)網(wǎng)絡(luò)中的數(shù)據(jù)傳輸數(shù)量較小時(shí),可以使用MF機(jī)制作為數(shù)據(jù)傳輸協(xié)議。本文提出一種多重洪泛機(jī)制,與傳統(tǒng)傳感器網(wǎng)絡(luò)路由協(xié)議,如Directed Diffusion和AODV相比,MF可以極大減少數(shù)據(jù)傳輸時(shí)延,增加數(shù)據(jù)成功傳輸?shù)母怕?同時(shí)并沒有大量增加網(wǎng)路中洪泛分組的數(shù)量。

［1]Selavo L,Wood A,Cao Q,et al.LUSTER:Wireless Sensor Network for Environmental Research［C］// Proceedings of SenSys’07.［S.1.］:IEEE Press,2007: 125-129.

［2]Gu Yu,He Tian.Data Forwarding in Extremely Low Duty-cycle SensorNetworkswithUnreliableCommunication Links［C］//Proceedings of SenSys’07.［S.1.］:IEEE Press:2007:458-462.

［3]Intanagonwiwat C,Govindan R,Estrin D,et al.Directed Diffusion for Wireless Sensor Networking［J］.IEEE/ ACM Transactions on Networking,2003,11(1):216-222.

［4]Heinzelman W,ChandrakasanA,BalakrishnanH.Energy-eocient Communication Protocol for Wireless Sensor Networks［C］//Proceedings ofInternational Conference on System Sciences.Hawaii,USA:［s.n.］, 2000:256-269.

［5]鄔春學(xué),劉 易.基于能量感知的WSN按需多徑路由協(xié)議［J］.計(jì)算機(jī)工程,2012,38(9):58-61.

［6]周 靈,王建新.無線多媒體傳感器網(wǎng)絡(luò)路由協(xié)議研究［J］.電子學(xué)報(bào),2011,39(1):149-156.

［7]Stann F,Heidemann J,Shroff R,et al.RBP:Robust Broadcast Propagation in Wireless Networks［C］// Proceedings of SenSys’06.［S.1.］:IEEE Press,2006: 236-248.

［8]Wang Feng,Liu Jiamhchun.RBS:A Reliable Broadcast ServiceforLarge-scaleLowDuty-cycledWireless SensorNetworks［C］//ProceedingsofICC’08.［S.1.］:IEEE Press,2008:215-222.

［9]Hui J W,Culler D.The Dynamic Behavior of a Data Dissemination Protocol for Network Programming at Scale［C］//Proceedings of SenSys’04.［S.1.］:IEEE Press,2004:458-465.

［10]Levis P,Patel N,Culler D,et al.Trickle:A SelfregulatingAlgorithmforCodePropagationand MaintenanceinWirelessSensorNetworks［C］// Proceedings of NSDI’04.［S.1.］:IEEE Press,2004: 551-524.

［11]Sun Yanjun,Gurewitz O,Du Shu,et al.ADB:An EfficientMultihopBroadcastProtocolbasedon Asynchronous Duty-cycling in Wireless Sensor Networks［C］//Proceedings of SenSys’09.［S.1.］:IEEE Press,2009:324-333.

［12]Liu B,Brass P,Dousse Q,et al.Mobility Improves Coverage of Sensor Networks［C］//Proceedings of MobiHoc’05.［S.1.］:IEEE Press,2005:265-278.

編輯 索書志

Multi-flooding Mechanism for Low-duty-cycle Wireless Sensor Network

TIAN Le
(College of Electrical and Information Engineering, Beijing University of Civil Engineering and Architecture,Beijing 100044,China)

A novel data transmission mechanism based on flooding for low-duty-cycle Wireless Sensor Network (WSN),named Multi-flooding(MF)is proposed.Using MF,the node which has data to send will keep trying to flood the data to its destination forKtimes,whileKdepends on the required successful transmission ration.Simulation results show that MF with limited times does not generate much more broadcasting packets and energy consumption compared with other routing protocols,but reduces the transmission delay and increases the successful transmission ration remarkably.

Multi-flooding(MF);low-duty-cycle;Wireless Sensor Network(WSN);flooding times;node energy consumption

田 樂.低工作周期無線傳感器網(wǎng)絡(luò)中的多重洪泛機(jī)制［J］.計(jì)算機(jī)工程,2015,41(3):102-105.

英文引用格式:Tian Le.Multi-flooding Mechanism for Low-duty-cycle Wireless Sensor Network［J］.Computer Engineering,2015,41(3):102-105.

1000-3428(2015)03-0102-04

:A

:TP393

10.3969/j.issn.1000-3428.2015.03.019

北京市教育委員會(huì)基金資助面上項(xiàng)目(KM201310016002)。

田 樂(1974-),男,講師、博士,主研方向:無線網(wǎng)絡(luò)。

2014-02-12

:2014-04-24E-mail:tlwhx@126.com