無線自組網中基于能量感知的跨層路由算法

鄧 敏，徐 方,2+，熊曾剛，葉從歡，夏洪星

(1.湖北工程學院 計算機與信息科學學院，湖北 孝感 432000；2.武漢大學 計算機學院，湖北 武漢 430072)

0 引 言

在自組織網絡的環境下，由智能移動設備構成的無線自組網節點受能源約束的影響很大，智能移動設備上日益增長的復雜應用和無線通信給設備帶來了越來越大的能量壓力[1]。設備因能量耗盡而停止提供服務，出現網絡分割的情況，導致網絡的一部分不能和網絡的另一部分進行正常通信[2]。因此，國內外研究者正致力于研究能量相關的路由協議，期望提高無線自組網中數據傳輸的能量效率。

最初，在計算路由協議的開銷時，主要采用節點的剩余能量進行度量。文獻[3]中的路由算法主要考慮節點上的初始能量、傳輸節點的剩余能量和每一次傳輸的開銷來選擇最高效的路徑。通過計算路徑沿線節點的剩余能量總和，文獻[4]說明了MBCR路由協議在路由決策時如何考慮路徑上總的剩余能量。文獻[5]描述了對MBCR路由進行改進的算法，它綜合使用路徑上的轉發跳數和總體能量消耗，能夠進一步提高轉發效率。最小能量流失率路由[6]引入節點能量消耗速率進行路由的度量，但是當網絡流量變化波動不大時，該方法的計算和評估不夠準確。DELAR[7]提出了一種能夠跨層感知能量負載的框架，通過考慮節點的剩余能量和網絡中節點的密度，能夠適合于由多種類型節點組成的異構無線自組網。LAER路由[8]是一種具有鏈路穩性感知和能量感知的路由算法，通過采用多目標線性規劃來優化路由決策。E2路由[9]提出了節點失效度的概念，并結合節點的剩余能量設計了一種靈活高效的路由方法。

目前，智能移動設備在日常生活中的普及，有利于形成新型的無線自組網，而這類網絡的路由性能還存在較大的提升空間。人們在生活中使用這些智能節點，并安裝了各種應用程序，而應用程序的運行對節點能量效率有一定的影響，進而影響到路由效率，因而在設計這類網絡的路由算法時，不僅要考慮節點的剩余能量和鏈路穩定性，還要進一步考慮應用程序對節點能耗的影響。基于以上分析，本文提出了一種能量感知的路由算法(context-aware energy-efficient routing，CAER)，算法采用跨層設計的思想設計能耗均衡的路由算法，提高網絡中的能量使用效率和網絡性能。

1 系統模型

1.1 上下文認知自學習模型

本文針對移動設備的特點提出了一種基于上下文認知的自學習模型(context-aware model，CAM)。CAM能動態采集系統中與應用相關的上下文信息，對上下文信息進行學習并優化調整相關參數，從而能動態地預測系統未來的能量消耗信息。首先，模型需要周期性的采樣系統使用情況的相關數據，然后設計能量模型，并通過采樣的數據來訓練該模型，最后根據設備當前的狀態計算出應用相關的能量效用值。為了減少模型產生的開銷，模型中存儲用戶應用程序的功率特征信息以減少在系統中進行的采樣頻率。此外，模型的訓練可以在設備充電時運行，從而減少對設備電池的消耗。

CAM模型工作在網絡的應用層。當一個新的應用啟動時應用程序監測模塊可以識別當前應用程序的類別。上下文信息采樣模塊從操作系統獲取所需要的上下文信息，這些信息包括：屏幕的亮度、設備的額定功率值、電池電量，以及設備各組件的工作負載狀態，這些組件如中央處理器(CPU)、圖形處理器(GPU)、無線局域網接口(WLAN)、蜂窩網絡接口(CELL)和顯示屏(MON)。應用程序監測模塊監測設備上運行的應用程序并獲取相關信息，如應用程序的類型、持續時間等。上下文信息處理模塊周期性獲取上述上下文信息，對上述上下文信息進行融合和推理，計算設備上與應用相關的能量消耗的效用值，為下一步的路由決策提供依據。上下文信息處理模塊將經過處理的上下文信息存儲在上下文知識庫中，上下文知識庫主要包含組件負載能耗表、應用負載信息表、監測和推理出的相關上下文信息。上下文知識庫中的信息能反映系統的動態變化，為下面的路由設計提供相關的能量約束信息。下面介紹上下文認知自學習模型的3個階段，分別是：初始化階段、應用程序監測階段、應用層能量效用計算階段。

1.2 初始化階段

日常生活中，由于人們所攜帶的移動設備規格存在多樣性，同樣的應用程序在不同的移動設備上可能產生不同的工作負載，即使是同樣的工作負載百分比，也可能在不同的設備上產生不同的能量消耗。因而在初始化階段需要建立組件負載信息表，使得CAM模型能夠適應于不同種類的移動設備。

根據文獻[10]研究結果表明，目前的移動設備(如智能手機和平板電腦)的主要耗能組件為：中央處理器(CPU)、圖形處理器(GPU)、無線局域網接口(WLAN)、蜂窩網絡接口(CELL)、屏幕(MON)。在初始化階段，首先運行一組預定義的任務在這些組件上產生不同程度的工作負載，然后監測相應的功率消耗。相關研究也表明[11]，只要經過合理的設計，這類在線監測和能量建模對設備正常使用的影響是微不足道的。

在初始化階段，模型在上下文知識庫中建立了一個組件負載能耗表，見表1。該表記錄各組件工作負載百分比與能量消耗速率之間的對應關系。在初始化階段，通過在節點上運行一組預定義的任務來獲取各組件的工作負載，設定的負載為5%、25%、50%、75%和100%。使用LCPU(x)、LGPU(x)、LWLAN(x)、LCELL(x)、LMON(x)分別表示CPU、GPU、WLAN、CELL、和MON等組件的工作負載是x%，Preal(x)表示工作負載為x%時從系統采樣的功率值。其中，x=5,25,50,75,100。

表1 組件負載能耗

系統的工作負載可以由表1中的組件的工作負載來表示，式(1)給出了當前系統的能量模型，Psys是當前系統的功率消耗。該能量模型考慮了上述提到的所有主要硬件組件的負載與系統能耗的關系。Lcomp(i)表示第i個組件上的工作負載。組件對應的權重Wcomp(i)用來平衡不同的組件對總體效用的影響。我們通過訓練能量模型可以得到權重因子Wcomp(i)的值，模型訓練的數據來自組件負載能耗表，其中存儲了真實的工作負載與在系統中監測到的系統的功率值。式(1)中，C為多元線性回歸模型中的常量

(1)

能量模型的誤差函數如式(2)所示，訓練過程的目標是最小化模型輸出值的誤差。通過比較模型計算的功率值Pcal(由式(1)計算得出)和從操作系統采樣的真實功率值Preal，我們可以獲得誤差值，然后利用這些誤差值調整權重值Wcomp(i)，達到優化能量模型的目的，從而進一步提高模型預測的精度

(2)

在初始化階段我們設計了能量模型，并且通過對模型的訓練取得了較優的權重值Wcomp(i)。在下一階段，我們將使用工作負載作為模型的輸入，使用模型評估系統的能量約束。

如上所述，系統的功率消耗被建模成一個預測模型。我們可以用目前的一些常用的回歸方法來求解模型的參數，其中非線性方法有支持向量回歸(SVR)和人工神經網絡(NN)；線性方法有多元線性回歸(MLR)。線性方法的主要優點是易于實現，而非線性方法可能會獲得更高的精度。由于移動設備資源受限，采用線性回歸能滿足該場景的精度和低能耗需求。

1.3 應用程序監測階段

在監測階段，我們構建一個應用負載信息表，一旦一個新的應用(表中沒有記錄的應用)啟動，CAM模型記錄這個應用程序運行時在各組件上額外產生的工作負載，當應用程序關閉時，計算該應用程序在組件上產生的工作負載的平均值，并把這些應用作為一條新的記錄存入應用負載信息表，見表2。

表2 應用負載信息

表2描述了應用負載信息表的基本結構。對于應用程序j，LCPU(j)表示CPU的工作負載，LGPU(j)、LWLAN(j)、LCELL(j)表示了類似的含義。屏幕的工作負載不記錄在這個表中，因為屏幕的能耗由其亮度決定，而屏幕的亮度取決于環境的照度和用戶的喜好，因此需要單獨采集和存儲。以上由應用程序產生工作負載可以用一個向量表示，如式(3)所示，PAPP(j)為應用j的功率特征

(3)

系統中應用程序產生的總功能值可以由系統中每個應用程序的功率消耗值之和表示。在計算能量約束時，式(4)的計算結果作為能量模型的部分輸入，能量模型的輸出則是整個系統的功率值

(4)

模型通過監測和更新應用相關的上下文信息提高其自適應能力，使得應用負載信息表能動態反映當前設備的使用情況。當應用負載信息表存在記錄的應用啟動時，模型考慮表中的數據計算當前的能量約束，運行階段根據當前設備相關信息對應用負載信息表采用增量更新的方式，CAM對于表中存在的應用，不定期的采樣這些應用在各個組件的平均功率，根據式(5)更新一個應用程序對應的功率消耗PAPP(j)(updated)，新的功率消耗PAPP(j)(updated)由兩個因素組成，一個是從表中取得的老的功率消耗值PAPP(j)(old)，另一個是剛剛從系統測量到的新的PAPP(j)(new)。使用歸一化的權重值(Wold,Wnew)表示兩個值對最新工作負載的影響，權重的取值由應用程序的運行持續時間決定。每當一個應用開始運行時，利用式(5)計算應用j對應的功率消耗和新采樣的負載值更新應用負載信息表，從而實現上下文認知自學習過程

PAPP(j)(updated)=Wold·PAPP(j)(old)+
Wnew·PAPP(j)(new)

(5)

(6)

相比于定期的硬件級別的監測，本文提出的模型是一個簡單和低開銷的方法，因為部署了該模型的設備能夠識別應用的類型，并結合功能特征和能量模型計算當前應用的能量約束。應用負載信息表中的數據可以用于訓練模型，因為它動態記錄設備使用的變化情況。

1.4 應用層能量效用計算階段

由于設備屏幕的亮度與人們的個人喜好相關，在計算設備的功率消耗特征時，應分別考慮應用產生的功率消耗和屏幕產生的功率消耗，則式(1)中表述的能量模型可以轉化為式(7)進行表示

Psys=PAPP+WMON·LMON+C

(7)

式(8)中，Uapp描述了應用對應能量約束的效用函數。Psys為式(7)計算出的系統當前功率消耗，Prat為設備的額定功率值

(8)

應用層能量效用不僅考慮應用程序的效用還應考慮網絡中節點內的剩余能量情況，在式(9)中，檢測時應用程序的實時能耗值用Econs表示，節點總電量用Etotal表示，Ubat為節點剩余能量效用函數，它的取值范圍是0到1之間

(9)

(10)

應用層能量效用(Cnode)由節點中應用的效用和節點中剩余能量的效用組成，如式(11)所示。通過使用歸一化的權重Wapp和Wbat來協調上述兩個因素的貢獻

Cnode=Wapp·Uapp+Wbat·Ubat
Wapp+Wbat=1

(11)

經過上述自學習過程中，應用層能量相關的上下文信息被學習和利用，在當前設備中，該過程對每類應用程序在每個硬件組件上產生的工作負載進行監測和采樣，然后將應用相關的能量約束存儲在應用負載信息表中。此外，每當一個應用程序啟動時，新的監測值會被用于更新應用負載信息表，體現了模型的自適應和自學習能力。通過使用這種方法，模型能夠處理移動應用市場上的大量應用程序。

2 CAER路由機制

2.1 跨層設計

在傳統互聯網中，分層設計的思想被廣泛使用。在分層設計中，網絡各層模塊間相對獨立使得網絡設計較為簡單并容易實現。但是，隨著移動無線網絡的出現，傳統分層設計的方法不利于未來普適網絡的發展。普適網絡要求網絡中的節點能感知節點自身和周圍環境上下文信息，并以自組織自適合的方式為用戶提供服務。而采用跨層設計的方法可以增強網絡各層的信息共享，從而能有效提高網絡的服務質量和能量效率。在本文提出了CAER路由的跨層設計方案中，網絡層在進行路由決策時，可以充分利用應用層，網絡層和數據鏈路層中的上下文信息，使得網絡中的數據傳輸更高效更節能。

圖1描述了網絡中的應用層、數據鏈路層和網絡層實現信息共享的過程，簡要描述了上述網絡層如何通過交換上下文信息來實現跨層節能的路由決策。圖中灰色背景的模塊是重點強調部分，分別是應用層的上下文認知自學習模塊、網絡層的路由信息處理模塊和數據鏈路層的鏈路穩定性監測與度量模塊。

圖1 路由的體系結構

應用層使用應用監測、能耗監測、剩余能量監測3個組件來收集應用與能耗相關的上下文信息，使用上下文認知自學習模型處理收集到的上下文信息。數據鏈路層部署的鏈路穩定性監測與度量模塊能夠分析接收到的無線信號強度，并利用相應的效用函數計算信號強度的效用值。網絡層的路由信息處理模塊包含上下文信息融合和路由信息處理，該模塊接收應用層的能量約束信息和數據鏈路層鏈路穩定性信息，跨層共享各類上下文信息進行路由決策。在CAER路由算法的設計中，本文采用跨層設計的方法，使得算法能夠綜合利用應用層、網絡層和數據鏈路層的信息進行路由設計和數據轉發決策，有助于提高網絡的服務質量和能量效率。

2.2 路由算法

本文提出的基于能量感知的跨層路由算法是在AODV路由算法[12]的基礎上進行的改進，在路由發現階段采用廣播報文的方法，轉發節點需要建立和維護路由表，并根據路由表進行數據報文的轉發。和AODV算法一樣，本算法也包含兩個過程，分別是路由發現階段和路由維護階段。接下來，本文重點介紹在AODV算法基礎上的改進部分。

當源節點需要發送數據時，源節點向周圍的鄰居節點發送路由請求報文(RREQ)，RREQ報文中包含的主要字段如圖2所示，本文在AODV協議RREQ報文的基礎上進行了改進，添加了節點的開銷(Enode)和鏈路的開銷(Elink)。

圖2 RREQ幀格式

節點能量開銷Enode的計算方法如式(12)所示，鏈路穩定性效用值Elink的計算方法如式(13)所示，路由路徑上當前節點的序號為k，設源節點的序號為1，沿著路由路徑序號k的值依次遞增，目的節點的序號用n表示

(12)

(13)

當某個中間節點接收到路由請求時，如果中間節點的路由表中包含有到達目的節點的路由信息，那么中間節點直接返回路由應答報文(RREP)，源節點收到該報文，完成路由發現過程；否則直到目的節點收到路由請求報文(RREQ)。當第一個RREQ報文到達目的節點時，目的節點啟動計時器，接收延時T時間內所有的路由請求報文。對于接收到的所有RREQ報文，利用式(14)計算該路徑上的效用值(Croute)，取Croute值最小的路徑作為數據轉發路徑，并在該路徑上發送路由應答報文(RREP)，完成路由的發現過程

(14)

3 性能評估

3.1 參數設置

利用NS2網絡仿真軟件，本文評估了CAER路由算法的能量效率和性能。在同樣的網絡環境中，對比分析了CAER、AODV、LAER和E2算法，為了充分分析路由算法的能量效率，網絡中的150個節點被分為3種類型，根據節點上運行的應用程序分為A類節點50個(空閑節點)，B類節點50個(游戲節點)，C類節點50個(視頻流節點)。數據傳輸時，隨機選擇4對源節點和目的節點，傳輸速率的比特率分別為150 Kbps、200 Kbps、250 Kbps、300 Kbps 和350 Kbps。仿真實驗的持續時間設為120 s，每種實驗運行30次。A、B、C這3類節點的功率分別為150毫瓦、350毫瓦和550毫瓦。WiFi接入的功率為400毫瓦，網絡中節點的能量初始值為100焦耳。在計算式(11)時，Wapp和Wbat權值分別設為0.4、0.6，體現了應用能效與剩余能量對總效用的實際影響。

3.2 不同運行時間下的能量消耗

A、B、C這3種類型節點的平均能耗情況如圖3～圖5所示，本文提出的CAER路由在不同程度上為3類節點節省了電能。對于A類節點來說，CAER算法的節能效果最明顯，因為A類節點處于空閑狀態，節點剩余能量多，為跨層信息共享的路由機制提供了更多的節能空間。以AODV協議為基準進行比較，采用CAER方案可以為A類節點節約18%的能量，為B類節點節約12%的能量，為C類節點節約7%的能量。

圖3 A類節點的平均能量消耗

圖4 B類節點的平均能量消耗

圖5 C類節點的平均能量消耗

3.3 網絡生存時間

圖6描述了在不同數據傳輸率下使用各算法的網絡生存時間，隨著網絡中數據傳業務的增加，網絡負載不斷增大，能量消耗也在逐漸加大，因而隨著傳輸速率的增加，網絡生存時間逐漸縮短。因為AODV算法沒有考慮能量消耗等因素，其在生存時間上的表現最差，考慮了能量信息的其它3種路由算法能不同程度的提高網絡生存時間。以AODV為基準，CAER算法平均提高網絡生存時間大約20%，而LAER和E2分別提高了大約12%和15%。

圖6 網絡生存時間

4 結束語

能量受限是無線網絡的重要特征之一，對于移動自組網絡更是如此。本文研究的無線自組網節點主要由人們攜帶的智能通信設備組成(如智能手機、平板電腦)，受限于目前的電池技術，智能通信設備的電能僅能維持較短的時間，然而智能通信設備上應用程序的不斷增加，進一步加快了設備上的能量消耗，從而降低了網絡的生存時間，當網絡中某個節點因能量耗盡而停止工作，可能會導致網絡分割，進而影響整個網絡的性能。本文主要針對由智能移動設備組成的無線自組網，研究基于能量感知的跨層節能路由算法。該算法采用跨層設計的思想綜合利用數據鏈路層、網絡層和應用層的上下文信息，提高了網絡中能量的使用效率和生存時間，實現了能量效率與網絡性能之間的平衡。

[1]Yao Y,Cao Q,Vasilakos A V.EDAL:An energy-efficient,delay-aware,and lifetime-balancing data collection protocol for heterogeneous wireless sensor networks[J].IEEE/ACM Transactions on Networking,2015,23(3):810-823.

[2]Priya S S,Krishnan H M.Energy aware span routing protocol in mobile Ad Hoc networks[J].Wireless Communication,2016,8(1):11-16.

[3]Pantazis N A,Nikolidakis S A,Vergados D D.Energy-efficient routing protocols in wireless sensor networks:A survey[J].IEEE Communications Surveys & Tutorials,2013,15(2):551-591.

[4]Bade S,Kumar M,Kamat P.A reactive energy-alert algorithm for manet and its impact on node energy consumption[J].International Journal of Computer Applications,2013,71(18):1-6.

[5]Varaprasad G,Narayanagowda S H.Implementing a new power aware routing algorithm based on existing dynamic source routing protocol for mobile ad hoc networks[J].IET Networks,2014,3(2):137-142.

[6]Gandhi C,Arya V.A survey of energy-aware routing protocols and mechanisms for mobile ad hoc networks[M].India:Springer India,2014:111-117.

[7]Hu L,Yuan’an L,Dongming Y,et al.Study of capacity region and minimum energy of delay-tolerant unicast mobile ad hoc networks using cell-partitioned model[J].Wireless Communications & Mobile Computing,2016,16(7):825-849.

[8]De Rango F,Guerriero F,Fazio P.Link-stability and energy aware routing protocol in distributed wireless networks[J].IEEE Transactions on Parallel and Distributed Systems,2014,23(4):713-726.

[9]Ramrekha TA,Talooki VN,Rodriguez,et al.Energy efficient and scalable routing protocol for extreme emergency ad hoc communications[J].Mobile Network Appl,2015,17(2):312-324.

[10]Ahmad R W,Gani A,Hamid S H A,et al.A survey on ener-gy estimation and power modeling schemes for smartphone applications[J].International Journal of Communication Systems,2016,12(3):22-33.

[11]Li D,Halfond W G J.An investigation into energy-saving programming practices for android smartphone app development[C]//Proceedings of the 3rd International Workshop on Green and Sustainable Software.ACM,2014:46-53.

[12]Ahmed A,Hanan A,Osman I.AODV routing protocol working process[J].Journal of Convergence Information Technology,2015,10(2):1-10.