基于交互式斜率比較的數據包節能傳輸調度*

劉思平， 周悅芝， 張堯學

(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-)，男，湖南衡山人，博士研究生，從事無線通信、低功耗傳輸調度研究。