劉思平， 周悅芝， 張堯?qū)W

(1.清華大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系，北京 100084；2.中南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長沙 410083)

基于交互式斜率比較的數(shù)據(jù)包節(jié)能傳輸調(diào)度*

劉思平1， 周悅芝1， 張堯?qū)W2

(1.清華大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系，北京 100084；2.中南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長沙 410083)

為了節(jié)省無線傳感器網(wǎng)絡(luò)中的數(shù)據(jù)包傳輸耗能，提出交互式斜率比較(ISC)算法進(jìn)行速率控制調(diào)度。該算法根據(jù)數(shù)據(jù)包到達(dá)和截止曲線，通過不斷比較到達(dá)點(diǎn)和截止點(diǎn)對應(yīng)的斜率，得出每個(gè)傳輸段及其速率。所提ISC算法在離線模式下可以實(shí)現(xiàn)最低能耗數(shù)據(jù)包傳輸，擴(kuò)展到在線模式后，傳輸能耗也可以逼近最小值。考慮在1 s時(shí)間內(nèi)傳輸500個(gè)包，所提方法在離線和在線模式下的能耗分別僅為傳統(tǒng)方案的0.413 %，0.483 %。

交互式斜率比較;數(shù)據(jù)包傳輸； 能耗； 速率控制; 調(diào)度

0 引 言

受電池容量等因素的限制，供電是無線傳感器網(wǎng)絡(luò)中的一個(gè)關(guān)鍵難題，低能耗技術(shù)成為推動(dòng)其發(fā)展的一種必要手段[1，2]。其中，數(shù)據(jù)包傳輸能耗占據(jù)較大比重[3]，實(shí)現(xiàn)節(jié)能傳輸需設(shè)計(jì)合理的速率控制策略來完成調(diào)度。已有工作中，對數(shù)據(jù)包具有相同到達(dá)時(shí)刻或相同截止時(shí)刻情況的節(jié)能傳輸研究得比較充分[4～6]。其中，文獻(xiàn)[6]基于數(shù)據(jù)包累積曲線，針對這兩種特殊場景實(shí)現(xiàn)了最低能耗傳輸調(diào)度。然而，一般場景下不同數(shù)據(jù)包的到達(dá)和截止時(shí)刻都可能不相同，而且包長和時(shí)延限制也可能不同。

本文針對一般場景，利用累積曲線提出交互式斜率比較(interactive slope comparison,ISC)算法得到低能耗傳輸曲線。具體地，按照時(shí)間順序針對包到達(dá)點(diǎn)和包截止點(diǎn)計(jì)算斜率，并不斷比較最小到達(dá)點(diǎn)斜率和最大截止點(diǎn)斜率，如果出現(xiàn)前者小于等于后者的情況，即可得到一個(gè)傳輸段及其速率。離線模式下，所提方法實(shí)現(xiàn)了最低能耗傳輸；在線模式下，傳輸能耗可以逼近離線模式下的最小值。

1 研究基礎(chǔ)

1.1 系統(tǒng)模型

(1)

圖1 數(shù)據(jù)包累積曲線Fig 1 Accumulative curves of data packets

1.2 理論基礎(chǔ)

對于單個(gè)數(shù)據(jù)包，實(shí)現(xiàn)節(jié)能傳輸需要盡可能降低傳輸速率[7]，然而任何包的傳輸速率不能無限制地小。一方面數(shù)據(jù)包必須在截止時(shí)刻前傳輸完畢；另一方面，如果某個(gè)包占用了大量時(shí)間就會(huì)使得隨后的包傳輸時(shí)間很短，這可能反而會(huì)增加整體能耗。對于一系列數(shù)據(jù)包的傳輸實(shí)現(xiàn)節(jié)能需采用合適的速率控制策略進(jìn)行調(diào)度。

對于兩種特殊場景，文獻(xiàn)[6]給出了具體的實(shí)現(xiàn)算法得到最低能耗下的各個(gè)傳輸段。對于數(shù)據(jù)包具有不同到達(dá)和截止時(shí)刻的一般場景，文獻(xiàn)[6]指出最低能耗傳輸曲線的任何一個(gè)傳輸段要么是在交A(t)先于交D(t)的情況下具有最小斜率，要么是在交D(t)先于交A(t)的情況下具有最大斜率。然而，對于系統(tǒng)實(shí)現(xiàn)尋找臨界斜率并非易事，同時(shí)文獻(xiàn)[6]也并未給出具體的算法流程。

2 交互式斜率比較調(diào)度

2.1 算法描述

圖2 ISC算法實(shí)現(xiàn)流程Fig 2 Implementation procedure of ISC algorithm

2.2 在線模式算法擴(kuò)展

圖3 擴(kuò)展到在線模式的ISC算法實(shí)現(xiàn)流程Fig 3 Implementation procedure of ISC algorithm byexpanding online mode

3 仿真結(jié)果

表1給出了不同數(shù)據(jù)包數(shù)目下單位比特的傳輸能耗。隨著數(shù)據(jù)包數(shù)目增多，單位比特的傳輸能耗不斷增加。所提ISC算法在離線模式下的能耗最小，而且在線模式下的能耗逼近于離線模式的最小值。當(dāng)包數(shù)目為100時(shí)，ISC算法在離線和在線模式下的能耗分別為傳統(tǒng)方案的78.9 %,80.6 %；當(dāng)包數(shù)目達(dá)到500時(shí)，相應(yīng)能耗傳輸僅為傳統(tǒng)方案的0.413 %,0.483 %。因此，本文算法達(dá)到了數(shù)據(jù)包節(jié)能傳輸?shù)哪康摹?/p>

表1 不同數(shù)據(jù)包數(shù)目下的單位傳輸能耗
Tab 1 Energy consumptions for transmitting one bit with different numbers of packets

包數(shù)目100200300400500傳統(tǒng)方案能耗(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 結(jié) 論

針對數(shù)據(jù)包的傳輸能耗受速率影響，而速率卻由包到達(dá)和截止時(shí)刻約束，利用數(shù)據(jù)包累積曲線，本文提出了ISC速率控制調(diào)度算法，并將該算法從離線模式擴(kuò)展到在線模式。仿真結(jié)果顯示：本文算法可以顯著節(jié)省數(shù)據(jù)包傳輸能耗，考慮在1 s時(shí)間內(nèi)傳輸500個(gè)包，ISC算法在離線和在線模式下的能耗分別僅為傳統(tǒng)方案的0.413 %,0.483 %。本文的研究結(jié)果對于提高無線傳感器網(wǎng)絡(luò)的能量效率具有重要意義。

[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

國家國際科技合作專項(xiàng)資助課題項(xiàng)目(2013DFB10070)

TN 92

： A

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

劉思平(1977-)，男，湖南衡山人，博士研究生，從事無線通信、低功耗傳輸調(diào)度研究。