基于优先级的WMSN区分服务路由算法

邓 达，徐 鹏

（成都万联传感网络技术有限公司 成都 610045）

基于优先级的WMSN区分服务路由算法

邓 达，徐 鹏

（成都万联传感网络技术有限公司 成都 610045）

提出一种基于区分服务（Diffserv）的QoS路由算法。该算法利用两种方式保证传输的QoS需求：一是在转发数据包时，以不同的概率公式选择路径；二是使用强占性优先排队模型处理节点缓存中不同类型的数据包。仿真实验显示，该路由算法能保证不同种类数据包的QoS需求，平衡网络的能量消耗，同时延长网络的生存周期。

区分服务； 优先级排队模型； 服务质量； 无线多媒体传感器网络

无线多媒体传感器网络（wireless multimedia sensor network， WMSN）是一种从传统无线传感器网络发展而来的新型网络，能够感知并传输声音、图像、视频剪辑等各种多媒体信息，通常部署在无人值守的环境中独立完成任务，没有基础设施，是一个能源消耗敏感的网络，可以广泛应用于军事、民用和商业领域［1］。WMSN集成了自组织、资源有限等一些传统无线传感器网络的特性，同时给多媒体信息的采集和传输提出了新要求，如硬件设计、节能控制、服务安全性和信息处理［2］等。

与传统无线传感器网络相比，WMSN具有以下特点：1） 更多的能源消耗。传统WSN能源消耗主要发生在无线传输数据，而WMSN需要额外能源进行数据收集和处理；2） 更复杂的处理任务。WMSN需要处理更复杂的任务，如图像压缩编码，分布式视频处理和信息融合。3） 更高的QoS需求。传统的WSN通常为了减少能源消耗而忽略QoS，而WMSN需要很快的实时性、高网络吞吐量来适应不同的应用程序，因此，需要更高的QoS保障［3］。4） 更多的功能和应用。WMSN能感知丰富的多媒体信息，因此适用于细粒度和高精确度的信息环境检测，并能够执行复杂的任务。

简而言之，WMSN需要在有限能量限制下，达到数据延迟尽可能低以及带宽利用率尽可能高的要求。因此，区分服务（DiffServ）是WMSN中最重要的特点之一。比如，在目标检测和跟踪系统中，实时音频数据的传输要求低延迟和小抖动，并允许一定误差；在周期环境检测中，对异常结果的可靠性要求非常高；而在工业控制过程中对实时性和可靠性都有很高要求［4］。

1 相关工作

作为一种特殊类型的无线传感器网络，WMSN支持图像，音频，视频等多媒体信息的传输，需要一定QoS保证。因此，路由协议，QoS保证已成为WMSN的研究热点。

SPEED［5］是一个实时路由协议，它在一定程度上实现了端到端的传输延迟保证，具有网络拥塞控制和负载平衡机制。首先，在节点中交换周围节点传输延迟信息，以获得网络信息。然后在节点通过局部位置和传输速率做出路由选择，并且通过邻居节点反馈机制来保证该网络的传输速率高于全局定义的传输速率阈值［6］。

文献［7］提出了一个基于遗传算法的WMSN路由算法。在该算法中，初始种群是随机产生的，下一代群体通过染色体交叉和变异操作产生。当满足QoS约束时，该算法可以快速收敛到最佳适应度。但它并没有考虑到能源约束的因素。文献［8］设计了一个基于DiffServ的路由算法。该算法对于实时业务通过考虑下一个节点到源节点的跳数来计算选择下一节点转发数据的概率；而对于尽力而为业务，则考虑下一节点的剩余电量。该算法利用非抢占式优先级排队机制，为高优先级的数据包实现了一定的优化，但是这种排队模型对优先级较低的数据包会带来更大的延迟［9］。

文献［10］讨论了一种区别角度的路由算法。在该算法中，节点根据偏转来对邻居节点进行分类，在转发数据时会根据数据流不同的需求选择不同的区域。此外，该算法通过如邻居节点的位置、单跳的通信业务负荷和剩余能量等因素实现区分路由。

SAR［11］是著名的QoS保证的无线传感器网络路由协议。该协议通过基于路由表驱动的多路径方法满足了低能耗和健壮性的要求。在选择路径时同时考虑到每条路径的能量，以及端到端的延迟需求和数据包的优先级。该算法需要维持一个以上的树结构，用以产生从每个源节点到目的节点的多条路径。每个节点建立多条具有不同QoS参数的到达源节点的路径，在发送数据包时，源节点将通过评估路径及数据包的优先级进行转发选择［6］。

2 区分服务模型

在传统IP网络中，QoS提供3种服务模型［12］：

1） 尽力而为的服务模式。应用程序可在不预约、不通知网络的情况下，在任何时间发送任何大小的数据。大多数的互联网应用使用这种服务模式，如HTTP、FTP等。

2） InteServ服务模型。这种服务模型定义在IETF RFC1633中［13］，通过资源预留［14］的方法实现QoS保证。InteServ模型满足多种QoS的要求。在这种模式下，应用程序发送数据包之前，需要通过特殊的QoS信令申请特定服务。应用程序首先通知网络自己的流量参数和特定服务质量的要求，包括带宽、时延等，收到预留资源确认后，开始从网络发送消息。应用程序发送的消息参数需要在自己所描述的流量参数范围之内［15］。

3） DiffServ服务模型。该模型网络体系结构由IETF的DiffServ工作组在1998年10月提出［16］，目的是为简化数据包传输机制和减少网络中内部节点的服务对象［17］。该模型是一个多服务模型，能满足不同QoS要求，无需使用RSVP，即不需要在应用程序发送数据包之前通知路由器预留资源。网络也不需要为每个数据流维持状态，只需要根据每个数据包不同的QoS需求提供特定服务。数据包的QoS可以通过不同的方法指定，如IP数据包的优先级位、数据包的源地址和目的地址等。基于这些信息，网络能够处理数据包分类、流量调整、流量监管及拥塞管理等任务［18］。

3 基于优先级的排队模型

排队模型中存在两种顾客到达系统等待处理方式。当系统处理低优先级顾客时，如果有高优先级的顾客进入系统缓存，系统对高优先级的顾客的应对情况可分为：1） 强占型优先权处理。在这种情形下，系统将立即停止正在进行的工作，直接处理新到达的高优先权的顾客数据包，对于如果系统内只有同类顾客的情况，则按照先到先服务的规则处理；2） 非强占型排队处理。在这种情形下，当优先级别较低的顾客数据在被处理时，如果有高优先级的顾客数据包进入系统缓存，不能强占系统的处理服务，而只能排在低优先权的顾客数据包之前等待处理。

对于强占型优先权排队模型而言，设高优先级的顾客和低优先级的顾客的到达率分别为 λ1和 λ2，Si为第i种类型顾客处理所需的时间，则平均服务时间是：

在系统的第一种类型的顾客的数量为Lq1，则高优先级类型的顾客的总服务时间为：

式中，Wq1是高优先级的顾客在系统中的平均等待时间。

Se是系统的平均剩余服务时间，设平均服务时间=E（S）， 方差为σ，则：

等待服务窗口的平均时间为：

代入式（4），则：

设W1S是系统中第一种类型的顾客的平均停留时间，则：

设WS，1～2是两种类型的顾客的平均停留时间，则：

式中，W2S是第二种类型的顾客在系统内的停留时间。

由于

代入式（10）可得：

则第二种类型的顾客在系统中的平均排队时间为：

而对于非抢占行优先权排队模型，同样设高优先级的顾客和低优先级的顾客的到达率为 λ1和 λ2，用N1（t）和N2（t）分别表示在t时刻，系统中两种顾客的队列长度，显然在这种排队规则的模型下，不是马尔科夫过程，通过状态转移方程组可解得［19］，高优先级的顾客在系统的平均等待时间为：

低优先级顾客的平均等待时间为：

从公式推导可以看出，两种不同优先级的排队模型对于低优先级顾客的等待时间差别不大；而对于高优先级的顾客，如果系统中处理的顾客属于高优先级的类型的个数较多，第二种模型无疑增大了高优先级顾客的服务时间。本文通过蒙特卡洛仿真使用方式来验证这一结论，设两种顾客均使用平均到达时间为0.5 s的随机时间到达系统，系统处理的平均时间为0.1 s，两种优先级的顾客每种20 000个，记录两种情况下的每个顾客在系统中的等待时间。

图1 强占型排队模型顾客等待时间结果

图2 非强占型排队模型顾客等待时间结果

结果显示，在两种顾客输入强度相同的情况下，对于强占型优先权排队模型，高优先权的顾客的等待时间能有较大程度的减少，低优先权的顾客的等待时间虽然较长，但是也在可以接受的范围之内；而对于非强占型优先权排队模型，高优先权的顾客等待时间没能大范围的缩短，另一方面，低优先权的顾客虽然在这种模型下，服务时间不会被强行打断，但从整体来看，相对上一种模型，却也没有得到很大程度的优化。

4 基于蚁群算法的DiffServ路由模型

蚁群算法的思想是模拟自然蚂蚁觅食的过程［20］。该算法在传输过数据包的节点之间留下信息素。当节点i准备发送数据包时，通过下一跳节点j的信息素浓度和发送成本计算选择j节点的发送概率。节点之间的信息素浓度会随着在这条路径上传输数据增多而升高，同时它会随着时间的推移而降低［21］。

这种模型分为如下两个阶段。

1） 梯度的建立

在梯度建立的阶段，按照文献［21］的方式使用全网广播从目的节点发送数据包遍历所有节点，在每个节点建立与之相邻节点的信息素浓度：

式中，hops是PS数据包从源节点到节点j的跳数；N是网络中的总结点数；γ是跳数的重要参数。

2） 发送数据

源节点S开始逐跳发送数据到目的节点D。每个节点在转发数据包之前，首先确定数据包的类型。如果该数据包属于保证服务的类型，如发送视频流或音频流，由于需要确保低延迟，则式（15）和式（16）将被选择用于计算转发数据的概率：

式中，τij是从节点i到j的信息素浓度；ηij是通过此路径发送数据的成本；Wjq1是这种类型的数据包在节点j的平均轮候时间；K是节点j的平均轮候时间的权重系数。通过式（15）和（16）选出的转发路径集中在该节点的平均等待时间，从而确保低延迟。

如果该数据包属于最佳努力类型，如图形或其他一些数据不需要低延迟，但需要较高的数据到达率，将选择式（17）和式（18）计算转发数据的概率：

式中，Ej为节点j的剩余能量；Wjq2为尽力而为类型的数据包在节点j的平均轮候时间。通过式（17）和式（18）选择的路径综合考虑下一跳节点的电源和数据包的平均等待时间。确保数据的到达率，以保持整个网络内的能量平衡。

本模型采用了优先级抢占的排队模型。一旦属于以确保服务的分组到达转发节点，该节点将中断正在进行的属于尽力而为的数据包（如果存在），转而处理高优先级的数据包，而尽力而为的数据包将返回到队列等待转发。

通过上一节的结论可知，两种数据包在节点的平均等待时间分别为式（6）中的W1q和式（12）中的W2q。

每间隔时间Δt，每个节点将计算并更新关于相邻节点的如下信息。

1） Δt后的剩余能量：E（t）= E（0）-nΔE。其中E（0）为初始能量，n是通过此路径的数据包数，ΔE是接收和转发数据包的能量消耗。

2） Δt后改变的信息素浓度：

式中，σ是挥发系数，即在Δt的时间内信息素浓度的减少量；Δτ是通过此路径的每转发一次数据包信息素浓度的增量；n是在此期间经历i、j两点发送的数据包的数量。

在初始时刻，这两种类型的数据包具有相同的概率公式来选择作为下一跳节点：

经过一段时间Δt，选择下一个节点的概率会根据以下因素变化而改变：式（19）所示的信息素的变化；下一个节点的能量水平；式（6）和式（12）所示的下一个节点的平均等待时间。

在间隔Δt后，对于第一种类型，即保证服务类型的数据包，选择下一节点的概率为：

而对于第二种类型，即尽力而为类型的数据包，选择下一节点的概率为：

每隔一段时间，源节点将以类似路径搜索的方式发送广播数据包，以排除电量耗尽的节点。

5 仿 真

用JAVA搭建实验环境模拟该算法。一定数量的传感器节点随机分布在边长为100的正方形区域内，节点的数据传输的范围是半径为10单位长度的圆形区域。每个节点的初始电量为2 000 mAh，接收一个数据包的消耗电量为1 mAh，发送一个数据包为2 mAh，转发一个数据包的延迟为0.1 s。每隔60 s，一个节点将被随机选出作为源节点向网内其他节点发送数据包。发送速率是10个/s数据包。

实验首先考察了该算法对网络规模的支持能力，设定不同数量的节点被部署在同一网络覆盖的区域内。对比SAR算法和文献［7］的Ke路由算法，计算汇聚节点接收100个数据包的延迟。当节点的数量小于200时，不能确保整个网络完全连通，当节点的数目大于500时，分组接收速度不再显著改善。因此，本文选取范围在200～500个节点。从图3可以看出，基于DiffServ的路由算法在各个不同数目的节点的网络规模下均具有良好的性能，其中Ensure of Service数据包在传输延迟上和已被认可和广泛引用的Ke算法接近。

图3 不同规模的网络下接收100个数据包的延迟

图4为用于接收等量的数据包传输延迟。可以看出，属于保证服务类型的数据包的传输延迟和Ke算法比较接近，均短于SAR路由算法。而尽力而为的数据包，其延迟也是在可接受的范围内。可以看出，基于DiffServ的路由算法更适合传输不同类型数据的无线多媒体传感器网络，同时满足多方面的要求。

图4 两种算法接收数据包的时间

图5为网络中节点的寿命。可以看到，使用DiffServ路由算法的节点的生存时间显著长于基于SAR的节点的生存时间。由于没有能量评估和节省机制，文献［7］提出的路有算法也不能有效优化节点的生命周期。另外，从图中也可以看出从第一个节点发生故障的时间到所有节点发生故障的时间很短，这表明该算法具有更好的网络能量利用率。

图5 网络中的节点的失效率

6 结 束 语

作为一种先进的无线传感器网络，无线多媒体传感器网络具有广阔的应用前景。本文提出了一种基于DiffServ的QoS路由算法。该算法通过路径选择和排队模型的方式可以确保不同类型的数据满足相应的QoS需求。此外，通过不同路径的选择，该路由算法提高了网络带宽的利用率，平衡了能源消耗，并延长了网络使用寿命。

［1］ 罗武胜， 翟永平， 鲁琴. 无线多媒体传感器网络研究［J］.电子与信息学报， 2008， 30（6）： 1511-1516. LUO Wu-sheng， ZHAI Yong-ping， LU Qin. Study on wireless multimedia sensor networks［J］. Journal of Electronics & Information Technology， 2008， 30（6）：1511-1516.

［2］ 王汝传， 孙力娟. 无线多媒体传感器网络技术［M］. 北京：人民邮电出版社， 2011. WANG Ru-chuan， SUN Li-juan. Wireless multimedia sensor network［M］. Beijing： Posts & Telecommunications Press，2011.

［3］ SUN Y， MA Hua-dong. The QoS guarantee problem for wireless multimedia sensor networks［J］. Acta Electronica Sinica， 2008， 36（7）： 1412-1420.

［4］ CHANG C K， HUANG J. Video surveillance for hazardous conditions using sensor networks［C］//2004 IEEE International Conference on Networking， Sensing and Control. ［S.l］： IEEE， 2004： 1008-1013.

［5］ HE T， STANKOVIC J A， LU C， et al. SPEED： a stateless protocol for real-time communication in sensor networks［C］//Proceedings 23rd International Conference on Distributed Computing Systems. ［S.l.］： IEEE， 2003： 46-55.

［6］ 李士宁， 滕文星. 无线传感器网络QoS路由研究进展［J］.计算机应用研究， 2008， 25（5）： 1304-1308. LI Shi-ning， TENG Wen-xing. Overview of QoS routing protocols in wireless sensor network［J］. Application Research of Computers， 2008，25（5）： 1304-1308.

［7］ 柯宗武， 李腊元. 无线多媒体传感器网络QoS路由算法研究［J］. 计算机工程与设计， 2008， 29（2）： 360-363. KE Zong-wu， LI La-yuan. QoS routing algorithm for wireless multimedia sensor networks［J］. Computer Engineering and Design， 2008， 29（2）： 360-363.

［8］ 衷柳生. 基于区分服务的无线多媒体传感器网络QoS路由协议［J］. 计算机应用研究， 2010（11）： 4218-4221. ZHONG Liu-sheng. QoS routing protocol for WMSNs based on differentiated services［J］. Application Research of Computers， 2010（11）： 4218-4221.

［9］ 陆传赉. 排队论［M］. 北京： 北京邮电大学出版社， 2009. LU Chuan-lai. Queueing theory［M］. Beijing： Beijing University of Posts and Telecommunications Press， 2009.

［10］ LI Fang-min， FANG Yi-lin， LI Heng， et al. QoS differentiated service routing for wireless multimedia sensor net works［J］. Acta Electronica Sinica， 2010， 38（10）：2322-2328.

［11］ SOHRABI K， GAO J. Protocols for self-organization of a wireless sensor network［J］. IEEE personal communications，2000， 7（5）： 16-27.

［12］ 袁刚， 程时端， 王文东， 等. IP网QoS管理体系框架的研究［J］. 计算机工程与应用， 2004（32）： 168-171. YUAN Gang， CHENG Shi-duan， WANG Wen-dong， et al. Research on IP QoS management architecture［J］. Computer Engineering and Applications， 2004（32）：168-171.

［13］ 兰江涛. 基于多路路由机制的DiffServ/MPLS服务质量研究［D］. 天津： 天津大学， 2005. LAN Jiang-tao. The research for multi-path-route based QoS of DiffServ/MPLS［D］. Tianjin： Tianjin University，2005.

［14］ 刘辰. 基于DiffServ模型的层次化QoS研究［D］. 南京：南京航空航天大学， 2008. LIU Chen. Research on hiberarchy QoS based on DiffServ［D］. Nanjing： Nanjing University of Aeronautics and Astronautics， 2008.

［15］ 王伟杰. 基于DiffServ协议的几种QoS实现机制［J］. 现代计算机， 2002（10）： 43-46. WANG Wei-jie. Several implementation mechanisms of QoS on DiffServ agreement［J］. Modern Computer，2012（10）： 43-46.

［16］ BRADEN R， CLARK D S. Integrated services in the internet architecture： an overview［EB/OL］. ［2014- 03-02］. http：//www.rfc.editor.org/rfc/rfc1633.txt.

［17］ 吴杰， 冯振明， 李衍达. Differentiated Services──Internet中实现QoS的新体系［J］. 清华大学学报（自然科学版），2000， 40（3）： 109-113. WU Jie， FENG Zhen-ming， LI Yan-da. Differentiated services： a new internet architectural model with QoS support［J］. Journal of Tsinghua University （Science and Technology）， 2000， 40（3）： 109-113.

［18］ BLAKE S， BLACK D， CARLSON M， et al. An architecture for differentiated services ［EB/OL］.［2014-03-11］. http：//www.rfc-editor.org/rfc/rfc2475.txt.

［19］ 赵国喜， 陈燕， 薛晓东. 非强占优先权下的M/M/1排队［J］. 大学数学， 2006， 22（1）： 44-48. ZHAO Guo-xi， CHEN Yan， XUE Xiao-dong. M/M/1 queue under nonpreemptive priority［J］， College Mathematics， 2006， 22（1）： 44-48.

［20］ DORIGO M. Optimization， learning and natural algorithms［D］. Italy： Politecnico di Milano， 1992.

［21］ 邓达， 周激流， 林锋. 基于蚁群算法的无线多媒体传感器网络路由研究［J］. 北京理工大学学报， 2011， 31（4）：456-460. DENG Da， ZHOU Ji-liu， LIN Feng. Research into WMSN routing algorithm based on ant colony optimization［J］. Transactions of Beijing Institute of Technology， 2011，31（4）： 456-460.

编 辑 蒋 晓

WMSN DiffServ Routing Algorithm Based on Priority

DENG Da and XU Peng
（Wiselink Sensor Networks CO.， LTD Chengdu 610045）

A quality of service （QoS） routing optimization algorithm based on differentiated services（DiffServ） is proposed. This algorithm improves QoS guarantees of wireless multimedia sensor network （WMSN）in two ways： selecting path through different probabilities when transmitting different kinds of packages， at the same time， adopting a preemptive priority queuing model for the packages in the sensor nodes. In simulation， we compared the method with SAR algorithm in various ways， including supporting capacity of network scale，transmission delay of data packages， energy efficiency and network life. Experimental results show that as far as above-mentioned indexes， the algorithm is superior to the SAR algorithm and the algorithm can guarantee QoS requirement of various data packages with different types.

DiffServ； priority queuing model； quality of service； wireless multimedia sensor network

TP393

A

10.3969/j.issn.1001-0548.2016.02.019

2014 - 11 - 07；

2015 - 12 - 23

国家自然科学基金（60773168）

邓达（1981 - ），男，博士，主要从事无线传感器网络和物联网应用方面的研究.