低工作周期無線傳感器網絡中的多重洪泛機制

田 樂

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

低工作周期無線傳感器網絡中的多重洪泛機制

田 樂

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

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

多重洪泛;低工作周期;無線傳感器網絡;洪泛次數;節點能耗

1 概述

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

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

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

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

2 相關工作

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

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

3 算法分析

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

如圖1所示,當網絡中的某一個節點需要把數據發送到目的節點或Sink,由于每個節點的傳輸能力有限,數據需要以多跳的方式逐跳轉發到目的節點。

圖1 無線傳感器網絡中的多跳傳輸

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

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

那么K次洪泛,能夠保證數據被正確傳輸的概率P為:

因此,當給定P時,洪泛次數K為:

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

因此,為了保證數據被正確傳輸的概率PN,洪泛次數K為:

4 仿真與性能分析

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

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

表1 仿真場景參數

圖2顯示了在不同的網絡規模情況下(網絡節點數量從400增加到900),網絡中傳輸的總的分組數。從圖中可以看出,MF僅比Directed Diffusion增加了大概11%左右,說明MF并沒有大規模增加廣播分組的數量,尤其是網絡中產生的有效分組數總量較小的情況下更是如此。圖3更加清晰地展示了該結論,圖3顯示的網絡中產生的洪泛和控制分組數量的詳細信息,從中可以看出MF中洪泛分組的數量是Directed Diffusion的1.23倍,這是因為MF中所有的源數據也是洪泛分組,而Directed Diffusion中源數據是以單播的形式傳輸的。

圖2 不同網絡規模情況下的分組數量

圖3 洪泛和控制分組的數量

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

圖4 數據平均傳輸時延

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

圖5 數據成功傳輸概率

圖6顯示了經過100次分組轉發后,網絡中節點平均的剩余能量值,從中可以看出雖然MF使用洪泛機制傳輸數據,但相對于Directed Diffusion并沒有造成節點能量的大量消耗,這是因為在MF中洪泛的次數是收到嚴格控制的,當滿足了用戶期望的數據成功傳輸概率后,每次數據傳輸的洪泛就會被取消,而Directed Diffusion在每次建立傳輸路徑和維護路由時,也需要產生大量的洪泛數據包,因此兩者的能量消耗并沒有明顯的差距。

圖6 節點平均剩余能量

經過仿真發現,MF數據傳輸機制在數據成功傳輸概率、數據傳輸時延方面大大優于傳統的以Directed Diffusion,AODV為代表的預設路由的數據傳輸機制,同時在節點能耗方面并沒有顯著的浪費,因此,MF是一種非常適合應用于低工作周期、低數據傳輸量的無線傳感器網絡的數據傳遞機制。

5 結束語

在低工作周期的無線傳感器網絡中,因為節點會周期性或隨機進入休眠狀態,造成數據傳輸時延和數據丟失情況的增加。當網絡中的數據傳輸數量較小時,可以使用MF機制作為數據傳輸協議。本文提出一種多重洪泛機制,與傳統傳感器網絡路由協議,如Directed Diffusion和AODV相比,MF可以極大減少數據傳輸時延,增加數據成功傳輸的概率,同時并沒有大量增加網路中洪泛分組的數量。

［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按需多徑路由協議［J］.計算機工程,2012,38(9):58-61.

［6]周 靈,王建新.無線多媒體傳感器網絡路由協議研究［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

田 樂.低工作周期無線傳感器網絡中的多重洪泛機制［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-),男,講師、博士,主研方向:無線網絡。

2014-02-12

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