-
无线多媒体传感器网络(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) 强占型优先权处理。在这种情形下,系统将立即停止正在进行的工作,直接处理新到达的高优先权的顾客数据包,对于如果系统内只有同类顾客的情况,则按照先到先服务的规则处理;2) 非强占型排队处理。在这种情形下,当优先级别较低的顾客数据在被处理时,如果有高优先级的顾客数据包进入系统缓存,不能强占系统的处理服务,而只能排在低优先权的顾客数据包之前等待处理。
对于强占型优先权排队模型而言,设高优先级的顾客和低优先级的顾客的到达率分别为λ1和λ2,Si为第i种类型顾客处理所需的时间,则平均服务时间是:
$${{\bar{S}}_{i}}=E({{S}_{i}})=\frac{1}{{{\mu }_{i}}}$$ (1) 设 ${{\rho }_{i}}={{\lambda }_{i}}/{{\mu }_{i}}={{\lambda }_{i}}{{\bar{S}}_{i}}$ ,则系统内的平均服务时间为:
$$\overline{S}=E(S)=\frac{{{\lambda }_{1}}}{\lambda }E({{S}_{1}})+\frac{{{\lambda }_{2}}}{\lambda }E({{S}_{2}})=\frac{1}{\lambda }({{\rho }_{1}}+{{\rho }_{2}})=\frac{\rho }{\lambda }$$ (2) 在系统的第一种类型的顾客的数量为Lq1,则高优先级类型的顾客的总服务时间为:
$${{\bar{S}}_{1}}{{L}_{q1}}=\frac{{{L}_{q1}}}{{{\mu }_{1}}}={{\rho }_{1}}{{W}_{q1}}$$ (3) 式中Wq1,是高优先级的顾客在系统中的平均等待时间。
${{\overline{S}}_{e}}$ 是系统的平均剩余服务时间,设平均服务时间$\overline{S}=E(S)$,方差为σ,则:
$${{\overline{S}}_{e}}=E({{S}_{e}})=\frac{E({{S}^{2}})}{2E(S)}=\frac{{{\sigma }^{2}}+{{(\overline{S})}^{2}}}{2\overline{S}}$$ (4) 等待服务窗口的平均时间为:
$${{W}_{q1}}={{\rho }_{1}}{{W}_{q1}}+\rho {{\overline{S}}_{e}}$$ (5) 代入式(4),则:
$${{W}_{q1}}=\frac{\lambda E({{S}^{2}})}{2}\frac{1}{1-{{\rho }_{1}}}=\frac{\lambda \frac{2}{\mu }}{2(1-\frac{\lambda }{\mu })}=\frac{{{\lambda }_{1}}}{\mu (\mu -{{\lambda }_{1}})}$$ (6) 设WS1是系统中第一种类型的顾客的平均停留时间,则:
$${{W}_{S1}}={{W}_{q1}}+\frac{1}{\mu }=\frac{1}{\mu -{{\lambda }_{1}}}$$ (7) 设WS,1-2是两种类型的顾客的平均停留时间,则:
$$({{\lambda }_{1}}+{{\lambda }_{2}}){{W}_{S,1\sim 2}}={{\lambda }_{1}}{{W}_{S1}}+{{\lambda }_{2}}{{W}_{S2}}$$ (8) $${{W}_{S2}}=(1+\frac{{{\lambda }_{1}}}{{{\lambda }_{2}}}){{W}_{S,1\sim 2}}-\frac{{{\lambda }_{1}}}{{{\lambda }_{2}}}{{W}_{S1}}$$ (9) 式中,Ws2是第二种类型的顾客在系统内的停留时间。
由于
$${{W}_{S,1\sim 2}}=\frac{1}{\mu -\lambda }=\frac{1}{\mu -({{\lambda }_{1}}+{{\lambda }_{2}})}$$ (10) 代入式(10)可得:
$${{W}_{S2}}=(1+\frac{{{\lambda }_{1}}}{{{\lambda }_{2}}})\frac{1}{\mu -({{\lambda }_{1}}+{{\lambda }_{2}})}-\frac{{{\lambda }_{1}}}{{{\lambda }_{2}}}\frac{1}{\mu -{{\lambda }_{1}}}$$ (11) 则第二种类型的顾客在系统中的平均排队时间为:
$$\begin{align} & {{W}_{q2}}={{W}_{S2}}-\frac{1}{\mu }= \\ & (1+\frac{{{\lambda }_{1}}}{{{\lambda }_{2}}})\frac{1}{\mu -({{\lambda }_{1}}+{{\lambda }_{2}})}-\frac{{{\lambda }_{1}}}{{{\lambda }_{2}}}\frac{1}{\mu -{{\lambda }_{1}}}-\frac{1}{\mu } \\ \end{align}$$ (12) 而对于非抢占行优先权排队模型,同样设高优先级的顾客和低优先级的顾客的到达率为λ1和λ2,用N1(t)和N2(t)分别表示在t时刻,系统中两种顾客的队列长度,显然在这种排队规则的模型下 $\{{{N}_{1}}(t),{{N}_{2}}(t)\}$ ,不是马尔科夫过程,通过状态转移方程组可解得[19],高优先级的顾客在系统的平均等待时间为:
$${{W}_{q1}}=\frac{{{L}_{q1}}}{{{\lambda }_{1}}}=\frac{{{\lambda }_{1}}({{\lambda }_{2}}+\mu )}{\mu (\mu -{{\lambda }_{1}})}$$ (13) 低优先级顾客的平均等待时间为:
$$\begin{align} & {{W}_{q2}}=\frac{{{L}_{q2}}}{\lambda 2}=\frac{{{\lambda }_{2}}[\lambda _{1}^{2}+{{\lambda }_{1}}({{\lambda }_{2}}-\mu )+{{\mu }^{2}}]}{\mu {{\lambda }_{2}}(\mu -{{\lambda }_{1}})(\mu -{{\lambda }_{1}}-{{\lambda }_{2}})}= \\ & \frac{\lambda _{1}^{2}+{{\lambda }_{1}}({{\lambda }_{2}}-\mu )+{{\mu }^{2}}}{\mu (\mu -{{\lambda }_{1}})(\mu -{{\lambda }_{1}}-{{\lambda }_{2}})} \\ \end{align}$$ (14) 从公式推导可以看出,两种不同优先级的排队模型对于低优先级顾客的等待时间差别不大;而对于高优先级的顾客,如果系统中处理的顾客属于高优先级的类型的个数较多,第二种模型无疑增大了高优先级顾客的服务时间。本文通过蒙特卡洛仿真使用方式来验证这一结论,设两种顾客均使用平均到达时间为0.5s的随机时间到达系统,系统处理的平均时间为0.1s,两种优先级的顾客每种20000个,记录两种情况下的每个顾客在系统中的等待时间。
结果显示,在两种顾客输入强度相同的情况下,对于强占型优先权排队模型,高优先权的顾客的等待时间能有较大程度的减少,低优先权的顾客的等待时间虽然较长,但是也在可以接受的范围之内;而对于非强占型优先权排队模型,高优先权的顾客等待时间没能大范围的缩短,另一方面,低优先权的顾客虽然在这种模型下,服务时间不会被强行打断,但从整体来看,相对上一种模型,却也没有得到很大程度的优化。
-
蚁群算法的思想是模拟自然蚂蚁觅食的过程[20]。该算法在传输过数据包的节点之间留下信息素。当节点i准备发送数据包时,通过下一跳节点j的信息素浓度和发送成本计算选择j节点的发送概率。节点之间的信息素浓度会随着在这条路径上传输数据增多而升高,同时它会随着时间的推移而降低[21]。
这种模型分为如下两个阶段。
1) 梯度的建立
在梯度建立的阶段,按照文献[21]的方式使用全网广播从目的节点发送数据包遍历所有节点,在每个节点建立与之相邻节点的信息素浓度:
$$\tau (i,j)=1-{{(\frac{\text{hops}}{N})}^{^{\gamma }}}$$ (15) 式中,hops是PS数据包从源节点到节点j的跳数;N是网络中的总结点数;γ是跳数的重要参数。
2) 发送数据
源节点S开始逐跳发送数据到目的节点D。每个节点在转发数据包之前,首先确定数据包的类型。如果该数据包属于保证服务的类型,如发送视频流或音频流,由于需要确保低延迟,则式(15)和式(16)将被选择用于计算转发数据的概率:
$${{P}_{ij}}=\frac{{{[{{\tau }_{ij}}(t)]}^{\alpha }}{{[{{\eta }_{ij}}]}^{\beta }}}{\sum\limits_{n\in {{v}_{a}}}{{{[{{\tau }_{in}}(t)]}^{\alpha }}{{[{{\eta }_{in}}]}^{\beta }}}}$$ (16) $${{\eta }_{ij}}=\frac{{{K}_{{}}}}{{{W}_{jq1}}}$$ (17) 式中,τij是从节点i到j的信息素浓度;ηij是通过此路径发送数据的成本;Wjq1是这种类型的数据包在节点j的平均轮候时间;K是节点j的平均轮候时间的权重系数。通过式(15)和(16)选出的转发路径集中在该节点的平均等待时间,从而确保低延迟。
如果该数据包属于最佳努力类型,如图形或其他一些数据不需要低延迟,但需要较高的数据到达率,将选择式(17)和式(18)计算转发数据的概率:
$${{{P}'}_{ij}}=\frac{{{[{{\tau }_{ij}}(t)]}^{{{\alpha }'}}}{{[{{{{\eta }'}}_{ij}}]}^{{{\beta }'}}}}{\sum\limits_{n\in \text{allowed}}{{{[{{\tau }_{in}}(t)]}^{{{\alpha }'}}}{{[{{{{\eta }'}}_{in}}]}^{{{\beta }'}}}}}$$ (18) $${{{\eta }'}_{ij}}=\frac{{{{{K}'}}_{1}}}{{{E}_{j}}}+\frac{{{{{K}'}}_{2}}}{{{W}_{jq2}}}$$ (19) 式中,Ej为节点j的剩余能量;Wjq2为尽力而为类型的数据包在节点j的平均轮候时间。通过式(17)和式(18)选择的路径综合考虑下一跳节点的电源和数据包的平均等待时间。确保数据的到达率,以保持整个网络内的能量平衡。
本模型采用了优先级抢占的排队模型。一旦属于以确保服务的分组到达转发节点,该节点将中断正在进行的属于尽力而为的数据包(如果存在),转而处理高优先级的数据包,而尽力而为的数据包将返回到队列等待转发。
通过上一节的结论可知,两种数据包在节点的平均等待时间分别为式(6)中Wq1的和式(12)中Wq2的。
每间隔时间Δt,每个节点将计算并更新关于相邻节点的如下信息。
1) Δt后的剩余能量:E(t)= E(0)-nΔE。其中E(0)为初始能量,n是通过此路径的数据包数,ΔE是接收和转发数据包的能量消耗。
2) Δt后改变的信息素浓度:
$${{\tau }_{ij}}(t+\Delta \tau )=(1-\sigma ){{\tau }_{ij}}+n\Delta \tau $$ (20) 式中,σ是挥发系数,即在Δt的时间内信息素浓度的减少量;Δτ是通过此路径的每转发一次数据包信息素浓度的增量;n是在此期间经历i、j两点发送的数据包的数量。
在初始时刻,这两种类型的数据包具有相同的概率公式来选择作为下一跳节点:
$${{\left\{ \begin{align} & {{P}_{ij}}=\left[ \frac{{{\tau }_{ij}}(0)}{\sum\limits_{n\in \text{allowed}}^{{}}{{{\tau }_{in}}(0)}} \right] \\ & {{\tau }_{ij}}=(i-\text{hops}/n)\lambda \\ \end{align} \right.}^{\alpha }}$$ (21) 经过一段时间Δt,选择下一个节点的概率会根据以下因素变化而改变:式(19)所示的信息素的变化;下一个节点的能量水平;式(6)和式(12)所示的下一个节点的平均等待时间。
在间隔Δt后,对于第一种类型,即保证服务类型的数据包,选择下一节点的概率为:
$${{P}_{ij}}=\frac{{{[{{\tau }_{ij}}(t+\Delta t)]}^{\alpha }}{{\left[ \frac{K}{{{W}_{jq1}}} \right]}^{\beta }}}{\sum\limits_{n\in \text{allowed}}{{{[{{\tau }_{in}}(t+\Delta t)]}^{\alpha }}{{\left[ \frac{K}{{{W}_{nq1}}} \right]}^{\beta }}}}$$ (22) 而对于第二种类型,即尽力而为类型的数据包,选择下一节点的概率为:
$$\left\{ \begin{align} & {{{{P}'}}_{ij}}=\frac{{{[{{\tau }_{ij}}(t+\Delta t)]}^{{{\alpha }'}}}{{[{{{{\eta }'}}_{ij}}]}^{{{\beta }'}}}}{\sum\limits_{n\in \text{allowed}}{{{[{{\tau }_{in}}(t+\Delta t)]}^{{{\alpha }'}}}{{[{{{{\eta }'}}_{in}}]}^{{{\beta }'}}}}} \\ & {{{{\eta }'}}_{ij}}=\frac{{{{{K}'}}_{1}}}{{{E}_{j}}(0)-n\Delta E}+\frac{{{{{K}'}}_{2}}}{{{W}_{jq2}}} \\ \end{align} \right.$$ (23) 每隔一段时间,源节点将以类似路径搜索的方式发送广播数据包,以排除电量耗尽的节点。
WMSN DiffServ Routing Algorithm Based on Priority
-
摘要: 提出一种基于区分服务(Diffserv)的QoS路由算法。该算法利用两种方式保证传输的QoS需求:一是在转发数据包时,以不同的概率公式选择路径;二是使用强占性优先排队模型处理节点缓存中不同类型的数据包。仿真实验显示,该路由算法能保证不同种类数据包的QoS需求,平衡网络的能量消耗,同时延长网络的生存周期。
-
关键词:
- 区分服务 /
- 优先级排队模型 /
- 服务质量 /
- 无线多媒体传感器网络
Abstract: 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. -
[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.