面向異構(gòu)業(yè)務(wù)的基于數(shù)據(jù)包優(yōu)先權(quán)的組播算法*

史玲華,吳松麗

(駐馬店職業(yè)技術(shù)學(xué)院信息工程系,河南 駐馬店 463000)

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

盡管有些應(yīng)用需要高優(yōu)先流量[4],但是基于IEEE 802.15.4標(biāo)準(zhǔn)的WSNs并不支持異構(gòu)流量業(yè)務(wù)。許多研究人員試圖通過單播業(yè)務(wù)滿足WSNs 的QoS。文獻(xiàn)[5]提出基于動(dòng)態(tài)多級優(yōu)先DMP(Dynamic Multi-Level Priority)數(shù)據(jù)包調(diào)度算法。通過DMP算法減少端到端傳輸時(shí)延,進(jìn)而滿足WSNs內(nèi)時(shí)延敏感性流量業(yè)務(wù)。DMP算法引用了時(shí)分多址接入TDMA(Time Division Multiple Access)技術(shù)和多隊(duì)列系統(tǒng)。

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

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

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

1 網(wǎng)絡(luò)模型

考慮分布式的基于簇拓?fù)涞腤SNs網(wǎng)絡(luò)。數(shù)據(jù)流量從信宿節(jié)點(diǎn)流向多播簇群。此外,網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)可以產(chǎn)生不同類型的數(shù)據(jù)流量。簇內(nèi)節(jié)點(diǎn)可通過一跳或多跳建立通信連接。

負(fù)責(zé)簇間通信的節(jié)點(diǎn)稱為主節(jié)點(diǎn)LNs(Leaf Nodes),而在源節(jié)點(diǎn)與LNs間的節(jié)點(diǎn)稱為轉(zhuǎn)發(fā)節(jié)點(diǎn)RNs(Relay Nodes)。在同一個(gè)簇內(nèi)的所有節(jié)點(diǎn)屬于同一個(gè)多播群。此外,假定隊(duì)列尺寸足夠大,鄰居節(jié)點(diǎn)間通信信道是無差錯(cuò)的信道。

考慮的網(wǎng)絡(luò)模型,如圖1所示。一個(gè)信宿節(jié)點(diǎn)S、6個(gè)傳感節(jié)點(diǎn)(A、B、C、D、E、F)。這6個(gè)傳感節(jié)點(diǎn)形成了一個(gè)簇群,并且節(jié)點(diǎn)A為數(shù)據(jù)包源節(jié)點(diǎn)、而節(jié)點(diǎn)E、F為LNs。而其他的節(jié)點(diǎn)(B、C、D)稱為RNs。

此外,依據(jù)節(jié)點(diǎn)到信宿跳數(shù),將簇內(nèi)節(jié)點(diǎn)劃分不同層。源節(jié)點(diǎn)離信宿只有一跳,將其稱為Level 1,而節(jié)點(diǎn)B、C屬于Level 2、節(jié)點(diǎn)D屬于Level 3,而節(jié)點(diǎn)E、F屬于Level 4。

圖1 網(wǎng)絡(luò)模型

2 POMT算法

針對異構(gòu)業(yè)務(wù),POMT算法引用了數(shù)據(jù)包優(yōu)先權(quán)。不同的數(shù)據(jù)包具有不同的轉(zhuǎn)發(fā)權(quán)。首先,引用兩級優(yōu)先權(quán):優(yōu)先和非優(yōu)先。整個(gè)POMT算法由數(shù)據(jù)包分類、隊(duì)列管理和信道優(yōu)先接入和可靠傳輸策略四部分組成。POMT算法框架如圖2所示。

圖2 POMT算法框架

數(shù)據(jù)包分類階段負(fù)責(zé)設(shè)置數(shù)據(jù)包優(yōu)先權(quán);而隊(duì)列管理階段是指如何依據(jù)數(shù)據(jù)包優(yōu)先權(quán)將數(shù)據(jù)包載入堆棧。在信道優(yōu)先接入階段,引用退避算法,給節(jié)點(diǎn)分配接入窗口。最后,通過重傳確認(rèn)機(jī)制確保可靠傳輸。

2.1 數(shù)據(jù)包分類

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

圖3 數(shù)據(jù)包分類標(biāo)志位

一旦接收了數(shù)據(jù)包,節(jié)點(diǎn)就檢測該數(shù)據(jù)包的預(yù)留字段Reserved值。如果是111,則為優(yōu)先數(shù)據(jù)包;否則就是非優(yōu)先數(shù)據(jù)包。

2.2 隊(duì)列管理

POMT算法在同一個(gè)隊(duì)列內(nèi)考慮兩個(gè)堆棧,分別存放優(yōu)先數(shù)據(jù)包和非優(yōu)先數(shù)據(jù)包,如圖4所示。

圖4 堆棧管理

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

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

隊(duì)列管理的目的在于通過時(shí)延敏感業(yè)務(wù)的隊(duì)列時(shí)延,進(jìn)而減少傳輸時(shí)延。端到端的傳輸時(shí)延取決于將數(shù)據(jù)包從源節(jié)點(diǎn)傳輸至目的節(jié)點(diǎn)所需要的傳輸次數(shù)。傳輸次數(shù)越多,時(shí)延越大,反之亦然。為此,POMT算法只轉(zhuǎn)發(fā)來自低層級的數(shù)據(jù)包,這減少了數(shù)據(jù)包被轉(zhuǎn)發(fā)的次數(shù)。

2.3 信道優(yōu)先接入

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

bt=Random(·)×ST

(1)

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

為了使得優(yōu)先數(shù)據(jù)包能夠優(yōu)先接入信道,POMT算法將優(yōu)先數(shù)據(jù)包的窗口CW設(shè)置更窄。因?yàn)榇翱贑W越窄,數(shù)據(jù)包越能優(yōu)先接入信道。

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

圖5 信道接入流程

2.4 可靠傳輸

為了保證數(shù)據(jù)傳輸?shù)目煽啃?引用確認(rèn)重傳機(jī)制。POMT算法引用iACK和eACK兩類確認(rèn)包。其中,iACK包屬于隱晦的確認(rèn)包[10]。將發(fā)送節(jié)點(diǎn)監(jiān)聽到鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)它傳輸?shù)陌?稱為iACK。而eACK包屬于明確的確認(rèn)包。當(dāng)接收節(jié)點(diǎn)接收了數(shù)據(jù)包,就向發(fā)送節(jié)點(diǎn)回復(fù)eACK。

以圖1為例,節(jié)點(diǎn)A向鄰居節(jié)點(diǎn)組播一個(gè)數(shù)據(jù)包,且節(jié)點(diǎn)B、C接收了數(shù)據(jù)包。一旦節(jié)點(diǎn)B、C接收了該數(shù)據(jù)包,就重播該數(shù)據(jù)包。當(dāng)節(jié)點(diǎn)A收到監(jiān)聽到節(jié)點(diǎn)B、C重播了自己轉(zhuǎn)發(fā)的數(shù)據(jù)包,就說明節(jié)點(diǎn)B、C已正確接收了自己轉(zhuǎn)發(fā)的數(shù)據(jù)包。這就隱晦的確認(rèn)包iACK。

如果在規(guī)定時(shí)間內(nèi),節(jié)點(diǎn)A未能收到此iACK包,則節(jié)點(diǎn)A就重傳數(shù)據(jù)包。簇內(nèi)的葉節(jié)點(diǎn)(E、F)收到數(shù)據(jù)包,它們就向查詢數(shù)據(jù)包的源節(jié)點(diǎn),并向它們回復(fù)eACK包。

3 實(shí)驗(yàn)仿真及性能分析

3.1 仿真環(huán)境及性能指標(biāo)

為了更好地分析POMT協(xié)議性能,利用MATLAB建立平臺(tái)。以圖1為仿真網(wǎng)絡(luò)模型。在每輪仿真中,每個(gè)節(jié)點(diǎn)產(chǎn)生10 000個(gè)數(shù)據(jù)包。節(jié)點(diǎn)A、B、C、D以隨機(jī)方式產(chǎn)生優(yōu)先數(shù)據(jù)包和非優(yōu)先數(shù)據(jù)包。數(shù)據(jù)傳輸率為250 kbit/s。依據(jù)文獻(xiàn)[11],節(jié)點(diǎn)在接收模式時(shí)電流消耗為19.7 mA,而傳輸模式時(shí)電流消耗為17.4 mA。

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

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

①端到端傳輸時(shí)延

端到端傳輸時(shí)延指將數(shù)據(jù)包從源節(jié)點(diǎn)傳輸至最后一個(gè)葉節(jié)點(diǎn)所經(jīng)歷的時(shí)間,其主要包括隊(duì)列等待時(shí)間、傳輸時(shí)間和MAC協(xié)議退避時(shí)間。因此,每一跳時(shí)延可定義為:

Dt=Tt+Qt+bt

(2)

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

②平均能耗

一個(gè)節(jié)點(diǎn)所消耗的總能量Etot可表示為:

Etot=NtPtTt+NrPrTr

(3)

③碰撞概率

當(dāng)兩個(gè)或多個(gè)節(jié)點(diǎn)選擇了同一個(gè)窄的退避時(shí)間去接入信道時(shí),它們就會(huì)出現(xiàn)碰撞。這個(gè)碰撞概率取決于競爭節(jié)點(diǎn)數(shù)、CW尺寸和退避算法。碰撞概率等于兩個(gè)或多個(gè)節(jié)點(diǎn)同時(shí)接入信道的次數(shù)與接入信道總次數(shù)的比值。兩個(gè)或多個(gè)節(jié)點(diǎn)同時(shí)接入信道就會(huì)發(fā)生碰撞。

④數(shù)據(jù)包傳遞率

傳輸碰撞或信道干擾等原因均會(huì)導(dǎo)致數(shù)據(jù)包丟失,使得數(shù)據(jù)包傳輸失敗。數(shù)據(jù)包傳遞率等于網(wǎng)絡(luò)內(nèi)成功接收了數(shù)據(jù)包數(shù)與總的所需傳輸?shù)臄?shù)據(jù)包數(shù)之比。

3.2 實(shí)驗(yàn)數(shù)據(jù)分析

首先從總體方案上比較了CSMA/CA和POMT算法的整體性能。CSMA/CA并不支持分類服務(wù)和組播的重傳。而提出的POMT協(xié)議支持?jǐn)?shù)據(jù)包分類以及重傳。表1對比了POMT和CSMA/CA協(xié)議特性。從表1可知,POMT協(xié)議支持組播的QoS服務(wù),這要?dú)w功于業(yè)務(wù)差異、退避算法和重傳機(jī)制。

表1 POMT和CSMA/CA

3.2.1 端到端傳輸時(shí)延

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

圖6 端到端傳輸時(shí)延

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

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

3.2.2 平均能量消耗

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

圖7 能量消耗

3.2.3 數(shù)據(jù)包傳遞率

在仿真中,統(tǒng)計(jì)成功傳輸?shù)臄?shù)據(jù)包數(shù)和總的數(shù)據(jù)包數(shù),便可得到兩個(gè)協(xié)議的數(shù)據(jù)包傳遞率如表2所示。

表2 數(shù)據(jù)包傳遞率

從表2可知,CSMA/CA的數(shù)據(jù)包傳遞率為96.45%,而POMT算法通過重傳機(jī)制可實(shí)現(xiàn)100%的傳遞率。對比表2數(shù)據(jù)不難發(fā)現(xiàn),兩個(gè)協(xié)議的初始傳輸數(shù)據(jù)包的成功率相近。而POMT算法通過一次重傳,數(shù)據(jù)包傳遞成功率接近99%,三次重傳就實(shí)現(xiàn)了100%。

3.2.4 碰撞概率

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

表3 碰撞概率

4 結(jié)束語

本文針對無線傳感網(wǎng)絡(luò)的異構(gòu)業(yè)務(wù),提出面向異構(gòu)業(yè)務(wù)的基于數(shù)據(jù)包優(yōu)先權(quán)的組播算法POMT。POMT算法引用數(shù)據(jù)包優(yōu)先權(quán),再依據(jù)這個(gè)優(yōu)先權(quán)接入信道,并利用退避算法接入信道。同時(shí),引用重傳機(jī)制和兩類ACK包確?？煽總鬏敗?shí)驗(yàn)數(shù)據(jù)表明,相比CSMA/CA算法,POMT算法的端到端傳輸時(shí)延和數(shù)據(jù)包傳遞率得到有效提高。但POMT算法的數(shù)據(jù)包碰撞率較高,這也是后期研究工作的重點(diǎn)。

[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] 陳東海,李長庚. 基于簇頭功能分化的無線傳感器網(wǎng)絡(luò)成簇算法[J]. 傳感技術(shù)學(xué)報(bào),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.