面向異構業務的基于數據包優先權的組播算法*

史玲華,吳松麗

(駐馬店職業技術學院信息工程系,河南 駐馬店 463000)

無線傳感網絡WSNs(Wireless Sensor Networks)已廣泛應用于異常事件檢測和重要數據收集[-2]。傳感節點以單播或組播方式將檢測到的數據或接收的數據包傳輸至目的節點。盡管單播已廣泛應用,但仍具有局限性。對于軟件更新或警示信息分發時,選擇組播方式將數據包傳輸至多個節點更為便利。然而,維持組播業務的服務質量QoS(Quality of Service)存在挑戰,特別是在異構流量業務環境[3]。本文所考慮的異構體現于多個業務間要求不同,如有些業務對時延敏感、有些業務允許一定的時延,即業務性能存在差異性。

盡管有些應用需要高優先流量[4],但是基于IEEE 802.15.4標準的WSNs并不支持異構流量業務。許多研究人員試圖通過單播業務滿足WSNs 的QoS。文獻[5]提出基于動態多級優先DMP(Dynamic Multi-Level Priority)數據包調度算法。通過DMP算法減少端到端傳輸時延,進而滿足WSNs內時延敏感性流量業務。DMP算法引用了時分多址接入TDMA(Time Division Multiple Access)技術和多隊列系統。

然而,基于TDMA的調度算法需要有一個中心節點分配時隙,這在隨機分布式傳感網絡中難以實現。而優化后的無碰撞的多載波監聽CSMA/CA(Carrier Sense Multiple Access with Collision Avoidance)給時延敏感業務提供優先信道接入。文獻[6]提出引用了CSMA/CA策略,并通過多級退避算法支持QoS服務。然而,這種信道優先接入策略并沒有考慮到信道接入時延,這直接影響到網絡內的端到端傳輸時延。

實際上,端到端傳輸時延和可靠傳輸是影響QoS的兩個重要因素。而端到端傳輸時延又取決于隊列、媒體接入控制MAC(Medium Access Control)和傳輸時延。

因此,本文試圖通過減少隊列、MAC和傳輸時延,進而減少端到端時延和保證優先數據包傳輸的可靠性。為此,本文提出了基于數據包優先權的組播算法POMT(Priority-Oriented Multicast Transmission Algorithm for Heterogeneous traffic)。考慮了業務的異構性,POMT算法將業務劃分優先和非優先兩類,并對隊列進行管理。然后依據業務流量類型設置信道接入窗口尺寸,進而保證優先業務提前接入信道。此外,為了實現可靠傳輸,引用確認重傳機制,提高了數據包傳輸成功率。實驗數據表明,提出的POMT算法能夠有效地降低端到端傳輸時延,并提高了數據包傳輸成功率。

1 網絡模型

考慮分布式的基于簇拓撲的WSNs網絡。數據流量從信宿節點流向多播簇群。此外,網絡內節點可以產生不同類型的數據流量。簇內節點可通過一跳或多跳建立通信連接。

負責簇間通信的節點稱為主節點LNs(Leaf Nodes),而在源節點與LNs間的節點稱為轉發節點RNs(Relay Nodes)。在同一個簇內的所有節點屬于同一個多播群。此外,假定隊列尺寸足夠大,鄰居節點間通信信道是無差錯的信道。

考慮的網絡模型,如圖1所示。一個信宿節點S、6個傳感節點(A、B、C、D、E、F)。這6個傳感節點形成了一個簇群,并且節點A為數據包源節點、而節點E、F為LNs。而其他的節點(B、C、D)稱為RNs。

此外,依據節點到信宿跳數,將簇內節點劃分不同層。源節點離信宿只有一跳,將其稱為Level 1,而節點B、C屬于Level 2、節點D屬于Level 3,而節點E、F屬于Level 4。

圖1 網絡模型

2 POMT算法

針對異構業務,POMT算法引用了數據包優先權。不同的數據包具有不同的轉發權。首先,引用兩級優先權:優先和非優先。整個POMT算法由數據包分類、隊列管理和信道優先接入和可靠傳輸策略四部分組成。POMT算法框架如圖2所示。

圖2 POMT算法框架

數據包分類階段負責設置數據包優先權;而隊列管理階段是指如何依據數據包優先權將數據包載入堆棧。在信道優先接入階段,引用退避算法,給節點分配接入窗口。最后,通過重傳確認機制確保可靠傳輸。

2.1 數據包分類

為了給數據包分類,引用802.15.4的幀結構[7],并利用物理層首部預留的比特位表征數據包類型。首先將數據包分為優先數據包和非優先數據包。整個幀控制部分由兩個字節構成,如圖3所示。將處于預留字段Reserved的第7 bit～9 bit表示數據包類型。若數據包是優先的,則Reserved=111;否則Reserved=100。

圖3 數據包分類標志位

一旦接收了數據包,節點就檢測該數據包的預留字段Reserved值。如果是111,則為優先數據包;否則就是非優先數據包。

2.2 隊列管理

POMT算法在同一個隊列內考慮兩個堆棧,分別存放優先數據包和非優先數據包,如圖4所示。

圖4 堆棧管理

一旦接收到數據包,首先確認該數據包的源地址和數據包的序列號,進而決定是否將數據包插入隊列中。如果是第1次接收該數據包,并且該數據包是來自層級更低的節點,則將數據包插入堆棧。然后,再確認數據包的類型(優先或非優先),再對應插入堆棧中。數據包出棧的策略:先進先出FIFO(First-In-First-Out)[8]。當接收到來自同一層級或更高層級的數據包時,就不轉發數據包。隊列管理算法的偽代碼如下所示。

Algorithm 1 2-Class Queue Management

1: While a packet arrives in the queue do

2: If the packet is a fresh packet then

3: if the packet is an external packet from a lower-level node or it is and internally generated packet then

4: if Type(packet)=priority packet then

5: insert the packet into pri stack of the queue

6: else

7: insert the packet into npri stack of the queue

8: end if

9: else

10: discard the packet

11: end if

12: else

13: discard the packet

14: end if

15: end while

隊列管理的目的在于通過時延敏感業務的隊列時延,進而減少傳輸時延。端到端的傳輸時延取決于將數據包從源節點傳輸至目的節點所需要的傳輸次數。傳輸次數越多,時延越大,反之亦然。為此,POMT算法只轉發來自低層級的數據包,這減少了數據包被轉發的次數。

2.3 信道優先接入

POMT算法引用基于優先權的CSMA/CA機制接入信道。所有節點從同一個競爭窗口CW隨機選擇退避時間[9]。退避時間bt取決于窗口CW尺寸、退避指數α以及單位的退避時隙ST,其定義如式(1)所示:

bt=Random(·)×ST

(1)

式中:Random(·)表示隨機取值函數。即從窗口CW隨機取整數。整數范圍為[0,CW-1],而CW=2α。

為了使得優先數據包能夠優先接入信道,POMT算法將優先數據包的窗口CW設置更窄。因為窗口CW越窄,數據包越能優先接入信道。

信道接入流程如圖5所示。首先確認隊列流量類型,然后依據流量類型設置窗口CW,再隨機設置退避時間。隨后,檢測信道是否為空閑。如果,空閑,就傳輸數據包。否則,就是再隨機選擇退避時間,并記錄退避次數Count。為了防止過多退避,設置退避次數上限MaxCount。如果Count小于MaxCount,就重新設置窗口CW,否則就接入信道失敗。

圖5 信道接入流程

2.4 可靠傳輸

為了保證數據傳輸的可靠性,引用確認重傳機制。POMT算法引用iACK和eACK兩類確認包。其中,iACK包屬于隱晦的確認包[10]。將發送節點監聽到鄰居節點轉發它傳輸的包,稱為iACK。而eACK包屬于明確的確認包。當接收節點接收了數據包,就向發送節點回復eACK。

以圖1為例,節點A向鄰居節點組播一個數據包,且節點B、C接收了數據包。一旦節點B、C接收了該數據包,就重播該數據包。當節點A收到監聽到節點B、C重播了自己轉發的數據包,就說明節點B、C已正確接收了自己轉發的數據包。這就隱晦的確認包iACK。

如果在規定時間內,節點A未能收到此iACK包,則節點A就重傳數據包。簇內的葉節點(E、F)收到數據包,它們就向查詢數據包的源節點,并向它們回復eACK包。

3 實驗仿真及性能分析

3.1 仿真環境及性能指標

為了更好地分析POMT協議性能,利用MATLAB建立平臺。以圖1為仿真網絡模型。在每輪仿真中,每個節點產生10 000個數據包。節點A、B、C、D以隨機方式產生優先數據包和非優先數據包。數據傳輸率為250 kbit/s。依據文獻[11],節點在接收模式時電流消耗為19.7 mA,而傳輸模式時電流消耗為17.4 mA。

此外,選擇傳統的CSMA/CA作為參照。同時,為了比較BO1和BO2兩個退避算法對性能影響,將引用BO1的POMT算法和引用BO2的POMT算法進行同步仿真,且分別記為POMT+BO1、POMT+BO2。

實驗仿真中考查了端到端傳輸時延、平均能量消耗、碰撞概率和數據包丟失率。各自定義如下:

①端到端傳輸時延

端到端傳輸時延指將數據包從源節點傳輸至最后一個葉節點所經歷的時間,其主要包括隊列等待時間、傳輸時間和MAC協議退避時間。因此,每一跳時延可定義為:

Dt=Tt+Qt+bt

(2)

式中:Tt、Qt和bt分別表示傳輸時間、隊列時間和每一跳的退避時間。

②平均能耗

一個節點所消耗的總能量Etot可表示為:

Etot=NtPtTt+NrPrTr

(3)

③碰撞概率

當兩個或多個節點選擇了同一個窄的退避時間去接入信道時,它們就會出現碰撞。這個碰撞概率取決于競爭節點數、CW尺寸和退避算法。碰撞概率等于兩個或多個節點同時接入信道的次數與接入信道總次數的比值。兩個或多個節點同時接入信道就會發生碰撞。

④數據包傳遞率

傳輸碰撞或信道干擾等原因均會導致數據包丟失,使得數據包傳輸失敗。數據包傳遞率等于網絡內成功接收了數據包數與總的所需傳輸的數據包數之比。

3.2 實驗數據分析

首先從總體方案上比較了CSMA/CA和POMT算法的整體性能。CSMA/CA并不支持分類服務和組播的重傳。而提出的POMT協議支持數據包分類以及重傳。表1對比了POMT和CSMA/CA協議特性。從表1可知,POMT協議支持組播的QoS服務,這要歸功于業務差異、退避算法和重傳機制。

表1 POMT和CSMA/CA

3.2.1 端到端傳輸時延

接下來分析POMT+BO1、POMT+BO2和CSMA/CA的端到端傳輸時延隨數據包尺寸變化情況,實驗數據如圖6所示,其中Non-POMT代表非優先數據包情況,而Pri-POMT代表優先數據包情況

圖6 端到端傳輸時延

從圖6可知,提出的POMT協議的端到端傳輸時延低于CSMA/CA。由式(2)可知,端到端傳輸時延包含了隊列時間和每一跳的退避時間。由于CSMA/CA沒有QoS保證,一旦發生碰撞,數據包繼續停留在隊列,等信道空閑時,再擇機傳輸。由于CSMA/CA并沒有對隊列有效管理,碰撞概率較大,從而導致較大的端到端傳輸時延。而POMT協議采取了重傳機制,盡管重傳增加了一定時延,但是有序重傳遠比靠隨機接入信道重傳,更有利于控制時延。值得說明的是:POMT通過業務類型的不同,設置不同的競爭窗口,降低了碰撞概率,減少了重傳次數,這有利于縮短時延。

此外,從圖6可知,對于優先數據包而方言,POMT+BO2的端到端傳輸時延低于POMT+BO1,原因在于:在相比于BO1策略,BO2策略中優先數據包接入信道幾率更高。它們的窗口CW寬度不同。而對于非優先數據包,POMT+BO2的端到端傳輸時延高于POMT+BO1。

3.2.2 平均能量消耗

圖7顯示了POMT和CSMA協議的平均能量消耗情況,其中數據包尺寸為120 byte。從圖7可知,CSMA/CA消耗的能量最高。原因在于:盡管CSMA/CA沒有采取重傳策略,但是它對于一個數據包,它都進行組播,這極大了增加了能耗。而POMT算法對于來自高層級節點的數據包是不進行組播。此外,從圖7可知,POMT+BO2協議與POMT+BO1協議的平均能耗相近。

圖7 能量消耗

3.2.3 數據包傳遞率

在仿真中,統計成功傳輸的數據包數和總的數據包數,便可得到兩個協議的數據包傳遞率如表2所示。

表2 數據包傳遞率

從表2可知,CSMA/CA的數據包傳遞率為96.45%,而POMT算法通過重傳機制可實現100%的傳遞率。對比表2數據不難發現,兩個協議的初始傳輸數據包的成功率相近。而POMT算法通過一次重傳,數據包傳遞成功率接近99%,三次重傳就實現了100%。

3.2.4 碰撞概率

CSMA/CA和POMT協議的碰撞概率如表3所示。從表3可知,CSMA/CA的碰撞概率低于POMT協議。原因在于:相比于POMT協議,CSMA/CA協議從更寬的CW尺寸。相比于POMT+BO2,POMT+BO1協議的非優先業務的碰撞概率更低,但優先業務的碰撞概率增加了。原因在于它們的CW尺寸的不同。

表3 碰撞概率

4 結束語

本文針對無線傳感網絡的異構業務,提出面向異構業務的基于數據包優先權的組播算法POMT。POMT算法引用數據包優先權,再依據這個優先權接入信道,并利用退避算法接入信道。同時,引用重傳機制和兩類ACK包確保可靠傳輸。實驗數據表明,相比CSMA/CA算法,POMT算法的端到端傳輸時延和數據包傳遞率得到有效提高。但POMT算法的數據包碰撞率較高,這也是后期研究工作的重點。

[1] Dargie W,Wen J. A Seamless Handover for WSN Using LMS Filter[C]//Proceedings of the 39th IEEE Conference on Local Computer Networks(LCN),2014:287-288.

[2] 陳東海,李長庚. 基于簇頭功能分化的無線傳感器網絡成簇算法[J]. 傳感技術學報,2015,28(2):244-248.

[3] Papadopoulos G Z,Beaudaux J,Gallais A,et al. T-AAD:Lightweight Traffic Auto-ADaptations for Low-Power MAC Protocols[C]//Proceedings of the 13th IEEE IFIP Annual Mediterranean Ad Hoc Networking Workshop(MED-HOC-NET),2014:79-86.

[4] Recas R,Khaled N,Barrio A A D,et al. Generic Markov Model of the Contention Access Period of IEEE 802.15.4 MAC layer[J]. Digital Signal Processing,2014,33(8):191-205.

[5] Nasser N,Karim L,Taleb T. Dynamic Multilevel Priority Packet Scheduling Scheme for Wireless Sensor Network[J]. IEEE Trans Wireless Commun,2013,12(4):1448-1459.

[6] Collotta M,Scata G,Pau G. A Priority-Based CSMA/CA Mechanism to Support Deadline-Aware Scheduling in Home Automation Applications Using IEEE 802.15.4[M]. Int J of Distributed Sensor Networks,2013.

[7] Papadopoulos G Z,Beaudaux J,Gallais A,et al. T-AAD:Lightweight Traffic Auto-ADaptations for Low-Power MAC Protocols[C]//Proceedings of the 13th IEEE IFIP Annual Mediterranean Ad Hoc Networking Workshop(MED-HOC-NET),2014:79-86.

[8] Narman H S,Hossain M S,Atiquzzaman M. Multi Class Traffic Analysis of Single and Multi-Band Queuing System[C]//Proc IEEE GLOBECOM,2013:1422-1427.

[9] Mahmood M A,Seah W K,Welch I. Reliability in Wireless Sensor Networks:Survey and Challenges Ahead[J]. Computer Networks,2015,79(4):166-187.

[10] Pavkovic B,Batic M,Tomasevic N. The Importance of Crosslayer Considerations in a Standardized WSN Protocol Stack Aiming for Io T:The Internet of Things(Ubiquity Symposium)[J]. ACM Ubiquity,2015,18(8):1-18.

[11] Cross Bow“MICAz”Datasheet. Document Part Number:6020-0060-04 Rev B.