无线传感器网络公平性算法的分析

李 庚，范 菁，王万升，向昌松

（云南民族大学云南省高校无线传感器网络重点实验室，云南昆明650500）

无线传感器网络公平性算法的分析

李 庚，范 菁，王万升，向昌松

（云南民族大学云南省高校无线传感器网络重点实验室，云南昆明650500）

为了保证无线传感器网络具有较好的公平性，同时拥有较高的吞吐量，提出了一种基于公平性的多数据包发送调度算法.在该算法中，数据包是按照信源识别的方式来存放的.距离网关一跳范围外的节点，采用改进的最大最小公平性调度算法；距离网关一跳范围以内的节点，每次成功竞争信道后，若节点内各个堆栈都有数据包，则节点一次发送多个数据包，每个堆栈都发送一个.否则，节点等待空闲一段时间.通过对比仿真实验，网络具有较好的公平性以及较高的吞吐量.

无线传感器网络；调度算法；公平性

由于传感器节点随机分布在网络中，节点所在的位置不同，各个节点得到的网络服务质量（QOS）会有一定的差别；靠近网关的节点，容易获取信道，有利于传输数据，占据较多的资源，相对的服务质量较好；而远离网关的节点会受到靠近网关的节点相应的压迫，难以占据信道，不利于传输数据，相对的服务质量比较差；因此，常常导致网络资源分配的不公平，网络整体的服务质量不理想.在多跳的无线传感器网络中，如何让各节点公平合理地共享无线信道资源，成为研究热点之一［1-4］.

国内外已有许多调度算法可以实现多跳网络内数据流的公平性.Izumikawa等［5］提出了一种基于数据流的调度算法，无线传感器节点中的数据包被分为源节点产生的数据包和来自其他节点的转发的数据包，数据包以轮询的方式进行发送，只有当各节点负载相同时，网络才具有较好的公平性；Naouel等［6］专注于空间／时分多址（STDMA），提出了在WMNs中的一个MAC层的数据包调度算法，将传输权力分配给链路，使空间使用最大化；Giang等［7］提出了在链路层上循环排队的概率控制（PCRQ），该方法中数据包按概率进入堆栈，循环选择堆栈来传输，数据包按概率离开堆栈；Nand等［8］针对Impre-cise Extended Inter-Frame Space（EIFS）问题中EIFS值和期望值不匹配产生的不公平和吞吐量降低，提出了一个加强的载波感应（enhanced car-rier sensing，ECS），将错误类型区分开来，相应地延迟传输，解决了这个问题；Cheng等［9］提出了自己的拥塞公平性策略（CCF），针对多对一的树形拓扑结构网络，在发生拥塞时，采用拥塞控制能够确保节点公平的传输数据，同时提出了基于子节点数目的传输调度算法，实现数据流之间的公平传输；Wakuda等［10］提出了在多跳无线传感器网络中，基于最大最小公平性准则的一种数据包调度算法，当节点要发送数据时，节点通过计算得到的概率，选择一定时间内节点内发送数据最少的堆栈来发送数据包；如果节点所选的堆栈没有数据，节点延迟发送，不参与信道竞争，让其他节点能够获取信道资源.

本文在分析已有的最大最小公平性调度算法的基础上，提出了一种基于公平性的多数据包发送调度算法.算法对于距离网关一跳范围外的节点，先以计算得到的概率进行堆栈选择，再检测对应下一跳节点堆栈的缓冲区是否已满，若未满，节点才竞争信道，使得节点能够有效发送数据.否则，节点进入等待状态，空闲一段时间.由于数据直接传输给网关的一跳节点之间的公平性没有得到控制，因此距离网关一跳范围内的节点，每次成功竞争信道后，若节点内各个堆栈都有数据，则节点一次发送多个数据包，每个堆栈都发送一个.否则，节点不发送数据包，进入等待状态，空闲一段时间，不参与信道竞争，让其他节点能够获取信道资源.仿真实验表明，采用本算法网络能够获得较好的公平性及较高的吞吐量.

1 最大最小公平性调度算法

在最大最小公平性调度算法［10］中，节点以CSMA机制竞争信道，通过计算得到的概率选择堆栈发送，使发送数据次数少的堆栈，以较大概率被选择，控制经过它的数据流，实现网络的公平性.算法模型如图1.

图1中，每个堆栈里的数据流Flow（n）都有与之对应的权重管理器W（n）和活动计数器A（n），来实现堆栈管理和数据调度.

在堆栈管理中，当节点收到一个数据包时，如果与产生该数据包的信源节点相对应的堆栈存在的话，那么数据包将要传入该堆栈，该堆栈相对应的活动计数器设为默认值.否则，要建立一个新的堆栈与之相对应，并且初始化.在数据调度中，节点以计算得到的概率p（k）从堆栈中选择一个，作为下一个发送数据包的堆栈，w（k）为堆栈Q（k）（1≤k≤n）的权重值.

当堆栈Q（k）被选定且堆栈内有数据包时，wk置为w，一个数据包从堆栈内离开.否则，堆栈对应的活动计数器自减1，并且节点延迟发送，等待一个固定时间twait，重复上面的步骤.如果所有的堆栈都没有数据，所有对应的权重管理器的值加1，但是权重值不能超过上限值wmax.当堆栈Q（k）的活动计数值减为0，移除堆栈Q（k）.当节点有一段时间没有收到某个节点产生的数据包时，对应那个节点的堆栈的权重管理器的值加1.

2 多数据包发送调度算法

在大规模无线传感器网络中，通常采用树状拓扑结构.对于距离网关一跳范围内的节点，能够直接把数据传送给网关，但这些节点之间无法通过控制数据流的发送，来实现数据流之间的公平性.因此，本文提出了一种基于公平性的多数据包发送调度算法.

在多数据包发送的调度算法中，每一个源节点产生的数据包在传输过程中，经过中转节点时都会产生一个与源节点相对应的堆栈来储存数据包.这些节点内的数据，是按照信源识别的方式来存放的.对于距离网关一跳范围外的节点，采取改进的最大最小公平性调度算法；对于距离网关一跳范围内的节点，每次成功竞争信道后，若节点内各个堆栈都有数据，则节点一次发送多个数据包，每个堆栈都发送一个.否则，节点不发送数据包，进入等待状态，不参与信道竞争，让其他节点能够获取信道资源.

如图2所示，对于距离网关一跳范围外的节点，每个堆栈里的数据流Flow（n）都有与之对应的权重管理器W（n）和活动计数器A（n），来实现堆栈管理和数据调度.节点侦听DIFS后，先检测节点内有无数据，节点有数据再以概率进行堆栈选择，选择的堆栈内若有数据，再检测下一跳节点对应缓冲区是否已满，若未满，节点才参与竞争、传输数据；否则，节点延迟发送，等待一段时间，不参与信道竞争，让其他节点能够获取信道资源.节点以概率的方式选择一定时间内节点中发送数据最少的堆栈，来发送数据包，不会出现某个数据流独占信道，该公平性调度算法能够有效控制经过它的数据流，均衡数据流的传输，实现节点内数据流之间的公平性，同时提高吞吐量.

对于网关一跳范围内的节点，它们能够直接把数据传送给网关.这些节点之间的数据流却没有有效的调度算法来控制，无法保证这些数据流之间的公平性.因此，在这些节点内，每个堆栈里的数据流Flow（n）都有与之对应的状态管理器S（n）和活跃计数器AC（n）.

当节点收到一个数据包时，如果与该数据包的信源节点相对应的堆栈存在的话，那么数据包将要传入该堆栈，该堆栈相对应的状态管理器S（n）和活跃计数器设为默认值.如果与该包的信源节点相对应的堆栈不存在，那么节点要建立一个新的堆栈与之相对应，并且初始化.当堆栈未满的时候，到达的数据包就传进堆栈.否则丢弃该数据包.

节点的数据调度通过状态管理器S和活跃计数器AC来实现.节点每次成功竞争信道后，检测节点内各个堆栈，如果都有数据，则节点一次发送多个数据，每个堆栈都发送一个.否则，节点不发送数据，进入等待状态，不参与信道竞争，让其他节点能够获取信道资源.假如调度器管理n个堆栈，堆栈M（k）（1≤k≤n）的状态管理器的值为s（k），那么s（k）＝1表示堆栈内有数据，s（k）＝0表示堆栈内没有数据；如图2，节点成功竞争信道后，检测各个堆栈的状态值s（k），如果都为1，则节点一次发送多个数据包，各个堆栈发送一个，数据包从堆栈内离开.数据包离开后的堆栈内，若没有数据包，那么对应的状态值s（k）置为0，否则，状态值s（k）为0的堆栈对应的活跃计数器的值自减1，节点延迟发送，等待一个固定时间Twait，重复上面的步骤.当堆栈M（k）的活跃计数值减为0，移除堆栈M（k）.

3 仿真结果及分析

为了将本文算法与已有算法的网络性能进行评估比较，建立算法0：最大最小公平性调度算法；算法1：多数据包发送调度算法.

在无线传感器网络中，大量的节点随机分布在监测区域内，通常形成的都是是树状拓扑结构，从中选取一个树枝状的子网络来建立模型，如图3所示.

使用Matlab对上述2种算法进行仿真，基本的仿真实验参数见表1.MAC层采用IEEE 802.11b DCF的RTS／CTS机制，节点感知距离220m，传输距离120m，节点间距离100m.其中，活跃计数器默认值设为6，活动计数器默认值为6，权重计数器上限值为22.

将节点的负载从100 kbit／s逐渐提高到2 000 kbit／s，考察节点在不同负载下的网络公平性以及吞吐量.进行10次实验，仿真结果取平均值，每次仿真时间为120 s.

所有节点在相同负载下，网络的公平性用公平性指标来衡量，

表1 基本的仿真参数

Xi是在无线链路中，没有数据包丢失的数据流端到端的吞吐量，是所有数据流平均端到端的吞吐量.

从图4～5中可以看出，负载很低时，所有的数据包都能到达网关，吞吐量达到上限，公平性为1.网络的公平性以及吞吐量随节点负载的增加而发生变化.

当节点负载为1 400 kbit／s时，各节点产生的数据流到达网关的吞吐量，见表2.

对于算法0，随着节点的负载提高，节点的传输任务加重，尤其是节点WN3.虽然节点WN1、WN2、WN3传输到网关的吞吐量差不多，但是由于各个节点内的数据流的数量不同，所有数据流之间的吞吐量相差很大，导致网络整体的公平性能下降；但是节点内的数据流之间，依然有较好的公平性.

表2 节点负载为1 400 kbit／s时网关数据流的吞吐量

对于算法1，随着节点的负载提高，节点的传输任务加重，虽然节点内数据流之间的公平性与算法0相比有所下降，但是很小，不明显，网络整体的公平性能一直很好.而且节点WN2、WN3一次可以发送多个数据包，可以有效降低每个数据包的平均访问时间，使得网络的吞吐量得到提高.

4 结语

本文针对无线传感器网络的公平性问题进行分析，在此基础上对最大最小调度算法进行改进，并提出了一种基于公平性的多数据包发送调度算法.针对简单的网络模型，使用Matlab对算法进行仿真.仿真结果表明，提出的算法具有更好的网络公平性，同时网络吞吐量较高.在网络范围内，任意节点或者同等条件下的数据流能够被公平合理的对待，不会有明显的差异.

［1］YIGITEL M A，INCEL O D，ERSOY C.QoS-aware MAC protocols for wireless sensor networks：A survey［J］.Computer Networks，2011，55：1982-2004.

［2］CARVALHO M M，GARCIA-LUNA-ACEVES J J.Delay analysis of IEEE 802.11 in single-hop networks［C］／／Proceedings of the 11th IEEE International Conference on Network Protocols（ICNP′03）.IEEE Press，2003：146-155.

［3］范菁，谢建斌，王万升，等.DCF及其自适应竞争窗口改进算法的仿真研究［J］.计算机工程与设计，2008，29（13）：3298-3302.

［4］TAY Y C，CHUA K C.A capacity analysis for the IEEE 802.11 MAC protocol［J］.ACM／Baltzer Wireless Networks，2001（7）：159-171.

［5］IZUMIKAWA H，ISHIKAWA H，SUGIYAMA K.Scheduling algorithm for fairness improvement among subscribers in multi-hop wireless networks［J］.Electronics and Communications in Japan（Part I：Communications），2007，90（4）：11-22.

［6］NAOUEL B S，JEAN-PIERRE H，A fair scheduling for wireless mesh networks［C］／／A Fair Scheduling for Wireless Mesh Networks.IEEE Press，2005：81-88.

［7］GIANG P T，NAKAGAWA K.Improvement of fairness by PCRQ scheduling in multi-Hop wireless ad hoc networks［C］／／Proceedings of Asia-Pacific Symposium on Queueing Theory and Network Application.IEEE Press，2007：339-348.

［8］LIZ S，GUPTA N A K.ECS：An enhanced carrier sensing mechanism for wireless ad Hoc networks［J］.Computer Communications，2005，28：1970-1984.

［9］CHENG Tien-ee，BAJCSY R.Congestion control and fairness for many-to-one routing in sensor networks［C］／／ACM SenSys.IEEE Press，2004：148-161.

［10］WAKUDA K，KASAHARA S，TAKAHASHI Y.A packet scheduling algorithm for max-min fairness in multi-Hop wireless LANS［J］.Computer Communications，2009，32：1437-1444.

（责任编辑 庄红林）

Analysis of fairness-based algorithm in wireless sensor networks

LI Geng，FAN Jing，WANG Wan-sheng，XIANG Chang-song
（Key Laboratory of Wireless Sensor Networks in Universities of Yunnan Province，Yunnan Minzu University，Kunming 650500，China）

In order to guarantee good fairness and high throughput in wireless sensor networks，this research gives an analysis of the existing fairness scheduling algorithm and proposes a multiple packet-scheduling algorithm based on fairness.The node is within one hop to Gateway，after every successful getting the channel in the competition with other nodes，each stack in the node has a packet，and the node will send multiple packets.Otherwise，the node will be waiting for a period of time.Through a simulationexperiment，the network has good fairness and high throughput.

wireless sensor network；scheduling algorithm；fairness

TP393

A

1672-8513（2014）06-0400-04

2014-04-04.

国家自然科学基金（61163061，60963026）；云南省应用基础研究计划项目（2011FZ174）.

李庚（1988-），男，硕士研究生.主要研究方向：无线传感器网络。

范菁（1976-），女，博士研究生，教授，硕士生导师.主要研究方向：无线传感器网络.