基于交互式斜率比较的数据包节能传输调度*

刘思平， 周悦芝， 张尧学

(1.清华大学 计算机科学与技术系，北京 100084；2.中南大学 信息科学与工程学院，湖南 长沙 410083)

基于交互式斜率比较的数据包节能传输调度*

刘思平1， 周悦芝1， 张尧学2

(1.清华大学 计算机科学与技术系，北京 100084；2.中南大学 信息科学与工程学院，湖南 长沙 410083)

为了节省无线传感器网络中的数据包传输耗能，提出交互式斜率比较(ISC)算法进行速率控制调度。该算法根据数据包到达和截止曲线，通过不断比较到达点和截止点对应的斜率，得出每个传输段及其速率。所提ISC算法在离线模式下可以实现最低能耗数据包传输，扩展到在线模式后，传输能耗也可以逼近最小值。考虑在1 s时间内传输500个包，所提方法在离线和在线模式下的能耗分别仅为传统方案的0.413 %，0.483 %。

交互式斜率比较;数据包传输； 能耗； 速率控制; 调度

0 引 言

受电池容量等因素的限制，供电是无线传感器网络中的一个关键难题，低能耗技术成为推动其发展的一种必要手段[1，2]。其中，数据包传输能耗占据较大比重[3]，实现节能传输需设计合理的速率控制策略来完成调度。已有工作中，对数据包具有相同到达时刻或相同截止时刻情况的节能传输研究得比较充分[4～6]。其中，文献[6]基于数据包累积曲线，针对这两种特殊场景实现了最低能耗传输调度。然而，一般场景下不同数据包的到达和截止时刻都可能不相同，而且包长和时延限制也可能不同。

本文针对一般场景，利用累积曲线提出交互式斜率比较(interactive slope comparison,ISC)算法得到低能耗传输曲线。具体地，按照时间顺序针对包到达点和包截止点计算斜率，并不断比较最小到达点斜率和最大截止点斜率，如果出现前者小于等于后者的情况，即可得到一个传输段及其速率。离线模式下，所提方法实现了最低能耗传输；在线模式下，传输能耗可以逼近离线模式下的最小值。

1 研究基础

1.1 系统模型

(1)

图1 数据包累积曲线Fig 1 Accumulative curves of data packets

1.2 理论基础

对于单个数据包，实现节能传输需要尽可能降低传输速率[7]，然而任何包的传输速率不能无限制地小。一方面数据包必须在截止时刻前传输完毕；另一方面，如果某个包占用了大量时间就会使得随后的包传输时间很短，这可能反而会增加整体能耗。对于一系列数据包的传输实现节能需采用合适的速率控制策略进行调度。

对于两种特殊场景，文献[6]给出了具体的实现算法得到最低能耗下的各个传输段。对于数据包具有不同到达和截止时刻的一般场景，文献[6]指出最低能耗传输曲线的任何一个传输段要么是在交A(t)先于交D(t)的情况下具有最小斜率，要么是在交D(t)先于交A(t)的情况下具有最大斜率。然而，对于系统实现寻找临界斜率并非易事，同时文献[6]也并未给出具体的算法流程。

2 交互式斜率比较调度

2.1 算法描述

图2 ISC算法实现流程Fig 2 Implementation procedure of ISC algorithm

2.2 在线模式算法扩展

图3 扩展到在线模式的ISC算法实现流程Fig 3 Implementation procedure of ISC algorithm byexpanding online mode

3 仿真结果

表1给出了不同数据包数目下单位比特的传输能耗。随着数据包数目增多，单位比特的传输能耗不断增加。所提ISC算法在离线模式下的能耗最小，而且在线模式下的能耗逼近于离线模式的最小值。当包数目为100时，ISC算法在离线和在线模式下的能耗分别为传统方案的78.9 %,80.6 %；当包数目达到500时，相应能耗传输仅为传统方案的0.413 %,0.483 %。因此，本文算法达到了数据包节能传输的目的。

表1 不同数据包数目下的单位传输能耗
Tab 1 Energy consumptions for transmitting one bit with different numbers of packets

包数目100200300400500传统方案能耗(J/bit)9．94×10-82．20×10-78．20×10-75．40×10-65．16×10-5离线ISC能耗(J/bit)7．84×10-89．86×10-81．25×10-71．62×10-72．13×10-7在线ISC能耗(J/bit)8．01×10-81．01×10-71．32×10-71．75×10-72．49×10-7

4 结 论

针对数据包的传输能耗受速率影响，而速率却由包到达和截止时刻约束，利用数据包累积曲线，本文提出了ISC速率控制调度算法，并将该算法从离线模式扩展到在线模式。仿真结果显示：本文算法可以显著节省数据包传输能耗，考虑在1 s时间内传输500个包，ISC算法在离线和在线模式下的能耗分别仅为传统方案的0.413 %,0.483 %。本文的研究结果对于提高无线传感器网络的能量效率具有重要意义。

[1] Prathap U,Shenoy D P,Venugopal K R,et al.Wireless sensor networks applications and routing protocols:Survey and research challenges[C]∥International Symposium on Cloud and Services Computing,2012:49-56.

[2] Yang S H.Wireless sensor networks:Principles,design and applications[M].London:Springer,2014.

[3] Feng D,Jiang C,Lim G,et al.A survey of energy-efficient wireless communications[J].Communications Surveys & Tutorials,IEEE,2013,15(1):167-178.

[4] Uysal-Biyikoglu E,Prabhakar B,El Gamal A.Energy-efficient packet transmission over a wireless link[J].IEEE/ACM Transactions on Networking,2002,10(4):487-499.

[5] Zafer M,Modiano E.Optimal rate control for delay-constrained data transmission over a wireless channel[J].IEEE Transactions on Information Theory,2008,54(9):4020-4039.

[6] Zafer M,Modiano E.A calculus approach to energy-efficient data transmission with quality-of-service constraints[J].IEEE/ACM Transactions on Networking,2009,17(3):898-911.

[7] Gallager R G.Energy limited channels:Coding,multiaccess and spread spectrum[R].Combridge:MIT,1987.

Energy-efficient packet transmission scheduling based on interactive slope comparison*

LIU Si-ping1, ZHOU Yue-zhi1, ZHANG Yao-xue2

(1.Department of Computer Science and Technology,Tsinghua University,Beijing 100084,China; 2.School of Information Science and Engineering,Central South University,Changsha 410083,China)

In order to save energy consumption of packet transmission in wireless sensor networks,an algorithm of interactive slope comparison(ISC)is proposed for rate-control scheduling.According to the packet arrival and deadline curves，and by comparing slopes corresponding to arrival and deadline points continuously,each transmission segment and its rate are obtained.In offline mode,the proposed ISC algorithm can achieve packet transmission with the minimal energy consumption;expanding in online mode,transmission energy consumption can also approach to the minimal value.Considering transmitting 500 packets within 1 s，the proposed method only consumes 0.413 % and 0.483 % energy of the traditional scheme in offline and online modes,respectively.

interactive slope comparison(ISC);packet transmission; energy consumption; rate control; scheduling

10.13873/J.1000—9787(2015)12—0022—03

2015—03—20

国家国际科技合作专项资助课题项目(2013DFB10070)

TN 92

： A

： 1000—9787(2015)12—0022—03

刘思平(1977-)，男，湖南衡山人，博士研究生，从事无线通信、低功耗传输调度研究。