一種基于能效與頻效的路由優(yōu)化算法

何林波，蔣定德，仲維佳

(1.成都信息工程大學(xué)信息安全工程學(xué)院,四川成都 610225；2.東北大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,遼寧沈陽(yáng) 110819)

?

一種基于能效與頻效的路由優(yōu)化算法

何林波1,，蔣定德2,，仲維佳2

(1.成都信息工程大學(xué)信息安全工程學(xué)院,四川成都 610225；2.東北大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,遼寧沈陽(yáng) 110819)

網(wǎng)絡(luò)能效和網(wǎng)絡(luò)頻效作為當(dāng)前的熱點(diǎn)研究問(wèn)題,對(duì)網(wǎng)絡(luò)性能有重要影響.然而針對(duì)移動(dòng)Ad Hoc網(wǎng)絡(luò)中的能效和頻效問(wèn)題,還缺乏深入研究,而且大多數(shù)研究?jī)H僅局限于單目標(biāo)的網(wǎng)絡(luò)能耗或網(wǎng)絡(luò)能效,聯(lián)合考慮網(wǎng)絡(luò)能效和網(wǎng)絡(luò)頻效的研究還不多.本文分析移動(dòng)Ad Hoc網(wǎng)絡(luò)中的網(wǎng)絡(luò)能效和網(wǎng)絡(luò)頻效問(wèn)題,討論二者間的權(quán)衡關(guān)系,利用多目標(biāo)優(yōu)化理論,構(gòu)建聯(lián)合網(wǎng)絡(luò)能效和網(wǎng)絡(luò)頻效的多目標(biāo)優(yōu)化模型,并利用加權(quán)和方法將多目標(biāo)優(yōu)化轉(zhuǎn)化成單目標(biāo)優(yōu)化,提出資源效率的概念,最后提出針對(duì)移動(dòng)Ad Hoc網(wǎng)絡(luò)資源效率優(yōu)化的路由策略.仿真結(jié)果表明,所提出的算法具有較好的性能.

移動(dòng)Ad Hoc網(wǎng)絡(luò)；能效；多目標(biāo)優(yōu)化；頻效；路由算法

1 引言

多跳無(wú)線網(wǎng)絡(luò)是一種非常具有潛力的網(wǎng)絡(luò),同時(shí)它也是一種復(fù)雜的系統(tǒng),目前仍然存在一些問(wèn)題需要徹底的研究.尤其隨著互聯(lián)網(wǎng)的飛速發(fā)展,導(dǎo)致網(wǎng)絡(luò)的流量不斷增長(zhǎng),因此網(wǎng)絡(luò)能耗也與日劇增[1-7].按照目前增長(zhǎng)趨勢(shì),到2025年信息通信行業(yè)的平均能耗將變成2006年的5倍,而網(wǎng)絡(luò)領(lǐng)域?qū)⒏?甚至可達(dá)到13倍[5-10].在網(wǎng)絡(luò)領(lǐng)域中有一半以上的能耗是無(wú)線網(wǎng)絡(luò)的能源消耗,需要最優(yōu)化理論進(jìn)行解決[11-15]；而網(wǎng)絡(luò)頻譜也是非常緊缺的資源.因此,研究能夠降低移動(dòng)多跳無(wú)線網(wǎng)絡(luò)能耗并獲得較高頻譜效率的高能效傳輸機(jī)制已成為當(dāng)今無(wú)線通信領(lǐng)域的熱點(diǎn)問(wèn)題[16-20].

如何構(gòu)建能效的網(wǎng)絡(luò)路由具有挑戰(zhàn)性,文獻(xiàn)[14]提出一種基于網(wǎng)絡(luò)的路由算法來(lái)尋找到云數(shù)據(jù)中心的最能效路徑,以便處理和存儲(chǔ)大數(shù)據(jù)；文獻(xiàn)[15]提出一種新的安全而切實(shí)可行的迂回能效路由方法來(lái)解決IP網(wǎng)絡(luò)中的節(jié)能問(wèn)題；文獻(xiàn)[17]利用跨層設(shè)計(jì)來(lái)獲得Ad Hoc網(wǎng)絡(luò)中能效的機(jī)會(huì)路由.IPv6家庭網(wǎng)絡(luò)中的能效路由也被研究[18],能效路由性能[19]、頻效多跳路由[20]也被分析.多跳網(wǎng)絡(luò)具有干擾對(duì)消的頻效路由[21]、頻譜感知的多媒體路由[22]也被提出來(lái)解決頻效問(wèn)題.在多跳無(wú)線網(wǎng)絡(luò)中,能效和頻效一直是衡量系統(tǒng)的重要性能指標(biāo).對(duì)于移動(dòng)Ad Hoc網(wǎng)絡(luò)而言,節(jié)點(diǎn)通常采用電池供電,提高網(wǎng)絡(luò)性能顯得非常重要.文獻(xiàn)[3-4]表明網(wǎng)絡(luò)中能效與頻效通常是矛盾,網(wǎng)絡(luò)能效和頻效無(wú)法同時(shí)達(dá)到最優(yōu),因此需要考慮網(wǎng)絡(luò)中能效與頻效的折中問(wèn)題.盡管以上方法能獲得較高能效或獲得較高頻效,但這些方法沒有同時(shí)考慮頻效和能效問(wèn)題.然而,由于網(wǎng)絡(luò)設(shè)備和協(xié)議的高能耗[23-24],如何同時(shí)獲得高能效和頻效是困難的[3-4].

本文首先針對(duì)無(wú)線網(wǎng)絡(luò)端到端鏈路的研究,引出了無(wú)線網(wǎng)絡(luò)中能效與頻效權(quán)衡的問(wèn)題.在此基礎(chǔ)上給出了無(wú)線多跳網(wǎng)絡(luò)中移動(dòng)Ad Hoc的能效和頻效模型并進(jìn)行了分析.之后結(jié)合兩個(gè)模型建立了能效和頻效權(quán)衡優(yōu)化的多目標(biāo)優(yōu)化問(wèn)題,并利用多目標(biāo)理論中加權(quán)和方法將多目標(biāo)問(wèn)題轉(zhuǎn)化為單目標(biāo)問(wèn)題并提出資源效率的概念.最后提出了ESTROA算法,并在吞吐量、能耗和資源效率等性能指標(biāo)上與對(duì)比算法進(jìn)行了對(duì)比分析,從而驗(yàn)證了算法的有效性.

2 問(wèn)題闡述

2.1 頻效與能效的權(quán)衡

考慮一條點(diǎn)到點(diǎn)的通信鏈路,設(shè)G是發(fā)送端與接收端信道增益,P是發(fā)送功率,PC是電路設(shè)備功率損耗,σ2是噪聲功率(高斯加性白噪聲),該鏈路能效和頻效可表示為：

(1)

其中,fSE(P)表示頻效,單位為bit/Hz；fEE(P)表示頻能效,單位為bit/J/Hz.

則可建立如下的多目標(biāo)優(yōu)化模型：

(2)

不同于單目標(biāo)優(yōu)化,常多目標(biāo)優(yōu)化問(wèn)題通常并不存在全局最優(yōu)解.因此,多目標(biāo)問(wèn)題的最優(yōu)解通常是滿足預(yù)設(shè)條件的一些解的集合.最常用的最優(yōu)解為Pareto最優(yōu)解,Pareto最優(yōu)解可定義為如下[11,25].

定義1 設(shè)點(diǎn)P0∈(0,Pmax],如不存在點(diǎn)P∈(0,Pmax]使得fSE(P)≥fSE(P0)且fEE(P)≥fEE(P0),而且fSE(P)>fSE(P0)與fEE(P)>fEE(P0)至少一個(gè)滿足時(shí),則稱P0∈(0,Pmax]為該多目標(biāo)問(wèn)題的一個(gè)Pareto最優(yōu)解.

定義2 設(shè)點(diǎn)P0∈(0,Pmax],如不存在點(diǎn)P∈(0,Pmax]使得fSE(P)>fSE(P0)與fEE(P)>fEE(P0)都滿足時(shí),則稱P0∈(0,Pmax]為該多目標(biāo)問(wèn)題的一個(gè)弱Pareto最優(yōu)解.

定義3 Pareto最優(yōu)解集是所有Pareto最優(yōu)解的集合.

定義4 有效與無(wú)效：設(shè)點(diǎn)P0∈(0,Pmax],如果不存在點(diǎn)P∈(0,Pmax]使得fSE(P)≥fSE(P0)、fEE(P)≥fEE(P0)而且fSE(P)>fSE(P0)與fEE(P)>fEE(P0)至少一個(gè)滿足時(shí),則稱P0是有效的,否則無(wú)效.

通過(guò)上述定義可得一個(gè)點(diǎn)如果是弱Pareto最優(yōu)解那么它一定是Pareto最優(yōu)解,但是一個(gè)解是Pareto最優(yōu)解那么它不一定是弱Pareto最優(yōu)解.換句話說(shuō),在本文中一個(gè)點(diǎn)是Pareto最優(yōu)解且有效的前提是不存在另外一個(gè)點(diǎn)能在不影響頻效(能效)的情況下改善能效(頻效).為了得到多目標(biāo)問(wèn)題的Pareto解,首先總結(jié)下式子(1)中表示的能效和頻效的性質(zhì).

(1)fSE(P)是嚴(yán)格遞增的.

(2)存fEE(P)在一點(diǎn)P*∈[0,∞),使得fEE(P)在區(qū)間P∈[0,P*)遞增,在區(qū)間P∈[P*,∞)上遞減即在P*處達(dá)到最大.

證明：性質(zhì)1顯然成立,下面證明性質(zhì)2.

β(P)=-(1+ρP)log(1+ρP)+ρ(P+PC)

能效(Energy Efficiency,EE)和頻效(Spectrum Efficiency,SE)的關(guān)系如圖1所示.

由圖1可清楚發(fā)現(xiàn)通常并不存在一種策略可以使得頻效和能效同時(shí)達(dá)到最優(yōu),能效和頻效間往往存在權(quán)衡(tradeoff)問(wèn)題.因此,單單采取能效或頻效這種單目標(biāo)優(yōu)化的形式具有一定的局限性.本文運(yùn)用多目標(biāo)優(yōu)化理論,將多目標(biāo)問(wèn)題轉(zhuǎn)化成單目標(biāo)問(wèn)題,再對(duì)各自網(wǎng)絡(luò)進(jìn)行優(yōu)化.

2.2 聯(lián)合能效與頻效的優(yōu)化模型

與固定網(wǎng)絡(luò)和蜂窩網(wǎng)絡(luò)不同,移動(dòng)Ad Hoc網(wǎng)絡(luò)是一種不依賴任何基礎(chǔ)設(shè)施的移動(dòng)網(wǎng)絡(luò).該網(wǎng)絡(luò)具有無(wú)中心結(jié)構(gòu),拓?fù)潆S時(shí)變化,能量和帶寬有限等特征.如圖2所示,移動(dòng)Ad Hoc網(wǎng)絡(luò)是由一組移動(dòng)節(jié)點(diǎn)組成,這些節(jié)點(diǎn)不依賴已經(jīng)存在的基礎(chǔ)設(shè)施的支持就可以建立節(jié)點(diǎn)與節(jié)點(diǎn)之間的鏈路.移動(dòng)Ad Hoc網(wǎng)絡(luò)所有節(jié)點(diǎn)地位平等,可自由移動(dòng),由于不需要要中心控制所以具備很強(qiáng)魯棒性.但又由于網(wǎng)絡(luò)的能量和帶寬受限問(wèn)題,因此提高網(wǎng)絡(luò)能效和頻效就至關(guān)重要.

假設(shè)移動(dòng)Ad Hoc網(wǎng)絡(luò)有n個(gè)節(jié)點(diǎn),則節(jié)點(diǎn)發(fā)送功率為：

Pij=cij×fij

(3)

節(jié)點(diǎn)的接收功率為：

Qij=γ×fij

(4)

其中,γ表示節(jié)點(diǎn)接收1bit數(shù)據(jù)所消耗的能量.

則公式(1)中的網(wǎng)絡(luò)能效fEE(P)和頻效fSE(P)表示為：

(5)

其中,l表示網(wǎng)絡(luò)路徑數(shù),hl表示第條路徑的跳數(shù),G表示接收端與發(fā)送端間的信道增益.

聯(lián)合能效和頻效的多目標(biāo)最優(yōu)化模型可表示為：

(6)

如何獲得等式(6)的最優(yōu)解是解決聯(lián)合能效和頻效的多目標(biāo)路由優(yōu)化問(wèn)題.

3 聯(lián)合優(yōu)化路由算法

針對(duì)移動(dòng)Ad Hoc網(wǎng)絡(luò),下面討論聯(lián)合頻效和能效的多目標(biāo)優(yōu)化路由算法.

3.1 聯(lián)合頻效能效的最優(yōu)解

引理1fSE(P)隨自變量P∈[0,∞)遞增.

引理2 存在一點(diǎn)P*∈[0,∞),使得fEE(P)在區(qū)間P∈[0,P*)遞增,在區(qū)間P∈[P*,∞)上遞減.

證明：

通過(guò)引理1、引理2和定義1,則得到如下定理1.

定理1 等式(6)中的多目標(biāo)問(wèn)題max{fSE,fEE}的Pareto最優(yōu)解(Ppos)為：

(7)

直接求解等式(6)是困難的,下面通過(guò)多目標(biāo)最優(yōu)化理論來(lái)獲得等式(7)所表示的等式(6)的Pareto最優(yōu)解.

為了獲得等式(6)的Pareto最優(yōu)解,等式(6)可變換為：

(8)

推論1 等式(8)中單目標(biāo)問(wèn)題的最優(yōu)解Popt就是等式(6)中多目標(biāo)問(wèn)題的一個(gè)Pareto最優(yōu)解.

證明：設(shè)N為約束條件中不等式gn(Pij)的個(gè)數(shù),則可得如下等式：

ω1=1-ω2;f1(·)=fSE(·);f2(·)=fEE(·)

λngn(Popt)=0

(9)

根據(jù)(9),得到如下等式：

(10)

其中,λn是拉格朗日系數(shù).

根據(jù)等式(10),得到等式(8)中的單目標(biāo)問(wèn)題的庫(kù)恩塔克條件(K-T條件)為：

由于f1,f2的凹性,所以等式(6)中多目標(biāo)問(wèn)題的Pareto最優(yōu)解與滿足K-T條件互為充分必要條件.可知單等式(8)中目標(biāo)問(wèn)題的解包含在多目標(biāo)問(wèn)題的Pareto最優(yōu)解集中.證畢

推論2 以下條件滿足其一時(shí),ωfSE+(1-ω)fEE在P∈[0,∞)上遞增：

(11)

2ωGTij(fijγ+σ2)+G(1-ω)-2ωTijσ2-

(12)

證明：設(shè)

則得到：

[ln2(σ2+GPij)Tij(Pij+γ×fij+σ2)2]

令

β=ωGTij(Pij+γ×fij+σ2)2+(1-ω)G(Pij+γ×fij

則得到等式：

β′=2ωGTij(Pij+γ×fij+σ2)+G(1-ω)-

=2ωGTij(Pij+γ×fij+σ2)

且有

推論3 設(shè)

當(dāng)ω=cosθ/(sinθ+cosθ)時(shí),該問(wèn)題和等式(8)所表示的問(wèn)題具有相同Pareto最優(yōu)解,即線性加權(quán)問(wèn)題可以轉(zhuǎn)化為三角線性加權(quán)問(wèn)題,對(duì)于一個(gè)θ值可以求出一個(gè)Pareto最優(yōu)解.并且可知當(dāng)Pareto曲線為凹時(shí),θ∈[0,π/2]可以覆蓋整個(gè)曲線.從而可得當(dāng)Pareto曲線為凹時(shí),對(duì)于等式(8)所表示的問(wèn)題,時(shí)可以覆蓋整個(gè)曲線.

推論4 當(dāng)Pareto曲線為凹時(shí),線性問(wèn)題可以轉(zhuǎn)換為三角線性加權(quán)問(wèn)題后求解.對(duì)于一個(gè)固定的θ,Pareto最優(yōu)解就是F=fSE(P)cosθ+fEE(P)sinθ與fSE(P)和fEE(P)確定的曲線在fSE-fEE坐標(biāo)系的切點(diǎn).

證明：設(shè)F=fSE(P)cosθ+fEE(P)sinθ,則等式(6)中多目標(biāo)問(wèn)題可變?yōu)橥普?中三角線性加權(quán)問(wèn)題,求解推論3中的問(wèn)題等同于求解F/(cosθ+sinθ)最大值.從而由F=fSE(P)cosθ+fEE(P)sinθ可以得到：

則在fSE～fEE坐標(biāo)系中,上面等式的意義就是斜率一定(給定)時(shí),在該曲線范圍內(nèi)尋找截距fSE的最大值.顯然,只有在直線與凹曲線相切時(shí),截距達(dá)到最大.那么切點(diǎn)便是Pareto最優(yōu)解.證畢

從而通過(guò)以上推導(dǎo),可以獲得等式(7)所表示的等式(6)多目標(biāo)最優(yōu)化模型的Pareto最優(yōu)解.

3.2 路由優(yōu)化算法

上面已經(jīng)推導(dǎo)了關(guān)于能效與頻效權(quán)衡的多目標(biāo)路由優(yōu)化模型(如等式(6)所示)的Pareto最優(yōu)解求解過(guò)程,下面提出聯(lián)合考慮能效與頻效折中的最優(yōu)路由算法(Energy efficiency and Spectrum efficiency-based Tradeoff optimization Routing Algorithm,ESTORA).ESTORA算法流程如圖3所示,ESTORA算法具體步驟如下：

步驟1：初始化網(wǎng)絡(luò)狀態(tài)、路由參數(shù),分析流量請(qǐng)求,將請(qǐng)求按照業(yè)務(wù)大小從大到小進(jìn)行排序,并生成請(qǐng)求隊(duì)列R；

步驟2：從隊(duì)列R中取出流量請(qǐng)求,進(jìn)行處理；

步驟3：如果目的節(jié)點(diǎn)在源節(jié)點(diǎn)覆蓋范圍內(nèi),則完成該請(qǐng)求的尋路過(guò)程,同時(shí)更新相應(yīng)的鏈路狀態(tài)信息跳轉(zhuǎn)至步驟5；若該節(jié)點(diǎn)為孤立節(jié)點(diǎn),則跳轉(zhuǎn)至步驟5,否則計(jì)算功率能量比并以此采用Dijkstra算法進(jìn)行選路以此來(lái)選擇資源效率較高的路徑；如果存在權(quán)重相同的情況,則隨機(jī)選擇其中一條路徑；

步驟4：若存在滿足QoS的路徑,則完成該請(qǐng)求的尋路過(guò)程,同時(shí)更新相應(yīng)的鏈路狀態(tài)信息,否則尋路失敗,鏈路狀態(tài)信息不做任何改變；

步驟5：將該業(yè)務(wù)請(qǐng)求從請(qǐng)求隊(duì)列中刪除,并判斷R是否為空.若為空,則程序結(jié)束,否則跳轉(zhuǎn)到步驟3.

4 仿真分析

本節(jié)對(duì)ESTORA算法進(jìn)行仿真分析,通過(guò)一系列仿真實(shí)驗(yàn)來(lái)驗(yàn)證所提出的ESTORA算法.最短優(yōu)先路徑路由算法(Shortest Path First routing algorithm,SPF)和基于節(jié)點(diǎn)剩余能量路由算法(Based on the Remaining Energy routing algorithm,BRE)被報(bào)道為兩種重要的路由算法；SPF算法從源節(jié)點(diǎn)到目的節(jié)點(diǎn)進(jìn)行選路時(shí),以節(jié)點(diǎn)間距離為權(quán)重,采用Dijkstra算法,以起始點(diǎn)為中心向外層層擴(kuò)展,直到擴(kuò)展到終點(diǎn)為止,從而完成選路；BRE算法讓網(wǎng)絡(luò)中剩余能量多的節(jié)點(diǎn)來(lái)轉(zhuǎn)發(fā)報(bào)文,保護(hù)網(wǎng)絡(luò)中能量較小的節(jié)點(diǎn),提高網(wǎng)絡(luò)利用率,延長(zhǎng)網(wǎng)絡(luò)的整體壽命,改善網(wǎng)絡(luò)能效.為了驗(yàn)證ESTORA算法,本文對(duì)比分析三種算法的性能.

4.1 仿真環(huán)境以及參數(shù)

仿真平臺(tái)為Matlab2012a,仿真實(shí)驗(yàn)使用隨機(jī)產(chǎn)生的網(wǎng)絡(luò)拓?fù)浜碗S機(jī)產(chǎn)生的流量請(qǐng)求來(lái)進(jìn)行驗(yàn)證分析.網(wǎng)絡(luò)拓?fù)渲泄?jié)點(diǎn)數(shù)為50個(gè),對(duì)應(yīng)最大通信半徑為600m,任意兩個(gè)節(jié)點(diǎn)在另外一個(gè)節(jié)點(diǎn)的覆蓋范圍內(nèi)即可形成鏈路,且兩節(jié)點(diǎn)之間形成的鏈路是雙向的；仿真場(chǎng)景中節(jié)點(diǎn)的移動(dòng)模型為隨機(jī)行走模型；業(yè)務(wù)帶寬范圍1M-2M；網(wǎng)絡(luò)仿真的區(qū)域大小為1200m×1200m.網(wǎng)絡(luò)仿真具體參數(shù)如表1所示.

表1 網(wǎng)絡(luò)仿真參數(shù)

4.2 仿真結(jié)果及分析

本節(jié)對(duì)比分析三種算法失敗次數(shù)、能耗、吞吐量、能效、資源效率以及網(wǎng)絡(luò)流質(zhì)量等,同時(shí)分析ESTROA隨節(jié)點(diǎn)速度變化時(shí)資源效率的變化情況.

A.尋路失敗次數(shù)

圖4表示了三種算法尋路失敗次數(shù)隨請(qǐng)求數(shù)目的變化情況,其中失敗率是網(wǎng)絡(luò)沒有尋找到路徑的業(yè)務(wù)數(shù)與總業(yè)務(wù)數(shù)的比值.從圖4可看出,ESTROA和BRE都可以達(dá)到較好的尋路成功率,并且ESTROA稍微優(yōu)于BRE算法,而SPF失敗率最大.這是因?yàn)镾PF只是基于最短路徑進(jìn)行選路,很容易造成路徑過(guò)于集中

而造成節(jié)點(diǎn)過(guò)早死亡,從而影響整個(gè)網(wǎng)絡(luò)的尋路情況；而ESTORA和BRE算法在進(jìn)行選路時(shí)都避免了選路過(guò)于集中的問(wèn)題,能擁有較高的尋路成功率.

B.網(wǎng)絡(luò)能耗

圖5表示了三種算法能耗隨網(wǎng)絡(luò)請(qǐng)求數(shù)目的變化情況.圖5表明,ESTROA的能耗最小,BRE能耗居中,而SPF能耗最大；隨著請(qǐng)求數(shù)目的增加,三種算法能耗都會(huì)有所增加.從圖5也可以看出,ESTROA相比BRE而言,能耗減少了大約一半.這說(shuō)明ESTROA算法沒有以犧牲能耗為代價(jià)去換取其他指標(biāo)的優(yōu)化,可見ESTROA算法能以較低的網(wǎng)絡(luò)能耗獲得具有較好的性能.

C.網(wǎng)絡(luò)吞吐量

圖6表示了三種算法網(wǎng)絡(luò)吞吐量隨請(qǐng)求數(shù)目的變化情況,其中網(wǎng)絡(luò)吞吐量通過(guò)網(wǎng)絡(luò)中所有成功傳輸?shù)恼?qǐng)求大小進(jìn)行衡量.圖6表明,ESTROA吞吐量最大,其次是BRE,SPF吞吐量最低.這是因?yàn)镾PF的尋路失敗率最高,其網(wǎng)絡(luò)吞吐量自然是最低的,這也是由于選路過(guò)于集中的原因引起的；而ESTROA和BRE算法在尋路失敗率上很很接近,則它們的網(wǎng)絡(luò)吞吐量也十分接近；相比之下,ESTROA稍優(yōu)于BRE算法.

D.網(wǎng)絡(luò)能效

圖7表示了三種算法網(wǎng)絡(luò)能效(bit/J)隨請(qǐng)求數(shù)目的變化情況.圖7表明,SPF具有最低的網(wǎng)絡(luò)能效,其次是BRE,ESTROA網(wǎng)絡(luò)能效最大.這是因?yàn)镾PF吞吐量最低和能耗較高,則其能效最低；ESTROA在吞吐量最大和能耗最低,則其能效最高.從圖7也可以看到,ESTORA能效相對(duì)于BRE提高了大約65%,這也說(shuō)明了功率能量比權(quán)重所選路徑的能效更優(yōu).圖7也表明,隨著請(qǐng)求數(shù)目的增多,三種算法的網(wǎng)絡(luò)能效有些波動(dòng),但是整體都維持在一個(gè)固定的水平.

E.網(wǎng)絡(luò)資源效率

圖8表示了三種算法網(wǎng)絡(luò)資源效率隨請(qǐng)求數(shù)目的變化情況.資源效率是為了頻效與能效平衡而提出的一個(gè)度量,該度量結(jié)合了網(wǎng)絡(luò)能效和頻效兩個(gè)方面去反應(yīng)網(wǎng)絡(luò)的情況.圖8表明,ESTROA在資源效率方面要由于其他兩個(gè)算法,分別提高了大約27%和160%；隨著請(qǐng)求數(shù)目的增多,三種算法的資源效率都呈現(xiàn)遞增趨勢(shì).圖8也表明,在進(jìn)行選路時(shí)結(jié)合功率和能量?jī)蓚€(gè)方面設(shè)計(jì)權(quán)重更適合對(duì)于網(wǎng)絡(luò)頻效和能效的整體優(yōu)化,而單單從一個(gè)方面進(jìn)行考慮往往無(wú)法滿足多目標(biāo)的優(yōu)化需求.

F.流質(zhì)量性能

假設(shè)有Z個(gè)數(shù)據(jù)流在移動(dòng)多跳Ad Hoc網(wǎng)絡(luò)中.數(shù)據(jù)流共有K類(C1,C2,C3,…CK)；每一類別有3個(gè)參數(shù)進(jìn)行描述分別是(Dk,Wk,λk),其中Dk表示Ck中數(shù)據(jù)流的最大延遲,Wk表示中數(shù)據(jù)流平均資源速率,λk表示中數(shù)據(jù)流的質(zhì)量影響系數(shù)；每一類中的所有流具有相同的影響系數(shù)；并且這個(gè)質(zhì)量影響系數(shù)可通過(guò)在解碼數(shù)據(jù)包時(shí)候衡量平均失真減少量(average distortion reduction).此外,對(duì)于,在鏈路l上最大傳輸速率表示為Tl,k,這個(gè)值取決于傳出功率.那么如果采用基于輪尋的時(shí)間分配,數(shù)據(jù)流的在鏈路上有效傳輸速率為.其中反應(yīng)了數(shù)據(jù)流的在鏈路上的時(shí)間分配比例.

設(shè),xz表示對(duì)于數(shù)據(jù)流的調(diào)度.那么表示運(yùn)用時(shí)數(shù)據(jù)流端到端延遲.通過(guò)前面的分析.可表示為：

(13)

其中,Lk表示第k類數(shù)據(jù)流的平均數(shù)據(jù)包長(zhǎng)度.

因此,從源節(jié)點(diǎn)n接收到的數(shù)據(jù)流質(zhì)量Qn可表示為：

(14)

其中,Nn,k表示從節(jié)點(diǎn)發(fā)出的數(shù)據(jù)流中第類數(shù)據(jù)流的個(gè)數(shù).I(·)表示一個(gè)指數(shù)函數(shù).

那么網(wǎng)絡(luò)的平均流質(zhì)量可表示為：

(15)

網(wǎng)絡(luò)的平均流質(zhì)量可進(jìn)一步表示為：

(16)

其中,Hk-max表示第類數(shù)據(jù)流的允許的最大跳數(shù),Hz(X)表示數(shù)據(jù)流的跳數(shù).

圖9表示三種算法在流質(zhì)量方面的對(duì)比情況.圖9表明ESTROA的流質(zhì)量?jī)?yōu)于BRE和SPF算法.這是因?yàn)镾PF選路過(guò)于集中因而會(huì)造成網(wǎng)絡(luò)鏈路利用不均勻,其網(wǎng)絡(luò)質(zhì)量也就最差；而ESTORA和BRE的網(wǎng)絡(luò)鏈路利用率優(yōu)于SPF算法,二者的網(wǎng)絡(luò)質(zhì)量更好.圖9也表明,ESTORA要稍優(yōu)于BRE算法,這也說(shuō)明ESTORA所選路徑在延遲方面更低一些；此外隨著節(jié)點(diǎn)數(shù)目的增多,三種算法的流質(zhì)量都有所增加,不過(guò)ESTROA和BRE的增加幅度更大一些,也就是說(shuō)明這兩個(gè)算法在請(qǐng)求數(shù)目增多時(shí)候,也能很好地保證網(wǎng)絡(luò)質(zhì)量.

G.節(jié)點(diǎn)移動(dòng)速度對(duì)資源效率的影響

圖10表示了ESTORA算法中節(jié)點(diǎn)移動(dòng)速度(從5m/s到20m/s之間變化)不斷變化時(shí)網(wǎng)絡(luò)資源效率的變化情況.圖10表明,隨著節(jié)點(diǎn)移動(dòng)速度的增加,網(wǎng)絡(luò)拓?fù)渥兓酱?網(wǎng)絡(luò)資源效率會(huì)出現(xiàn)下降的趨勢(shì),但在較高移動(dòng)速度時(shí)ESTORA仍表現(xiàn)出較好的性能.從圖10也可以看到,隨著請(qǐng)求數(shù)目的增多,網(wǎng)絡(luò)資源效率呈現(xiàn)遞增的趨勢(shì),這說(shuō)明ESTORA合理的路徑選擇并沒有使得網(wǎng)絡(luò)效率隨著請(qǐng)求的增多而有所降低,從而能很好地降低了網(wǎng)絡(luò)擁塞,提高了網(wǎng)絡(luò)性能.

5 結(jié)束語(yǔ)

本文研究了研究了無(wú)線多跳網(wǎng)絡(luò)中移動(dòng)Ad Hoc網(wǎng)絡(luò)能效與頻效權(quán)衡折中資源效率聯(lián)合優(yōu)化路由算法.首先通過(guò)對(duì)端到端鏈路的分析引出了無(wú)線網(wǎng)絡(luò)中能效與頻效權(quán)衡的多目標(biāo)優(yōu)化問(wèn)題,隨后給出了相關(guān)定義和聯(lián)合考慮移動(dòng)Ad Hoc能效和頻效的優(yōu)化模型,并利用多目標(biāo)理論中加權(quán)求和方法將多目標(biāo)問(wèn)題轉(zhuǎn)化為單目標(biāo)問(wèn)題,最后結(jié)合理論分析,提出了一種聯(lián)合考慮網(wǎng)絡(luò)能效和頻效的路由優(yōu)化算法.仿真結(jié)果表明,本文所提出的算法可行和有效的.

[1]Fettweis G,Zimmermann E.ICT energy consumption-trends and challenges[A].Proc.the International Symposium on Wireless Personal Multimedia Communications[C].2008.1-4.

[2]Hooper A.Green computing[J].Communications of the ACM,2008,51(10):11-13.

[3]Onireti O,Heliot F,Imran M.On the energy efficiency-spectral efficiency trade-off in the uplink of CoMP system[J].IEEE Transactions on Wireless Communications,2012,11(2):556-561.

[4]Deng L,Rui Y,Cheng P,et al.A unified energy efficiency and spectral efficiency tradeoff metric in wireless networks[J].IEEE Communication Letters,2013,17(1):55-58.

[5]Jiang D,Xu Z,Li W,et al.Network coding-based energy-efficient multicast routing algorithm for multi-hop wireless networks[J].Journal of Systems and Software,2015,104:152-165.

[6]Jiang D,Yao C,Xu Z,et al.Multi-scale anomaly detection for high-speed network traffic[J].Transactions on Emerging Telecommunications Technologies,2015,26(3):308-317.

[7]Jiang D,Xu Z,Liu J,et al.An optimization-based robust routing algorithm to energy-efficient networks for cloud computing[J].Telecommunication Systems,2016,63(1):1-10

[8]Dimitriou N,Polydoros A,Barnawi A.Cooperative path establishment for robust connectivity in mobile ad-hoc networks[J].Proc.2013 20th International Conference on Telecommunications (ICT),2013:1-5.

[9]Jiang D,Xu Z,Zhang P,et al.A transform domain-based anomaly detection approach to network-wide traffic[J].Journal of Network and Computer Applications,2014,40(2):292-306.

[10]Rizzelli G,Morea A,Tornatore M,et al.Energy efficient traffic-aware design of on-off multi-Layer translucent optical networks[J].Computer Networks,2012,56(10):2443-2455.

[11]Marler R,Arora J.Survey of multi-objective optimization methods for engineering[J].Structural and Multidisciplinary Optimization,2004,26(6):369-395.

[12]蔣定德,王興偉,郭磊,等.大尺度IP骨干網(wǎng)絡(luò)流量矩陣估計(jì)方法研究.電子學(xué)報(bào),2011,39(4):763-771.

Jiang Ding-de,Wang Xing-wei,Guo Lei,et al.Approach of traffic matrix estimation in large-scale IP backbone networks[J].Acta Electronica Sinica,2011,39(4):763-771.

[13] Jiang D,Xu Z,Nie L,et al.An approximate approach to end-to-end traffic in communication networks.Chinese Journal of Electronics,2012,21(4):705-710.

[14]Baker T,Al-Dawsari B,Tawfik H,et al.GreeDi:An energy efficient routing algorithm for big data on cloud[J].Ad Hoc Networks,2015,35(4):83-96.

[15]Li Q,Xu M,Yang Y,et al.Safe and practical energy-efficient detour routing in IP networks[J].IEEE/ACM Transactions on Networking,2014,22(6):1925-1937.

[16]Agrawal H,Johri P,Kumar A.Emerging trends in energy efficient routing protocols[A].Proc.the International Conference on Computing,Communication and Automation[C].2015.523-528.

[17]Zuo J,Dong C,Nguyen H,et al.Cross-layer aided energy-efficient opportunistic routing in Ad Hoc networks[J].IEEE Transactions on Communications,2014,62(2):522-535.

[18]Kaiser A,Boc M.Energy-efficient routing in IPv6 home networks[A].Proc.the 23rd International Conference on Computer Communication and Networks[C].2014.1-8.

[19]Sarker A,Fatema N,Binti B,et al.Performance evaluation of energy efficient routing algorithm for ad-hoc network[A].Proc.the International Conference on Electrical Engineering and Information and Communication Technology[C].2014.1-6.

[20]Ba-Hutair M,Saad M.A spectrum-efficient routing protocol for multi-hop 802.11 networks[A].Proc.the International Conference on Information and Communication Technology Research[C].2015.242-245.

[21]Wang Y,Sheng M,Lui K,et al.Spectrum-efficient routing algorithms with successive interference cancellation in multi-hop wireless networks[A].Proc.IEEE Wireless Communications and Networking Conference[C].2014.2492-2497.

[22]Shah G,Alagoz F,Fadel E,et al.A spectrum-aware clustering for efficient multimedia routing in cognitive radio sensor networks[J].IEEE Transactions on Vehicular Technology,2014,63(7):3369-3380.

[23]商云飛,徐明偉,李丹.聯(lián)網(wǎng)路由設(shè)備與協(xié)議節(jié)能研究綜述.電子學(xué)報(bào),2012,40(11):2290-2297.

Shang Yun-fei,XUu Ming-wei,Li Dan.Research on energy-saving routing devices and protocols in the internet[J].Acta Electronica Sinica,2012,40(11):2290-2297.

[24]劉權(quán),王曉東.MR2-GRADE:一種基于梯度值的無(wú)線傳感器網(wǎng)絡(luò)高能效多徑干擾避免路由協(xié)議.電子學(xué)報(bào),2011,39(3A):147-152.

Liu Quan,Wang Xiao-dong.MR2-GRADE:a high energy efficiency and interference-free multipath routing protocol based on grade for wireless sensor network[J].Acta Electronica Sinica,2011,39(3A):147-152.

[25]Kasprzak E,Lewis K.Pareto analysis in multi-objective optimization using the collinearity theorem and scaling method[J].Structural and Multi-disciplinary Optimization,2001,22(2):208-218.

何林波 男,1978年1月生于四川遂寧,碩士,講師,主要研究領(lǐng)域?yàn)榫W(wǎng)絡(luò)通信、移動(dòng)互聯(lián)網(wǎng)、無(wú)線網(wǎng)絡(luò),SDN等,為本文通訊作者.

E-mail:hlb@cuit.edu.cn

蔣定德 男,1974年2月生于四川德陽(yáng),博士,教授,博士生導(dǎo)師,主要研究方向?yàn)榫W(wǎng)絡(luò)測(cè)量、建模與優(yōu)化、軟件定義網(wǎng)絡(luò)、綠色通信等,為本文通訊作者.

E-mail:jiangdingde@ise.neu.edu.cn

仲維佳 男,1990年19月生于遼寧沈陽(yáng),碩士研究生,主要研究方向?yàn)榫W(wǎng)絡(luò)測(cè)量、綠色通信.

An Energy Efficiency and Frequency Efficiency Based Routing Optimization Algorithm

HE Lin-bo1,JIANG Ding-de2,ZHONG Wei-jia2

(1.CollegeofInformationSecurityEngineering,ChengduUniversityofInformationTechnology,Chengdu610225,China;2.CollegeofInformationScienceandEngineering,NortheasternUniversity,Shenyang110819,China)

Networks′ energy efficiency and frequency efficiency are regarded as current hot topic,which have an significant impact on network performance.However,the in-deep studies about energy efficiency and frequency efficiency problem and mobile Ad hoc networks are absent.More studies only consider networks′ energy efficiency and frequency efficiency of single object,while it is very few to combine networks′ energy efficiency and frequency efficiency.This paper analyzes energy efficiency and frequency efficiency problem in mobile Ad Hoc networks.Then we discuss the tradeoff between both them.Multi-objective optimization theory is used to build multi-objective optimization model combining networks′ energy efficiency and frequency efficiency.The weight sum method is exploited to convert the multi-objective optimization into the single-objective optimization.And we propose a notation of resource efficiency.Finally,we present a routing scheme for resource efficiency optimization in mobile Ad Hoc networks.Simulation results show that the proposed algorithm exhibits better performance.

mobile Ad Hoc networks;energy efficiency;multi-objective optimization;frequency efficiency;routing algorithm

2015-07-25；

2015-11-14；責(zé)任編輯：郭游

國(guó)家自然科學(xué)基金(No. 61571104, No.61071124), 遼寧省教育廳科學(xué)研究一般項(xiàng)目(No. L20150174), 新世紀(jì)優(yōu)秀人才支持計(jì)劃(No. NCET-11-0075), 中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資助(No. N120804004, No.N130504003).

TP393

A

0372-2112 (2016)10-2314-09

??學(xué)報(bào)URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.10.005