无线传感器网络中基于贝叶斯可变频的CSMA/CA算法研究*

罗震钧,张颖江,钟 珞,吕 品

(1.武汉理工大学计算机学院,武汉 430070;2.湖北省食品药品监督检验研究院,武汉 430064;3.湖北工业大学计算机学院,武汉 430068)



无线传感器网络中基于贝叶斯可变频的CSMA/CA算法研究*

罗震钧1,2,张颖江1,3*,钟 珞1,吕 品1

(1.武汉理工大学计算机学院,武汉 430070;2.湖北省食品药品监督检验研究院,武汉 430064;3.湖北工业大学计算机学院,武汉 430068)

针对于在无线传感器网络中多个节点向Sink节点发送数据包造成的延时、丢包、碰撞检测、网络阻塞等问题,在802.15.4协议CSMA/CA算法的基础上提出了一种基于贝叶斯可变频的CSMA/CA算法(BVF-CSMA/CA)。该算法将贝叶斯估值得到的参数区间与CSMA/CA的碰撞检测机制相结合,使传感器节点发送的多数据包能正常与Sink节点实时通讯,采用这种算法减少了碰撞检测、节约了能耗、降低了网络通讯量、延长了网络的生命周期。本文通过使用NS2仿真工具模拟验证了该无线传感器网络的丢包率和能耗,实验结果表明,改进后的算法显著改善了这两个性能指标。

无线传感器网络;贝叶斯公式;可变频率算法;载波监听多路访问/冲突避免策略

无线传感器网络WSNs(Wirless Sensor Networks)以其组网方便、实时监测、使用灵活、采集信息快速等特点被越来越多地应用到各种领域中,例如:航天航空、军事监控、环境监测、医疗卫生、交通运输、智能家庭等等。但是WSNs的能耗问题一直是制约该网络发展的瓶颈。由于无线传感器节点一旦部署就很难更换电池,特别是抛撒到人们不易到达的地方,这些无线传感器节点被部署后其生命周期一般是一次性的。因此,如何节约WSNs的能耗或最大限度延长生存期是WSNs研究的重点。

目前,WSNs的能耗研究热点很多,并且取得了很大的进展。姚玉坤等人从无线传感器的网络层提出了能耗均衡的自供能分簇路由算法,该算法通过对簇头选举机制进行了改进,充分保存与利用补给能量,提高了能量利用性能[1]。Ozlem Durmaz等人提出了多通道的MAC协议,设计了无线传感器网络的最大化吞吐量,其目的为协调传输多个频率频率以提高能源效率[2]。顾云丽等人提出了基于蜂群算法的WSNs任播路由器协议(ABCARP),该协议通过短途和长途侦查蜂查询周边的区域和基站并由采集蜂负责分组传递,通过仿真证明该协议性能较好[3]。Medagliani等人设计并分析了基于WSNs的跨层侦测移动目标系统,研究了通信层的两种介质X-MAC协议和Cas-MAC协议受此启发设计了D-MAC协议,通过仿真验证提出了一个基于节点评价能量消耗水平的网络生命周期模型,并提出了跨层优化配置方法的系统参数[4]等等。从以上文献的研究可以看出WSNs的研究越来越偏向使用算法自动调节节点的参数,以适应环境,从而减少能量消耗和提高效率,也就是使用的方法越来越智能化与自动化,具有智能学习的性质。

本文研究的关注点是减少WSNs在传输中的数据包碰撞,提高网络的利用率;在WSNs中由于节点众多,并且数据传输时间不确定,使用单一频率传输数据不可避免地产生数据碰撞,而WSNs主要采用的是传统的载波监听多路访问/冲突避免策略CSMA/CA(Carrier Sense Multiple Access with Collision Avoidance)。这种策略在大量无线传感器节点向同一个节点实时通讯时会存在一些问题,如:多次碰撞后节点停止传输,丢包率高,网络延迟过长等。故本文为了解决这些问题提出了一种基于数理统计中贝叶斯公式的可变频率算法。

1 相关工作

在WSNs中,传感器节点在数据包传输过程中经常会出现多个节点向同一个节点发送数据包的情况。这就不可避免地产生传输数据冲突、无线频率拥塞、通讯效率的降低等等,结果会导致发送的数据包不断滞留,而新的数据包又不断进入队列等待,发送方与接收方都不能很好地处理数据包,将会有越来越多的数据包阻塞到网络中,情况严重的时候会造成整个WSNs的瘫痪。WSNs使用802.15.4协议的CSMA/CA机制处理这种情况[5],该机制被用来调节传输介质的使用权,所有的传感器节点在传输数据之前会先检测所使用传输媒介是否被占用,如果被占用则延迟一段时间再次检测,该过程反复执行,直到检测传输介质为空闲时则进行数据传输。虽然该机制能有效地减少了传输碰撞,提高了网络的利用率。但是在无线传感器网络中节点的数量一般情况下是比较多的,分布并无规律,发送时间也不能确定等。因此CSMA/CA的3个参数Nb(Number of backoff)(最大值为4)、Cw(Content window length)(最大值为31)和Be(Backoff exponent)(最大值为5)设置的最大值会经常被超过[6]。这样会造成传感器节点耗费大量能量来计算等待时间、数据包被大量丢失、网络延迟也不断加剧等等。另外,很多传感器节点部署的目的是要求实时感知物理世界的,这就降低了WSNs的实时性。

为解决这些问题,最近几年国内外的专家学者都提出了对CSMA/CA的改进算法。Rejane[7]提出了基于MAC协议的CSMA/CA优化算法,该算法改进了传输时间和约束机制,根据GTS的不同大小需求引入相应的竞争周期以保证时隙分配,并提高网络的性能。Ashrafuzzaman[8]提出了基于WSNs的时隙CSMA/CA最优能量和吞吐量的操作区域,利用模型寻找到最佳的时隙工作点参数,控制带宽及减少碰撞达到节约能源延长生命周期。Mario[9]研究的是基于支持期限调度优先级的CSMA/CA机制,其特点是通过单调速率(RM)来保证时隙配置等。以上方法都是利用最优化参数来提高效率,但WSNs网络是经常变化的,缺少网络重新变化后如何优化的研究。Iwanicki[10]则是利用动态分配频谱的技术来将限定好的频谱分配给需要使用的传感器节点,但是缺乏智能学习功能,容易造成频谱的浪费。文献[11-13]都提出了在WSNs中引入贝叶斯的变化公式对使用的算法进行相应的改进,用于降低网络能耗、减少路径损耗、故障检测、数据融合等。本文则是结合以上两种策略来对IEEE802.15.4协议MAC层的CSMA/CA机制改进,用于提高整个网络的性能。

2 可变频率算法的分析及研究

2.1 贝叶斯公式数学原理分析及使用

贝叶斯公式就是用来计算后验概率的公式,它利用搜集到的信息对原来判断进行修正。即已知道结果发生的条件下,推断原因发生的可能性大小。这种结果发生在事件后的概率称为后验概率,用来计算后验概率的公式称为贝叶斯公式[14]。具体描述如下:

假设事件A是事件B发生的原因,且先验概率P(A)已知,那么事件A的后验概率P(A|B)为式(1)所示:

(1)

WSNs节点发送数据包时,发送数据的节点一般都是随机发送数据的,各个节点发送数据的事件被认为都是互不干扰的独立事件,则可以看作事件A,另一节点接收数据可被看作事件B,发送数据事件A是接收数据事件B发生的原因。P(B|A)则被认为发送节点发送数据后接收节点正常接收到数据的概率。具体表示如图1所示。

图1 WSNs节点发送接收贝叶斯公式使用原理图

在上图中A1,A2,…,Ai表示为节点1,2,……,i发送数据包的事件,B表示为节点0接收数据包的事件,则P(Bj|Ai)表示为节点i发送数据后B节点接收到的概率,那么用贝叶斯公式所求的P(Ai|Bj)表示为B点接收到数据后Ai节点发出数据的概率(注:图1中i=j,如果B节点扩展后当B节点不唯一时则i与j不相同)。如果知道A1,A2,…,Ai各节点在一段时间t内发送数据的概率后,则通过相应的算法流程对发送数据概率最合适的节点采取可变频率策略用于减少数据包在WSNs中的冲突。

2.2 可变频率节点的选取

根据文献[15],IEEE 802.15.4定义了两个物理层的频率标准,即2.4 GHz频段和868/915 MHz。前者是免许可的标准,后者则是欧美的频段,文中主要采用的是2.4 GHz频段。频率公式如式(2)所示:

Fc=2405+5(k-11)k=11,12……26

(2)

从上述公式上可以看出该频段共有16个频率,也就是意味着接收节点最大可以变换16个频率。但如果存在传感器数据通讯节点的数目是远大于16个,或者远小于16个,则可变频率应选取最恰当的节点用于频率变换,其目的为既要保证正常数据传输,又要使占用的资源最小。

为求得最恰当的传感器节点用于可变频率,则需要根据贝叶斯方法估计总体参数。假设节点发送数据事件符合正态分布。那么式(1)可以写成如式(3)所示:

(3)

设随机变量参数θ∈A,则θ也为正态分布,且θ～N(μ,φ)其中方差φ已知道,期望μ未知,那么转换为求期望μ范围,又设x∈B,式(3)可以写成如式(4)所示:

P(θ/x)∞π(θ)P(x/θ)

(4)

在上述公式中,∞为正比符号,x是传感器节点B的观测值,这些值是可以得到的。则当θ变化时P(x/θ)就是θ的函数,可写为l(θ/x)。这个函数被叫做似然函数,式(4)可以变化为式(5)所示:

P(θ/x)∞π(θ)l(θ/x)

(5)

即估计出期望μ,那么:

(6)

假设取到正态分布N(μ0,φ0)为μ的先验分布,则由式(6)可得到:

π(μ)=(2πφ0)-1/2exp{-(μ-μ0)22φ0}

(7)

再根据式(5)得到μ的后验分布:

P(μ/x)∞π(μ)l(μ/x)=π(μ)P(x/μ)

(8)

即:

(9)

(10)

由以上的推导可以得到期望μ的置信区间和方差φ,则根据这两个参数来选取可变频率的节点。式(2)已经确定在一个Sink节点的WSNs中,可用频率数为16,那么通过节点选取算法选择合适的节点变频。具体算法步骤如下:

Step 4:反复重复Step 2和Step 3的循环,直到第μn的置信区间与上一个μn-1的置信区间相同或者频段数都被使用(也就是找到第15个分频节点),跳出循环,算法结束。

2.3 可变频率算法流程

在WSNs的IEEE 802.15.4协议中,CSMA/CA是作为重要的冲突避免算法,不少算法是对该协议进行改进,用于降低能耗[17]。本文使用的是基于贝叶斯可变频的CSMA/CA算法BVF-CSMA/CA(Bayes Variable Frequency CSMA/CA),其改进原理是当CSMA/CA的竞争机制失败后或满足一定条件时,使用基于贝叶斯可变频的选取算法,选择合适的节点和频率进行变频传输。该算法的其具体流程如图2所示。

图2 可变频率算法流程图

在图2中,当数据发生碰撞时开始判定是否使用CSMA/CA策略,如果使用CSMA/CA策略,则判定当该策略在后退次数Nb或后延时间的长度Cw都达到最大值或同时同步传输的节点数目n在两个以上(碰撞的概率最大)。符合这些条件时使用可变频率节点选取算法,利用贝叶斯公式选取可变频率的节点,求出相应的参数通过可变频率选取算法并通过式(2)分配相应的频率。分配频率后等待一定时间ti-1(其中i要大于等于1)后,判定是不是数据成功传输,如果不能成功传输则跳转到判定是否使用可变频率算法步骤,继续可变信道节点的选取。反之,则该算法结束。

3 实验仿真及结果分析

3.1 仿真环境与参数配置

本文仿真环境主要是构建药检云计算平台智能化实验室为目的,这种实验室能采集和监控实验室的一切信息,为药检人员远程访问、数据溯源、药品评价模型等提供条件,其利用无线传感器网络感知药检实验室内部的温度、湿度、光照、洁净度或监控药品检验检测仪器设备的视频、图片等数据信息(如色谱仪、液相、电子天平等的视频信息)。本文以药检实验室为模拟环境,实验室的标准区域一般为60 m×30 m的范围。实验仪器与实验环境中布置无线传感器节点用于采集感知到的信息,Sink节点安置在中间用于收集其他节点的信息。以这样环境布置的无线传感器网络如图3所示。

图3 基于无线传感器网络的药检实验室环境

NS2(Network Simulator 2)是一种开源的、免费的、针对网络技术的软件模拟平台,其功能强大、涉及到网络的所有方面,并且仿真数据能被得到认可[18]。本文采用该软件的NS2.34版本作为仿真实验软件来分析验证该算法的性能,其仿真参数如下表1所示。

本文的实验选取的16个发送节点其中有4个是仿真药检实验室的固定发送数据流(温度、湿度、光照、洁净度),其余12个使用函数random()随机发送数据包(用于采集药检仪器的视频、图片等信息),接收节点为汇聚节点Sink,仿真时间根据实验需要设置。运行NAM得到的仿真图如图4所示。

表1 仿真参数配置表

图4 仿真拓扑结构图

3.2 仿真实验过程与结果分析

本文的主要对比使用CSMA/CA算法、CSMA/CA-TDMA算法[19]、BVF-CSMA/CA算法的性能。对这3种算法做理论上的分析,BVF-CSMA/CA算法是在CSMA/CA算法的基础上改进的,前者的使用条件是在后者的参数已经达到最大值或者网络已经负载过重时采用该策略,从这种角度分析可以得出前者比后者更有优势。CSMA/CA-TDMA算法是通过对超帧中竞争的直接分配和数据时隙的相互申请来实现整个网络的竞争,其特点是最优化利用网络资源,但在多节点向同一节点发送数据包的环境下,网络中的时隙资源都可能会被占用,这也会造成拥塞,而且算法中所用的广播信息会增加网络中的负荷。

本文的实验是通过分析无线传感器网络的两个重要指标——丢包率与能耗,用来判定这3种算法的优劣。在药检实验室模拟场景中对3种算法比较,实验数据通过仿真工具NS2的trace功能获取,仿真实验后3个算法分别得到3个后缀名为tr的数据文件,使用gawk程序提取相关内容(如:时间、节点、能量、数据包的数量等),然后再使用gnuplot绘制图形工具对得到的数据绘图。实验的丢包数对比如图5所示,在图5中,设置20 s的仿真时间,对比丢包数可以看出使用CSMA/CA和BVF-CSMA/CA算法在发送400个数据包的时候接收到的数据包大约都为50%,而CSMA/CA-TDMA算法则利用最优化的时隙资源,把数据包的接收率达到近90%,在这个阶段CSMA/CA-TDMA算法的性能最优,CSMA/CA和BVF-CSMA/CA算法性能几乎一样。随着发送数据包总量的逐渐增大BVF-CSMA/CA的优势逐渐显示出来,而CSMA/CA-TDMA在数据包达到2000个以上时则接收数稳定在1600个附近,说明网络资源利用率已经不能再优化了。整个网络数据包发送总量达到3200个数据包时BVF-CSMA/CA接收率大概为74%,丢包率为16%,而CSMA/CA-TDMA的接收率为50%多一点,丢包率接近50%;CSMA/CA的接收率则大约为32%,丢包率为68%。由以上分析结果可以得出结论随着发送数据包数量的增加,BVF-CSMA/CA算法比另外两种算法在数据包接收率方面的优势更加明显。

图5 CSMA/CA、BVF-CSMA/CA、CSMA/CA-TDMA的发送包与接收包

图6 CSMA/CA、BVF-CSMA/CA、CSMA/CA-TDMA能量消耗比较图

为进一步验证算法的有效性,对3种算法的能耗做比较。同样设置20 s的仿真时间,同时设置节点的能量为无限大(防止节点死亡),仿真结果如图6所示。在该图中,在整个网络数据包量达到1100个数据包之前,CSMA/CA算法能耗最小,因为另外两种算法还未达到最优化。当数据包的数量在1600左右时,CSMA/CA-TDMA算法的利用率最高,因此能耗最低。但之后BVF-CSMA/CA算法随着Sink节点的变频频率的使用,优势逐渐显示出来,而CSMA/CA-TDMA算法由于资源已经不能再优化了,接收的数据包较少,因此能耗增加较快,从图5中也可以反映出来。到最后在发送3200个数据包时BVF-CSMA/CA算法比CSMA/CA算法的能耗降低了近20%,比CSMA/CA-TDMA算法的能耗也有优势。

4 结论

本文在802.15.4协议的CSMA/CA算法基础上提出了基于贝叶斯可变频的CSMA/CA算法。该算法基于贝叶斯公式,利用802.15.4协议制定的16个可变频段用于节点变频。在WSNs多节点向同一节点传输数据包的条件下,通过仿真实验对比验证CSMA/CA、BVF-CSMA/CA、CSMA/CA-TDMA 3种算法的丢包率和能耗两个性能参数,得到的结论是BVF-CSMA/CA算法显著地提高WSNs网络的性能。从而节约了整个WSNs的能源,减少了数据碰撞,保证了数据的实时传输并延长了整个网络的生命周期。

[1] 姚玉坤,王冠,任智,等. 能耗均衡的自供能无线传感器网络分簇路由算法[J]. 传感技术学报,2013,26(10):1420-1425.

[2]Ozlem Durmaz,Lodewijk,Pierre,Paul. MC-LMAC:A multi-channel MAC protocol for wireless sensor networks[J]. Ad hoc networks,2010,9(5):73-94.

[3]顾云丽,徐昕,杜杰,等. 基于蜂群算法的无线传感器网络任播路由协议[J]. 传感技术学报,2013,26(4):564-569.

[4]Paolo Medagliani,Gianluigi Ferrari,Vincent Gay. Cross-layer design and analysis of WSN-based mobile target detection systems[J]. Ad Hoc Networks,2013,11:712-732.

[5]Muffy Calder,Michele Sevegnani,Modelling IEEE 802. 11 CSMA/CA RTS/CTS with stochastic bigraphs with sharing[J]. Formal Aspects of Computing,2014,26(2):537-561.

[6]Chiara. Performance Analysis of IEEE 802. 15. 4 Beacon-Enabled Mode[J]. IEEE Transactions on Vehicular Technology,2010,59(4):2031-2045.

[7]Rejane Dalce,Van Den,Thierry Val. Optimization of a CSMA/CA based MAC protocol designed for confined WSNS[C]//2012 International Conference on Wireless Communications in Under-ground and Confined Areas,ICWCUCA 2012:1109-1113.

[8]Ashrafuzzaman Kazi,Energy and throughput optimal operating region in slotted CSMA/CA based WSN[J]. IEEE Communications Letters,2012,16(9):1524-1527.

[9]Mario Collotta,Gianfranco Scata,Giovanni Pau,A Priority-Based CSMA/CA Mechanism to Support Deadline-Aware Scheduling in Home Automation Applications Using IEEE 802. 15. 4[J]. Inter-national Journal of Distributed Sensor Networks,2013,22(4):1155-1169.

[10]Iwanicki K,Steen M V,Multi-hop cluster hierarchy maintenance in wireless sensor networks:A case for gossip-based protocols[C]//The Sixth European Conference on Wireless Sensor Networks,Cork,Ireland,Feb,2009:102-117.

[11]齐华,王恒,刘军. 可变周期的基于贝叶斯估计的TPSN改进算法[J]. 传感技术学报,2013,26(3):407-410.

[12]Lau Bill C P,Ma Eden W M,Chow Tommy W S,Probabilistic fault detector for Wireless Sensor Network[J]. Expert Systems with Applications,2014,41(1):3703-3711.

[13]张品,董为浩,高大冬. 一种优化的贝叶斯估计多传感器数据融合算法[J]. 传感技术学报,2014,27(5):643-648.

[14]刘次华、万建平. 概率论与数理统计[M]. 北京:高等教育出版社,2003:24-29.

[15]IEEE Computer Society. IEEE Standard for Local and metropolitan area networks-Part15. 4:Low-Rate Wireless Personal Area Networks(LR-WPANs)[S]. New York:IEEE,2011:146-150.

[16]叶中行、王蓉华、徐晓玲等. 概率论与数理统计[M]. 北京:北京大学出版社,2010:254-284.

[17]Mohammad,Iman,Abbaspour. An adaptive CSMA/TDMA hybrid MAC for energy and throughput improvement of wireless sensor networks[J]. Ad Hoc Networks. 2011:1297-1304.

[18]方陆平、刘世华、陈盼等. NS-2网络模拟基础与应用[M]. 北京:国防工业出版社,2008.

[19]任昊翔,郭达伟,邵凝宁,等. 一种新型的无竞争的基于TDMA的MAC协议[J]. 传感技术学报,2013,26(1):89-94.

罗震钧(1985-),男,汉族,工程师,武汉理工大学计算机学院在职博士研究生,湖北省食品药品监督检验研究院情报信息中心科员,主要从事云计算、智能计算及无线传感器网络能耗方面的研究,26111221@qq.com;

张颖江(1959-),男,汉族,湖北工业大学教授,武汉理工大学博士生导师,主要从事无线网络协议、无线传感器网络能耗和安全、自动控制的研究,yjjzhang@mail.hbut.edu.cn;

钟珞(1957-),男,汉族,武汉理工大学教授,博士生导师,主要从事智能技术与智能系统,软件工程,知识发现与数据挖掘的研究;

吕品(1973-),女,汉族,武汉工程大学副教授,武汉理工大学博士研究生,主要从事数据挖掘,社会网络与网络信息分析的研究,lpwhict@163.com。

ResearchonBayesVariableFrequencyCSMA/CAAlgorithminWirelessSensorNetworks*

LUOZhenjun1,2,ZHANGYingjiang1,3*,ZHONGLuo1,LÜPin1

(1.School of Computer Science and Technology,Wuhan University of Technology,Wuhan 430070 China;2.Hubei Institute for Food and Drug Control,Wuhan 430064,China;3.Hubei University of Technology,Wuhan 430068,China)

In the process of transmitting data packets from more than one node to the Sink node,there are many problems in wireless sensor networks,such as,packet delay,packet loss,collision detection,network congestion and so on. This paper proposes a new Bayes variable frequency CSMA/CA algorithm(BVF-CSMA/CA)that is based on the 802.15.4 protocol of CSMA/CA algorithm. This algorithm combines the Bayes interval estimation and collision detection mechanism of CSMA/CA so as to realize the real-time transmission of each node sent by data packets to the Sink node. Thereby it reduces the collision detection,saves energy,reduces the network traffic and prolongs the network life cycle. This paper verifies the packet loss rate and energy consumption by using the NS2 simulation tool and the experimental results show that the improved algorithm has significantly improved the two performance parameters.

wireless sensor networks;bayes formula;variable frequency algorithm;CSMA/CA

项目来源:国家自然科学基金青年基金项目(61103136);中国食品药品检定研究院科学检验精神研究项目的子课题项目(2012X1-029)

2014-04-04修改日期:2014-07-29

10.3969/j.issn.1004-1699.2014.09.020

TP391

:A

:1004-1699(2014)09-1269-06