滿足業務實時性要求的路由設計*

侯 華,任艷娜,周武旸

(1.河北工程大學信息與電氣工程學院,河北 邯鄲 056038;2.中國科學技術大學電子工程與信息科學系,合肥 23000)

?

滿足業務實時性要求的路由設計*

侯 華1*,任艷娜1,周武旸2

(1.河北工程大學信息與電氣工程學院,河北 邯鄲 056038;2.中國科學技術大學電子工程與信息科學系,合肥 23000)

針對無線傳感器網絡數據傳輸實時性問題,基于非均勻分簇網絡模型提出了一種路由方法。其主要思想是為收集的數據設定截止期,通過鏈路時延估計,綜合考慮截止期和鏈路時延等影響接收端接收數據的有效性的因素,提出了一種可以滿足多種業務時延要求的路由方法。仿真實驗結果表明,該路由方法能夠保證信息的有效性。

無線傳感器網絡;路由;延遲;截止期錯失率;非均勻分簇

隨著實時應用需求的逐漸增多,如何在無線傳感器網絡中為這類業務提供滿意的服務受到了越來越廣泛的關注。例如,在重病監護室內,患者身上安放的傳感器節點會采集該患者身體的血壓、體溫等數據,并將這些信息實時地傳送給監護人員,如果數據顯示有異常情況發生,那么監護人員會立即接到相應的報警信息并通過閱讀監測信息得知異常數據源的具體情況并及時采取相應的急救措施。實時服務與傳統的盡力(Best-Effort)服務模型的區別在于前者對數據包的傳輸截止期有更為嚴格的要求。若實時業務的數據包時延超過了截止期,往往代表這部分數據已經失效,而失效數據的傳輸有可能會帶來嚴重的后果。因此,為了支持逐漸增多的實時應用,在無線傳感器網絡中提供有保障的服務質量QoS(Quality of Service)顯得尤為重要。

1 相關工作

文獻[1-4]在非分簇網絡中,通過計算轉發節點到匯聚節點的距離,將數據的截止期要求轉化為相應的傳輸速率要求,然后選擇滿足速率要求的節點作為下一跳轉發節點,以滿足數據的實時性要求,降低數據截止期錯失率。由于上述4篇文獻均未考慮數據融合技術,因此節點轉發數據將消耗較多的能量。文獻[5-7]采用非均勻分簇網絡模型,將整個網絡分為大小不同的簇,路由方法也分為簇內路由和簇間路由兩部分。簇內節點將數據轉發給其簇首,簇首將采集到的信息進行數據融合后,轉發給符合要求的下一跳簇首,通過多跳方式將數據轉發給匯聚節點。這種數據轉發方法,能降低節點的能量消耗,可惜的是沒有考慮到信息的實時性要求,信息截止期錯失率較高。文獻[8-9]在路由選擇時考慮信息的實時性要求,將信息分類為實時性數據和非實時性數據。實時性數據轉發時,選擇最短路徑轉發,用以降低數據轉發時延。文獻[8]中的非實時性數據轉發時,綜合考慮數據傳輸的可靠性和能量消耗。而文獻[9]中的非實時性數據轉發時,則綜合考慮鄰居節點的剩余能量和緩沖隊列占空比,選擇總體代價最小的節點作為下一跳轉發節點。這類方法可以粗略地將數據分類為實時性數據和非實時性數據,并不能滿足多種類型業務中每一種業務的特定時延要求。

本文考慮分簇網絡模型下的路由策略。簇首節點首先根據每個數據各自的截止期和估計的鏈路時延,將信息分批次放入不同的隊列中,在各隊列的信息被發送出去之前,隊列內的信息首先進行數據融合處理。這樣做,既可以滿足不同信息的實時性要求,又可以降低簇首節點的能量消耗,有利于保障整個系統的穩定性。

2 路由方法設計

本文路由方法的設計目標是滿足多業務傳輸時各類業務的時延要求,降低信息截止期錯失率。

2.1 網絡拓撲模型

本文采用文獻[5]中介紹的非均勻分簇網絡模型。

傳感器節點部署在均勻間隔的同心圓網絡中,Sink節點在網絡正中心,圓環間的間隔為δ。若節點i與Sink節點間的近似距離為di,節點i根據di判定自己所在的環k。若di滿足如下關系:

(k-1)δ≤di≤kδ

(1)

則表明節點i處于第k環。

在WSN中,節點間發送數據的能耗與跳數和距離相關。若兩節點之間的距離為g,由文獻[5]可知,g≤87 m時,單跳通信比多跳通信更節省能量,且隨著融合率c的增加,單跳通信將比多跳通信節省更多的能量。本文簇內節點采取單跳通信方式,因此將圓環間的間隔δ定為87 m。

各環最優簇首個數由以下公式確定:

(2)

其中,mk是第k環的簇首個數,P是該網絡中最大的環數。可見,簇首個數mk與圓環編號k成正比,第k環轉發外環數據的能耗由第k環各簇首均衡分擔。其中,位于圓環編號為1內的節點直接與匯聚節點通信。

若第k圓環的面積為Sk,把該圓環劃分為mk份,則該環內的每個簇首的競爭區域近似為Sk/mk。通過公式:

(3)

競爭半徑R隨著圓環編號k的增大而減少,形成離Sink節點較近的圓環成簇個數較少、成簇范圍較大的非均勻分簇網絡。由文獻[5]仿真實驗驗證,建立的非均勻分簇網絡可以解決能量空洞問題。

2.2 鏈路時延估計

(4)

(5)

其中,Packet_size是數據包的尺寸,Ack_size是確認數據的長度,Bandwidth是網絡帶寬。由式(5)可以看出,網絡帶寬、確認數據的長度及數據包的尺寸共同決定了Delaytran的大小。

延遲估計器采用TCP協議中的RTT(Round Trip Time)估計法[11-12]:

R←αR+(1-α)M

(6)

(7)

由發送節點獲得每個數據包鏈路延遲測量值M。即發送節點記錄發包時間Ts和由ACK包攜帶的其轉發節點收到包的時間Tr。假設ACK包通過一個反向并行的無沖突信道傳輸,那么Tr和Ts的差可近似作為M的計算值。

2.3 路由方法設計

信息轉發包括兩部分,第1部分是簇內節點信息的轉發,第2部分是簇首節點信息的轉發。該部分內容將對兩部分信息轉發的方法做詳細介紹。

2.3.1 簇內信息轉發方法設計

在系統中,每一個傳感器節點都儲存有一個針對于各種類型業務的信息表格,該表格中記錄了每一類信息包括截止期在內的各種特征。表格按信息截止期長短對其進行等級劃分,截止期越短的信息其等級越高,因為這代表了該數據對實時性的要求越高。

表1 信息表格結構

業務類型占2 bit。用于表示所傳輸的業務類型,如表2所示。

表2 業務類型域中內容

無線傳感器網絡中主要是數據的傳輸,根據具體場合數據傳輸的實時性要求將實時性要求特別嚴格的數據業務類型定義為十分緊急;將實時性要求較嚴格的數據業務類型定義為緊急;將實時性要求不嚴格的數據業務類型定義為非緊急。

實際的信息截止期是從0到1536 ms,占據11 bit的存儲空間。

簇內的每個感知節點按一定的時間間隔采集其感知范圍內的信息。節點采集到信息后,將該信息特征與該節點存儲的信息等級表的相關內容進行對比,并根據信息等級表設置信息截止期t。即將RTS幀中時延容忍域設為定時器,定時器的值被設置為信息剩余的截止期t,可見t隨著時間的推移而遞減。RTS幀結構如下:

表3 RTS幀結構

節點之間的通信采用基于競爭的MAC協議,通過RTS/CTS/DATA/ACK的交互方式轉發信息。簇首收集的是本簇內所有節點的信息,簇內節點到簇首的鏈路時延可能會不同。因此,當簇首將本簇內所有節點的信息收集完后,各個節點的信息截止期應變化為t=t-Delaylink max。其中,Delaylink max是一個簇內的所有節點到匯聚節點的鏈路時延的最大值。簇首節點收集其感知范圍內的信息所設定的信息截止期變化,也遵循此規律。

2.3.2 簇首信息的轉發方法設計

簇首收集完本簇內節點的信息后,將信息分批、融合發送給匯聚節點。簇首通過計算待轉發數據的截止期與簇首到匯聚節點鏈路的時延差2個數值并將其進行比較,來決定數據發送的批次和時間。若轉發數據的截止期與簇首到匯聚節點的鏈路時延的差大于T,則將該待轉發數據定為等待發送數據;反之,將該待轉發數據定為立即被發送數據。其中,T是根據實時性數據的時延要求定義的時間間隔。所有的簇首都照此原則選擇立即待轉發數據,并對其進行數據融合處理。偽代碼如下所示:

ifTi>0,i∈{1,2,…,n}

N(1,k)←i,k←k+1

end if

Delaymax←argmax{Delay1,Delay2,…,Delayk-1}

Ti←Ti-Delaymax,i∈N

if(Ti-Delay-link)

Ac=1,M(1,c)←i,c←c+1

else then

Bm=1,Q(1,m)←i,m←m+1

end if

數據分類后,數據轉發流程偽代碼如下:

ACH=1,BCH=1 then

else then

ACH=1,BCH=0

else then

ACH=0,BCH=1 then

else then

ACH=0,BCH=0

end if

根據數據的截止期將簇首采集的數據分為4類組合:ACH=1,BCH=0,僅有立即轉發的數據;ACH=0,BCH=1,全為等待轉發的數據;ACH=1,BCH=1,既有立即轉發的數據又有等待轉發的數據;ACH=0,BCH=0,簇首沒有收集到數據。

4種數據類型組合對應的數據轉發流程偽代碼如下:

caseACH=1,BCH=0

if Channelstate=1 then

Send data to Sink node then

ACH=0,BCH=0

break

else then

t=randn(0,c-1)

backoff t then

return to check the state of channel

end if

caseACH=0,BCH=1

if Channelstate=1 then

Send data to Sink node

BCH=0

break

else then

t=randn(0,m-1)

backoff t then

if(Ti-t)>Ttolerate,i∈Qthen

return to caseACH=0,BCH=1

else then

return to caseACH=1,BCH=1

end if

caseACH=1,BCH=1

if Channelstate=1 then

Send data to Sink then

ACH=0 then

Ti←Ti-twait,i∈Qthen

return to caseACH=0,BCH=1

else then

t←randn(0,c-1)

backoff t

Ti←Ti-t,i∈Mthen

ifTi

discard data then

Tj←Tj-t,j∈Qthen

return to caseACH=0,BCH=1

else then

return to check the state of channel

end if

caseACH=0,BCH=0

break

2.3.3 快速的路由方法設計

本小節是從實際系統運行的角度考慮,主要分析系統解析信息截止期的快慢。

理論上信息截止期是一個具體的數值,如512 ms。在系統中,如果硬件解析512時需要解析9bit的數據,需要很多個時鐘周期,勢必影響算法的復雜度。在實際的應用系統中,需要簡化實際的信息截止期,將信息截止期進行量化,分為若干個區間,系統按信息截止期區間對應的二進制編碼進行解析,可以大大縮短解析時間,降低算法復雜度。

表4 x值分段表

參照表4中x值劃分的方法將信息截止期0～1536 ms劃分為8段,如表5所示。

表5 信息存活時間的量化和編碼

由表5可知,信息截止期只占3bit的存儲空間,系統解析信息截止期時只需解析3bit的二進制編碼,大大降低了算法復雜度,加快了系統的運行速度。

3 仿真及性能分析

本文仿真基于OMNeT++環境,使用NED和C++語言實現網絡模型和數據轉發方法的仿真,并使用MATLAB軟件導出數據,對實驗結果進行分析和評估。其中假設采用基于競爭的介質訪問控制(MAC,Media Access Control)協議,且忽略無線信道干擾。仿真中εf、節點初始能量E、Ee等參數的取值與文獻[14]相同。覆蓋區域半徑R=400 m,仿真節點個數N=1000、N=2000、N=3000、N=4000。

在傳感器網絡中,支持實時性QoS要求滿足截止期錯失率在可以容忍的范圍內。嚴格來說,硬實時應用要求所有的包都滿足截止期要求,而軟實時應用要求滿足截止期的包達到一定的比例。本文路由設計的目標就是盡力提高這一比例,使更多的數據包在截止期內轉發給匯聚節點,以滿足信息的實時性要求,保證數據的有效性。

為簡單起見,本文仿真主要將簇頭收集的數據分為兩批轉發給匯聚節點。根據信息的截止期將實時性要求較高的數據定義為第1批轉發數據,且在合適的時間轉發給匯聚節點。實時性要求不高的數據,等待第1批數據轉發完畢,在合適的時間將數據轉發給匯聚節點。

圖1 全部數據的截止期錯失率比較

圖1對比了在節點個數不同時,文獻[5]采用的路由方法和本文所采用的路由方法及文獻[9]采用的路由方法DGEER(Delay-Guaranteed Energy-Efficient Routing)在信息截止期錯失率方面的差異。其中,圖例中的“本文”表示采用實際的信息截止期,“快速的路由方法”表示采用量化的信息截止期。由圖1可以看出,采用本文的快速路由方法與非快速路由方法時,信息截止期錯失率基本無差異。由2.3.3小節分析可知,采用量化的信息截止期可以大大降低算法復雜度,故實際系統中應采用量化的信息截止期。且由圖1可以看出,采用本文所提的路由方法時,信息截止期錯失率明顯比采用文獻[5]的路由方法及采用DGEER時低,且隨著節點個數的增多,本文所提算法的信息截止期錯失率增長速度比較慢,這說明本文所提算法可以更好地滿足信息的實時性要求,保證信息的有效性。主要在于本文在數據轉發時采用類似于排隊的方法,實時性要求越嚴格的數據在較早的時間轉發給匯聚節點。且充分考慮全部信息的實時性要求,盡量在信息的截止期內將數據轉發給匯聚節點,保證了數據的實時性傳輸。

圖2是在不同節點數量的情況下,實時性要求較高的數據采用3種路由方法時,信息截止期錯失率的比較。通過圖可以看出,采用本文提出的路由方法時信息截止期錯失率最小,表明其實時性更好。主要是因為本文采用的路由方法在轉發實時性要求較高的數據時,綜合考慮信息的截止期和鏈路時延,轉發順序優先于實時性要求不高的數據,盡可能在信息的截止期內將數據轉發給匯聚節點,滿足信息的實時性要求。通過圖2還可以看出采用本文的快速路由方法與非快速路由方法時,信息截止期錯失率大小基本相同。

圖2 實時性要求較高的數據的截止期錯失率比較

圖3 實時性要求不高的數據的截止期比較

圖3給出了在節點個數不同時,實時性要求不高的數據采用3種路由方法時,信息截止期錯失率的對比。通過圖3可以看出采用本文的快速路由方法與非快速路由方法相比較,信息截止期錯失率差異不明顯。圖中還可以看出,采用本文提出的路由方法時節點的截止期錯失率最小。主要在于本文采用的路由方法綜合考慮數據的截止期和簇首到匯聚節點的鏈路時延,數據在最合適的時間轉發出去,可以盡量減少簇首對信道的競爭,在保證實時性數據的實時性要求的同時,也實現了非實時性數據傳輸的實時性。

4 結束語

本文基于非均勻分簇的無線傳感器網絡模型,對網絡中數據的實時轉發方法進行了研究。通過對鏈路時延的估計,分析簇內信息轉發時信息截止期的變化,然后結合信息截止期和鏈路時延,將簇首收集的信息在合理的時間轉發給匯聚節點,提高了信息轉發的實時性,保證了信息的有效性。設計的快速信息截止期存儲方法,可以大大減小存儲空間,縮短系統解析信息截止期的時鐘周期,降低算法復雜度。仿真實驗表明本文提出的數據轉發方法能滿足信息的實時性要求,在實時性以及數據的整體有效性上優于文獻[5]及DGEER?？焖俚男畔⒔刂蛊诖鎯υO計在數據傳輸實時性的性能上與實際的信息存活時間基本相同。

本文簇首轉發信息采用單跳的通信方式,這樣勢必會比多跳通信消耗的能量多,下一步的工作是在考慮信息截止期和鏈路時延的前提下,設計簇首之間通過多跳的方式轉發信息的方法,在滿足信息實時性要求的同時降低能量的消耗。

[1] 李燕君,王智,孫優賢. 傳感器網絡基于兩跳鄰居信息的實時路由設計[J]. 軟件學報,2009,20(7):1931-1942.

[2]Lin K,Ge H G,Xiong N X,et al. Energy Efficiency QoS Assurance Routing in Wireless Multimedia Sensor Networks[J]. Systems Journal,IEEE,2011,5(4):495-505.

[3]Deng X,Yang Y Y. Online Adaptive Compression in Delay Sensitive Wireless Sensor Networks[J]. IEEE Transactions on Computer,2012,61(10):1429-1442.

[4]Deng X,Yang Y Y. Communicati on Synchronization in Cluster-Based Sensor Networks for Cyber-Physical Systems[J]. IEEE Transactions on Emerging Topics in Computing,2013,1(1):98-110.

[5]侯華,劉超,周武旸. 能量高效均衡的動態分簇路由設計[J]. 北京郵電大學學報,2013,36(3):54-59.

[6]喬學工,王哲,王華倩,等. 基于權值的非均勻分簇路由算法[J]. 傳感技術學報,2014,27(1):107-112.

[7]蔣暢江,石為人,唐賢倫. 能量均衡的無線傳感器網絡非均勻分簇路由協議[J]. 軟件學報,2012,23(5):1222-1232.

[8]Alam R,Abdur M. Energy-Aware QoS Provisioning for Wireless Sensor Networks:Analysis and Protocol[J]. Journal of Choong Seon Communications and Networks,2009,11(4):390-405.

[9]梁慶偉,姚道遠,鞏思亮. 一種保障時延能量高效的無線傳感器網絡路由協議[J]. 西安交通大學學報,2012,46(6):48-52.

[10]李燕君,王智,孫優賢. 無線傳感器網絡的鏈路分析與建模[J]. 傳感技術學報,2007,20(8):1846-1851.

[11]Chipara O,He Z,Guo L X,et al. Real-Time Power-Aware Routing in Sensor Networks[J]. 14th IEEE International Workshop on Quality of Service,2006:83-92.

[12]Rajendran V,Obraczkal K,Garcia-Luna-Aceves J J. Energy Efficient Collision Free Medium Access Control for Wireless Sensor Networks[J]. Wireless Networks,2006,12(1):63-78.

[13]樊昌信,張甫翊,徐炳祥,等. 通信原理[M]. 北京:國防工業出版社,2001.

[14]Mao S,Zhao C L,Zheng Z,et al. An Improved Fuzzy Unequal Clustering Algorithm for Wireless Sensor Network[J]. Mobile Networks and Applications,2012,11(6):45-250.

侯華(1980-),女,博士,副教授,研究生導師,2003年畢業于西南科技大學電子信息工程專業,2008年獲中國科學技術大學通信與信息系統專業博士學位,現任教于河北工程大學,研究方向為移動通信技術、認知無線電技術、無線傳感器網絡,hbhouhua@163.com;

任艷娜(1987-),女,碩士研究生,現就讀于河北工程大學信息與電氣工程學院,研究方向為無線傳感器網絡;

周武旸(1972-),男,中國科學技術大學電子工程與信息科學系教授、博士生導師。1993年和1996年在西安電子科技大學獲學士和碩士學位,2000年在中國科學技術大學獲博士學位。研究方向為中繼與協作通信、無線資源管理、無線組網技術。

DesignofRoutingBasedonMeetingServiceReal-TimeRequirements*

HOUHua1*,RENYanna1,ZHOUWuyang2

(1.School of Information and Electrical Engineering,Hebei University of Engineering,Handan Hebei 056038,China;2.Department of Electronic Engineering and Information Science,University of Science and Technology of China,Hefei 23000,China)

For wireless sensor networks of real-time data transmission phenomenon,a new routing method is proposed based on the uneven cluster network model. Through setting deadline for collecting data,estimating link delay and considering the factors influencing the validity of receiver’s receiving data such as the deadline of information,link delay,etc,a new routing method fit for multi-service delay requirements is proposed. Simulation results show that the routing method can ensure the validity of the information.

wireless sensor network;routing;delay;deadline miss ratio;uneven clustering

項目來源:河北省自然科學基金項目(F2012402046);河北省高等學?？茖W技術研究重點項目(ZH2011222)

2014-04-03修改日期:2014-07-12

10.3969/j.issn.1004-1699.2014.09.021

TP393

:A

:1004-1699(2014)09-1275-06