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

田 樂

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

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

田 樂

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

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

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

1 概述

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

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

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

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

2 相關(guān)工作

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

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

3 算法分析

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

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

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

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

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

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

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

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

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

4 仿真與性能分析

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

場景都至少進行50次不同拓撲的仿真,并取平均值作為網(wǎng)絡(luò)的性能指標。

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

圖2顯示了在不同的網(wǎng)絡(luò)規(guī)模情況下(網(wǎng)絡(luò)節(jié)點數(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ù)量的詳細信息,從中可以看出MF中洪泛分組的數(shù)量是Directed Diffusion的1.23倍,這是因為MF中所有的源數(shù)據(jù)也是洪泛分組,而Directed Diffusion中源數(shù)據(jù)是以單播的形式傳輸?shù)摹?/p>

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

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

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

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

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

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

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

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

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

5 結(jié)束語

在低工作周期的無線傳感器網(wǎng)絡(luò)中,因為節(jié)點會周期性或隨機進入休眠狀態(tài),造成數(shù)據(jù)傳輸時延和數(shù)據(jù)丟失情況的增加。當網(wǎng)絡(luò)中的數(shù)據(jù)傳輸數(shù)量較小時,可以使用MF機制作為數(shù)據(jù)傳輸協(xié)議。本文提出一種多重洪泛機制,與傳統(tǒng)傳感器網(wǎng)絡(luò)路由協(xié)議,如Directed Diffusion和AODV相比,MF可以極大減少數(shù)據(jù)傳輸時延,增加數(shù)據(jù)成功傳輸?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]鄔春學,劉 易.基于能量感知的WSN按需多徑路由協(xié)議［J］.計算機工程,2012,38(9):58-61.

［6]周 靈,王建新.無線多媒體傳感器網(wǎng)絡(luò)路由協(xié)議研究［J］.電子學報,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］.計算機工程,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

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

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

2014-02-12

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