基于數據卸載策略的能量優化方法在移動代理路徑規劃中的應用

史霄波，魯建宇，王文燁，阮航，朱瑄，3

（1.華中科技大學，湖北武漢430074；2.河南師范大學，河南新鄉453007；3.華中師范大學，湖北武漢430079）

研究與開發

基于數據卸載策略的能量優化方法在移動代理路徑規劃中的應用

史霄波1，2，魯建宇1，王文燁1，阮航1，朱瑄1，3

（1.華中科技大學，湖北武漢430074；2.河南師范大學，河南新鄉453007；3.華中師范大學，湖北武漢430079）

提出了移動代理數據卸載策略，對無線傳感器網絡中現有移動代理規劃路徑進行優化，根據卸載規則決定是否將數據分組分離通過優化的卸載路徑傳遞，卸載數據的移動代理通過原路徑訪問數據源節點。使用移動代理經典算法IEMF（itinerary energy minimum for first-source-selection）進行大量的仿真實驗，結果顯示，提出的數據卸載策略能有效地解決數據源節點能量消耗過快的問題，延長數據源節點的生存期。

數據卸載；移動代理；路徑規劃；無線傳感器網絡

1 引言

無線傳感器網絡（wireless sensor network，WSN）能在復雜地形、危險地區部署大規模的傳感器，通過自組網的方式進行通信和聚合信息，借助無人機等其他無人操控設備共同構建網絡，在天氣預測、災情監測、軍事、交通管理、野外火災監測［1，2］等領域應用廣泛。傳感器節點能量和計算能力有限，網絡中部分傳感器節點能量消耗完會影響數據采集的準確性，所以減少傳感器節點的能量消耗，延長傳感器網絡的生存期成為傳感器網絡研究的熱點之一［3-6］。

WSN中傳感器節點由3類組成：匯聚（sink）節點；感知信息的數據源傳感器節點；轉發數據的中繼傳感器節點。匯聚節點派出移動代理（mobile agent，MA）通過無線多跳的方式依次訪問路徑中所有的數據源傳感器節點，移動代理對數據源傳感器感知的數據經過壓縮融合，帶回sink節點。參考文獻［7］中將WSN中移動代理的設計分成4部分：結構設計、路徑規劃、中間件設計、移動代理的協同操作，其中移動代理的路徑規劃設計是移動代理設計的核心問題。移動代理路徑規劃算法包括單移動代理路徑規劃（single-mobile agent itinerary planning，SIP）算法，如IEMF/IEMA［7，8］、LCF/GCF［9］，多移動代理路徑規劃（multi-mobile agent itinerary planning，MIP）算法：GA-MIP［10］、TBID［11］、NOID［12］、BST/MST［13］、DSG-MIP［14］等。這些移動代理路徑規劃算法規劃路徑時，都以減少總的能量消耗和數據時延為目標，但是隨著MA訪問數據源傳感器數量增多，攜帶的數據量增大，MA經過傳感器節點時消耗的能量增大，路徑遠端的數據源節點能量消耗遠遠大于路徑近端的數據源節點能量消耗，數據源節點能量消耗的不均衡會造成網絡生存期縮短。

本文針對以上問題提出數據卸載技術［15，16］，對單移動代理和多移動代理路徑規劃算法規劃路徑進行優化，均衡數據源傳感器節點的能量消耗，提高數據源傳感器節點的能量效率，延長網絡的生存期。

2 無線傳感器網絡移動代理路徑規劃

2.1 移動代理在WSN中的應用

WSN中的n個監測點位置的傳感器作為數據源節點，所有傳感器節點初始能量已知，設置一個能量不受限制的匯聚節點。異常情況發生時，sink節點派出MA按照規劃好的路徑以無線多跳的方式訪問所有n個監測點的數據源傳感器節點，將數據源傳感器節點執行監測任務感知數據帶回sink節點。

MA從sink節點派出時只有固定的部分包括處理模塊和路徑地址信息等，經過多跳到達數據源傳感器節點，將數據源節點感知的數據添加到MA中，以后MA經過多跳每到達一個數據源節點時添加數據源節點感知的數據。假設n個數據源傳感器初始能量相同，每一個傳感器處理單位長度數據能量消耗相同，第1個數據源傳感器生存期最長，能量效率最高，第2個數據源傳感器次之，第n個數據源傳感器生存期最短，能量效率最低。

為MA訪問n個數據源傳感器節點規劃出優化路徑，要協同考慮總能量消耗、數據源節點能量消耗、時延等因素。

2.2 數據融合模型

MA訪問第2～n個數據源傳感器節點時，為了減少數據冗余，需要將傳感器節點感知的數據和MA傳遞的數據進行融合。ρ表示數據的融合率，0≤ρ≤1，ρ=1表示數據完全融合，ρ=0表示數據沒有融合，假設所有數據源節點的融合率相同。MA訪問第k個數據源節點后的大小為：

2.3 能量消耗模型

根據第2.2節對MA訪問傳感器的能耗進行估算，主要包括數據感知、數據壓縮、數據融合、通信能量消耗等。MA的路徑｛t→Vi（n）→t}=｛t，｛Srci1，Srci2，…，Srcin}，t}，表示MA從sink節點t出發訪問所有的n個傳感器節點后返回t。每一個節點的通信能量消耗包括接收MA的能量消耗、控制能量消耗和發送MA的能量消耗。定義ectrl為表示節點數據通信的控制能量消耗，Mrx和Mtx分別接收和發送一個數據位的能量消耗，lrx和ltx分別表示節點接收的數據大小和發送的數據大小。一個數據源節點的通信能量消耗表示為：

其中，Mp表示數據源節點感知和壓縮一個數據位的能耗，Mg表示融合一個數據位的能耗，數據源節點k的能量消耗表示為：

3 移動代理數據卸載策略

WSN中n個數據源傳感器是MA路徑中的關鍵節點，位于路徑最后的數據源節點n能量消耗En最大。移動代理數據卸載是在原規劃路徑不變的情況下，進行數據源節點數據的卸載操作，將數據源節點轉發其他傳感器感知數據和數據融合的功能卸載到中繼節點，減少數據源傳感器節點處理的數據量，降低數據源節點k的能量消耗Ek。

3.1 一次數據卸載

未進行數據卸載時的移動代理數據傳遞如圖1所示。數據源節點k-1發送的數據經過多跳到達數據源節點k；將節點k感知的數據進行壓縮后和接收到的k-1節點傳遞的數據融合發送到下一跳節點a。

圖1 移動代理數據未卸載

數據源節點k能量消耗：

k后中繼節點a能量消耗：

如圖2所示移動代理在第k個數據源節點進行數據卸載操作，數據源節點k-1發送的數據在到達k前before_offload節點b處進行數據卸載；卸載數據后的MA頭部發送到數據源節點k，對k感知的數據進行壓縮后和MA頭部一起發送到路徑規劃的after_offload節點a；數據由節點b發送到offload節點o；節點o轉發數據到節點a，在節點a進行數據的融合操作。

數據源節點k能量消耗為：

圖2 移動代理數據卸載

k后中繼節點a能量消耗為：

k數據轉發節點o能量消耗為：

使用數據卸載策略，數據源節點k節省的能量消耗為：

k使用數據卸載策略增加的總能量消耗：

采用移動代理數據卸載策略的數據源傳感器節點能量消耗等于移動代理訪問第一個數據源傳感器節點的能量消耗Ek＇=E1，也就是使用數據卸載策略之后，每一個進行數據卸載的數據源傳感器節點的能量消耗相同，達到了能耗均衡的目的，從而延長數據源傳感器節點的生存期。但是使用數據卸載策略會增加總能量消耗，增加的總能量消耗分散在中繼節點a和卸載節點o。

3.2 卸載節點選擇

數據卸載要為進行數據卸載前的k-1個數據源感知的數據選擇卸載路徑，數據卸載的能量消耗主要來源于k前before_offload節點b轉發數據到卸載節點o，卸載節點o轉發數據到k后after_offload節點的能量消耗。尋找使卸載能量消耗值最小的傳感器節點o，作為數據卸載節點，卸載節點選擇算法偽代碼見算法1。使用算法1尋找k卸載節點時分兩種情況：before_offload節點b和after_offload節點a的傳輸半徑R之內的傳感器節點集合交集不空時，返回值s為卸載節點o，增加的總能量消耗為Et=（Eka＇-Eka）-（Ek-Ek＇）+Eko；before_offload節點b和after_offload節點a的傳輸半徑R之內的傳感器節點集合交集為空時，返回值s為卸載節點o，需要再次調用卸載節點選擇算法，將節點o作為before_offload節點b，尋找下一個卸載節點o，直到滿足第一種情況，增加的總能量消耗Et=（Eka＇-Eka）-（Ek-Ek＇）+m·Eko，m是尋找到的卸載節點的個數。

算法1卸載節點選擇算法

初始化offload_before［］/b傳輸半徑R內的傳感器

初始化offload_after［］/a傳輸半徑R內的傳感器

ifoffload_before［］∧offload_after［］≠

｛distance=0；

while（s in（offload_before［］∧offload_after［］∧s not in source［］））

｛ifd（k，s）＞distance/d（k，s）表示k與s之間的距離

｛d（k，s）→distance}}}

else

｛distance=max_value；

while（s in offload_before［］∧s not in source［］）

｛if d（a，s）＜distance

d（a，s）→distance}

}

returns

3.3 數據卸載實現

MA按照路徑規劃算法規劃的路徑遷移，對路徑中的每一個數據源節點，判斷是否采用MA數據卸載策略，也就是在不更改路徑的情況下執行MA數據卸載策略。MA數據卸載策略以減少數據源傳感器能量消耗為目的，在實施過程中如果對數據源傳感器節點有額外增加的能量消耗，此數據源節點將不采用數據卸載策略，具體規則如下。

·數據源節點k不采用數據卸載策略的能量消耗為Ek，采用數據卸載策略的能量消耗為Ek＇，若滿足Ek＞Ek＇，可以考慮進行數據卸載。

·如果路徑中數據源節點k的下一跳after_offload節點a是數據源節點k+1。Eka＇和Eka分別表示節點a使用和不使用數據卸載能量消耗，由于Eka＇＞Eka，所以k不能直接使用第3.1節的數據卸載策略。需要進行迭代調整：k+1節點只能作為數據源節點，數據融合轉由后序的after_offload節點完成；MA攜帶的k-1個數據源節點數據沿迭代數據卸載路徑傳遞到后序的after_offload節點。迭代時將k作為before_offload節點，k+1數據源節點和k+1后第一跳節點作為after_offload節點調用算法1。迭代卸載路徑示意如圖3所示：第k個數據源節點539進行數據卸載操作，k+1節點494是after_offload節點，調用算法1找到offload節點778；539節點作為before_offload節點，第k+1個數據源節點494的下一跳節點493作為after_offload節點調用算法1，找到offload節點777。

·路徑中數據源節點k的下一跳after_offload節點是MA已經收集過數據的數據源節點n，由于Eka＇＞Eka，所以數據源節點k不采用數據卸載策略。

MA從sink節點派出采用數據卸載策略訪問路徑中所有數據源節點，算法流程如圖4所示。

4 仿真實驗

MA數據卸載策略不改變MA已有路徑規劃，可以應用于現有的MIP和SIP算法，本文對IEMF算法規劃的路徑使用與不使用MA數據卸載策略兩種情況，進行了大量的仿真實驗對比。

4.1 仿真參數

使用OPNET［17］在1 000 m×500 m的范圍內隨機部署800個傳感器節點，sink節點部署在網絡的邊緣，隨機選取5～40個數據源傳感器節點。sink節點派出移動代理訪問所有的數據源傳感器，通過無線多跳的方式收集感知數據，傳遞給sink節點。仿真參數見表1。

圖3 迭代卸載路徑示意

圖4 MA數據卸載策略路徑流程

表1 移動代理WSN仿真參數

4.2 融合率對MA數據卸載的影響

隨機選取10個數據源節點，使用數據卸載策略，不同的數據融合率對數據源節點平均節省能耗百分比的影響如圖5所示，融合率越低節省的能耗越多。

圖5 融合率和數據源節點節省能耗百分比

4.3 仿真性能

10個數據源節點，每個數據源節點平均節省能耗百分比如圖6所示，每個數據源節點能耗如圖7所示。未采用數據卸載策略，MA訪問數據源節點數越多攜帶的數據越大能量消耗越大。采用數據卸載策略將數據交給卸載節點來進行傳遞，減少數據源節點的能量消耗，隨著MA訪問數據源節點數的增加，數據源節點節省的能量消耗增加。

圖6 數據源節點節省能耗百分比

圖7 數據源節點能耗

圖8顯示隨著數據源節點數的增加使用數據卸載策略比不使用數據卸載策略可以節省更多的能量。數據源節點數對MA完成數據匯聚任務的總能耗的影響如圖9所示，MA數據卸載策略的使用會增加總能量消耗。根據第3.1節中各個節點能量消耗的分析，每一次數據卸載增加一定的能量消耗，這些能量消耗分散在數據卸載節點和數據源之后的數據融合節點。

5 結束語

圖8 數據源節點數和數據源節點總能耗

圖9 數據源節點數和總能耗響

移動代理數據融合和收集技術是無線傳感器網絡的關鍵技術，sink節點派出移動代理智能、高效地完成傳感器數據的收集工作。本文首先介紹了SIP和MIP算法普遍存在的單個數據源節點能量消耗不均衡的問題，MA訪問的數據源節點越多攜帶的數據量越大，消耗的能量越多。提出MA數據卸載策略，將MA攜帶的數據不通過數據源節點進行傳輸，實驗證明采用MA數據卸載策略減少數據源節點的能量消耗，有效地緩解了數據源節點能量消耗不均衡的問題。后序的研究將設計更完善的數據卸載的策略，均衡數據源節點的能量消耗，同時盡量減少總能量消耗的增加；考慮將數據卸載策略的思想應用到移動通信領域。

［1］VARAKLIOTIS S，HAILES S，DENARDI R，et al.UAV and cognitive radio technologies in the emergency services arena［J］.British Association of Public Safety Communications Officials，2010（11）.

［2］ABDULLA A E A A，FADLULLAH Z M，NISHIYAMA H，et al.An optimal data collection technique for improved utility in UAS-aided networks［C］/2014 IEEE International Conference on Computer Communications，April 27-May 2，2014，Toronto，Canada.New Jersey：IEEE Press，2014.

［3］PADILLA P，CAMACHO J，MACIA-FERNANDEZ G，et al.On the influence of the propagation channel in the performance of energy-efficient geographic routing algorithms for wireless sensor networks（WSN）［J］.Wireless personal communications，2013，70（1）：15-38.

［4］AHMAD A，LATIF K，JAVAIDL N，et al.Density controlled divide-and-rule scheme for energy efficient routing in wireless sensor networks［C］/2013 26th Annual IEEE Canadian Conference on Electrical and Computer Engineering（CCECE 2013），May 5-8，2013 Regina，Saskatchewan，Canada.New Jersey：IEEE Press，2013.

［5］蘇金樹，郭文忠，余朝龍，等.負載均衡感知的無線傳感器網絡容錯分簇算法［J］.計算機學報，2014，37（2）：445-456.SU J S，GUO W Z，YU C L，et al.Fault-tolerance clustering algorithm with load-balance aware in wireless sensor network［J］.Chinese Journal of Computers，2014，37（2）：445-456.

［6］郭文忠，蘇金樹，陳澄宇，等.無線傳感器網絡中帶復雜聯盟的自適應任務分配算法［J］.通信學報，2014，35（3）：1-10.GUO W Z，SU J S，CHEN C Y，et al.Self-adapted task allocation algorithm with complicated coalition in wireless sensor network［J］.Journal on Communications，2014，35（3）：1-10.［7］CHEN M，GONZALEZ S，ZHANG Y，et al.Multi-Agent Itinerary Planning for Wireless Sensor Networks［M］.Heidelberg：Springer，2009，22：584～597.

［8］CHEN M，YANG L T，KWON T，et al.Itinerary planning for energy-efficientagentcommunication inwirelesssensornetworks［J］.IEEE Transactions on Vehicular Technology，2011，60（7）：3290-3299.

［9］QI H R，WANG F Y.Optimal itinerary analysis for mobile agents in ad hoc wireless sensor networks［J］.Proceedings of the IEEE，2001.

［10］CAI W，CHEN M，HARA T，et al.A genetic algorithm approach to multi-agent itinerary planning in wireless sensor networks［J］.Mobile Networks and Applications，2011，16（6）：782-793.

［11］KONSTANTOPOULOS C，MPIZIOPOULOS A，GAVALAS D，et al.Effective determination of mobile agent itineraries for data aggregation on sensor networks［J］.Knowledge and Data Engineering，IEEE Transactions on，2010，22（12）：1679-1693.

［12］GAVALAS D，MPIZIOPOULOS A，PANTZIOU G，et al.An approach for near-optimal distributed data fusion in wireless sensor networks［J］.Wireless Networks，2010，16（5）：1407-1425.

［13］CHEN M，CAI W，GONZALEZ S，et al.Balanced itinerary planning for multiple mobile agents in wireless sensor networks［J］.Ad Hoc Networks，2010，49：416-428.

［14］WANG J F，ZHANG Y，CHENG Z L，et al.EMIP：energy-efficient itinerary planning for multiple mobile agents in wireless sensor network［J］.Telecommunication Systems，2015：1～8.

［15］CHEN M，HAO Y X，LI Y，et al.On the computation offloading at Ad Hoc cloudlet：architecture and service models［J］.IEEE Communications，2015，53（6）：18-24.

［16］CHEN M，ZHANG Y，LI Y，et al.EMC：Emotion-aware mobile cloud computing in 5G［J］.IEEE Network，2015，29（2）：32-38.

［17］陳敏.OPNET物聯網仿真［M］.武漢：華中科技大學出版社.2015.CHEN M.OPNET Internet of Things Simulation［M］.Wuhan：Huazhong University of Science and Technology Press，2015.

App lication of mobile agent itinerary p lanning based on data offloading strategy of energy optimal method

SHI Xiaobo1，2，LU Jianyu1，WANG Wenye1，RUAN Hang1，ZHU Xuan1，3
1.Huazhong University of Science and Technology，Wuhan 430074，China 2.Henan Normal University，Xinxiang 453007，China 3.Central China Normal University，Wuhan 430079，China

A data offloading strategy for optimizing itinerary planning of MA（mobile agent）was proposed.When MA visits source nodes based on data offloading strategy，it decides whether to transfer data package via optimized offloading itinerary and MA（mobile agent）visits data source nodes via conventional itinerary.Based on considerable simulations with the representative MA itinerary planning，i.e.itinerary energy minimum for first-source-selection（IEMF），it verifies that the problem of excessive energy consumption from source nodes can be efficiently solved and the lifetime of source nodes is prolonged.

data offloading，mobile agent，itinerary planning，wireless sensor network

s：The National Natural Science Foundation of China（No.61300224），Key Science and Technology Program of Henan Province（No.132102210483，No.102102210178），The Foundation and Cutting-edge Technologies Research Program of Henan Province（No.122300410344），The Natural Science Research Projects of Department of Education of Henan Province（No.2008A520013，No.2011A520023）

TP393

A

10.11959/j.issn.1000-0801.2016035

2015-04-15；

2015-12-11

朱瑄，xuanzhu@mail.ccnu.edu.cn

國家自然科學基金資助項目（No.61300224）；河南省重點科技攻關計劃基金資助項目（No.132102210483，No.102102210178）；河南省基礎與前沿技術研究計劃基金資助項目（No.122300410344）；河南省教育廳自然科學研究計劃基金資助項目（No.2008A520013，No.2011A520023）

史霄波（1972-），女，華中科技大學計算機科學與技術學院博士生，河南師范大學計算機與信息工程學院副教授，主要研究方向為無線傳感器網絡、機器學習、智能醫療。

魯建宇（1994-），男，華中科技大學光學與電子信息學院在讀，主要研究方向為移動軟件開發、無線傳感器網絡。

王文燁（1991-），男，華中科技大學計算機科學與技術學院碩士生，主要研究方向為無線傳感器網絡、生理信號處理。

阮航（1990-），男，華中科技大學計算機科學與技術學院碩士生，主要研究方向為分布式計算、無線傳感器網絡、模式識別。

朱瑄（1979-），女，華中科技大學計算機科學與技術學院在站博士后，華中師范大學計算機學院講師，主要研究方向為無線傳感器網絡、物聯網、智能醫療。