面向异构业务的基于数据包优先权的组播算法*

史玲华,吴松丽

(驻马店职业技术学院信息工程系,河南 驻马店 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.