基于粒子群優(yōu)化的ad hoc網(wǎng)絡(luò)最小能耗多播路由算法

朱曉建，沈軍

(1.東南大學 計算機科學與工程學院，江蘇 南京 211189；2.東南大學 計算機網(wǎng)絡(luò)和信息集成教育部重點實驗室, 江蘇 南京 211189)

1 引言

無線ad hoc網(wǎng)絡(luò)由一組無線設(shè)備組成，在不需要使用網(wǎng)絡(luò)基礎(chǔ)設(shè)施的情況下，可以實現(xiàn)快速臨時組網(wǎng)，具有廣泛的應用。在無線ad hoc網(wǎng)絡(luò)中，節(jié)點使用電池提供能量，而電池的能量十分有限，一旦電池的能量耗盡，節(jié)點將不能繼續(xù)工作，網(wǎng)絡(luò)將不再連通。因此，在無線ad hoc網(wǎng)絡(luò)中，節(jié)能是一個核心問題，針對越來越多的多播應用，如何構(gòu)造最小能耗多播樹是一個重要問題。

文獻[1]指出在無線ad hoc網(wǎng)絡(luò)中無論使用全向天線還是使用有向天線，構(gòu)造最小能耗多播樹問題是一個NP難解問題，因此需要設(shè)計有效的啟發(fā)式算法以求得較好的近似最優(yōu)解。文獻[2]提出了在使用全向天線的情況下構(gòu)造最小能耗廣播樹的BIP(broadcast incremental power)算法和構(gòu)造最小能耗多播樹的MIP(multicast incremental power)算法，MIP算法首先利用BIP算法構(gòu)造一棵廣播樹，然后對該廣播樹進行修剪得到多播樹，未考慮不同的中繼節(jié)點選擇對構(gòu)造多播樹的影響。文獻[3]提出了在使用有向天線的情況下構(gòu)造最小能耗廣播樹的D-BIP(directional BIP)算法和構(gòu)造最小能耗多播樹的D-MIP(directional MIP)算法，與MIP算法基于BIP算法類似，D-MIP算法是基于D-BIP算法的。文獻[4]提出了一種優(yōu)化最小能耗廣播樹的r-shrink算法，該算法首先基于其他算法構(gòu)造一棵廣播樹，然后以降低樹的總能耗為目標，對樹的結(jié)構(gòu)進行調(diào)整。文獻[5]提出了一種構(gòu)造最小能耗廣播樹的模擬退火算法，利用BIP算法構(gòu)造初始解，求解質(zhì)量顯著優(yōu)于BIP算法，但僅對中小規(guī)模網(wǎng)絡(luò)的最小能耗廣播樹問題求解效果較好。文獻[6]提出了一個構(gòu)造最小能耗多播樹的蟻群算法，并在構(gòu)造過程中使用r-shrink算法優(yōu)化多播樹的構(gòu)造，優(yōu)化效果較好，但運行時間較長。文獻[7]提出了一種構(gòu)造最小能耗多播樹的PSOR算法，對到達非多播組成員的傳輸建立懲罰函數(shù)，在多播樹的構(gòu)造過程中基于收縮重疊傳輸范圍改變多播樹的結(jié)構(gòu)，以減少多播能耗，并給出了理論上的最大近似比，該算法的時間復雜度較高。這些算法大多是直接針對最小能耗廣播樹的構(gòu)造，很少是直接針對最小能耗多播樹的構(gòu)造，并且不同算法的適用情況不同。文獻[8]提出了一種新型離散粒子群優(yōu)化算法求解帶權(quán)無向圖的Steiner樹問題，通過搜索最優(yōu)中繼節(jié)點來獲取Steiner樹，但由于無線傳輸本身所固有的多播特性使得無線網(wǎng)絡(luò)的最小能耗多播樹問題不同于Steiner樹問題。文獻[9]首先對最小能耗多播樹問題進行整數(shù)線性規(guī)劃，然后運用一種多相離散粒子群算法分布式地計算該整數(shù)線性規(guī)劃的最優(yōu)解，引入共生機制處理約束，該方法計算復雜度較高。

針對不同的中繼節(jié)點選擇對構(gòu)造最小能耗多播樹的影響，本文提出了一種改進的離散粒子群算法，引入慣性權(quán)重策略以平衡離散粒子群算法的全局搜索能力和局部搜索能力，以優(yōu)化在使用全向天線和有向天線情況下的最小能耗多播樹的構(gòu)造，并通過相關(guān)的模擬實驗驗證了改進后的離散粒子群算法的優(yōu)化能力，以及優(yōu)化最小能耗多播樹構(gòu)造的有效性。

2 問題模型

考慮靜態(tài)無線ad hoc網(wǎng)絡(luò)由若干個無線節(jié)點構(gòu)成，節(jié)點的位置已知。節(jié)點配有多個收發(fā)器可以同時支持多個多播會話，并且節(jié)點可以動態(tài)地調(diào)整自身的發(fā)送能量，本文只考慮節(jié)點的發(fā)送能量，不考慮接收能量和處理能量。

采用與文獻[1～3]相似的天線模型和無線傳播模型。在使用全向天線的情況下，假設(shè)均勻傳播，信號能量按照 r-α衰減，r是到信號源的距離，α為通信媒介參數(shù)，其值取決于通信介質(zhì)，通常介于2和4之間，本文假設(shè)α=2。當節(jié)點i的傳輸能量pi≥時，節(jié)點j可以成功接收到節(jié)點i發(fā)送的信號，rij為節(jié)點i和節(jié)點j之間的距離，βj為節(jié)點j的接收能量門限。假設(shè)所有節(jié)點的接收能量門限都相同且歸一化為1。節(jié)點i的傳輸范圍由節(jié)點i的傳輸距離ri所決定，節(jié)點i的傳輸能量pi=。在使用有向天線的情況下，假設(shè)節(jié)點的傳輸能量均勻分布在天線波束內(nèi)，當節(jié)點 i的傳輸能量 pi≥θi/360×時，位于節(jié)點i的天線波束內(nèi)的節(jié)點j可以成功接收到節(jié)點i發(fā)送的信號，θi為節(jié)點i的波束寬度。節(jié)點i的傳輸范圍不僅取決于節(jié)點i的傳輸距離ri，還取決于節(jié)點 i的波束寬度 θi，節(jié)點 i的傳輸能量 pi=max{θi,θmin}/360×，其中 θmin為最小波束寬度。和使用全向天線相比，由于有向天線的波束較窄，使用有向天線使得在給定傳輸距離時可以節(jié)省傳輸能量，或者在給定傳輸能量時可以延長傳輸距離。位于節(jié)點 i傳輸范圍內(nèi)的節(jié)點都可以接收到節(jié)點 i所發(fā)送的信號，即無線傳輸本身具有多播特性(WMA, wireless multicast advantage)，WMA特性使得無線多播不同于有線多播。

假設(shè)網(wǎng)絡(luò)中各個節(jié)點的傳輸能量均確定，可以將網(wǎng)絡(luò)模型化為一個有向圖G=(V, E)，V表示網(wǎng)絡(luò)節(jié)點集合，邊集E定義為：對于V中的任意節(jié)點i、j, ＜i, j＞∈E當且僅當節(jié)點j位于節(jié)點i的傳輸范圍之內(nèi)。由于節(jié)點的傳輸能量p可以在一定的范圍內(nèi)進行調(diào)節(jié)(p≤pmax，pmax為節(jié)點的最大傳輸能量)，在調(diào)節(jié)節(jié)點傳輸能量的同時，節(jié)點的傳輸距離發(fā)生變化，相關(guān)的網(wǎng)絡(luò)鏈路被添加或移除，網(wǎng)絡(luò)拓撲結(jié)構(gòu)也相應發(fā)生變化。對于給定的網(wǎng)絡(luò)G，以及多播會話指定的發(fā)送節(jié)點s、接收節(jié)點集D，D={d1，d2，…，dg}，網(wǎng)絡(luò)中除了發(fā)送節(jié)點s和目標節(jié)點D之外的其他節(jié)點都視為可參與多播會話的中繼節(jié)點，本文研究的是如何建立基于源端的多播樹 T(VT,ET)，T的根節(jié)點是 s，T的任意葉子節(jié)點 l∈D，T中除了源節(jié)點s和目標節(jié)點D之外，其余節(jié)點為中繼節(jié)點。

在使用全向天線的情況下，T中任一節(jié)點i的傳輸能量 pi取決于它的最大鏈路傳輸能量，即；在使用有向天線的情況下，T中任一節(jié)點i的傳輸能量pi取決于其最大鏈路傳輸能量和其波束寬度，即樹 T的總能耗 p(T)為各個節(jié)點的能耗之和，即

假設(shè)網(wǎng)絡(luò)中各節(jié)點的位置相對固定，每個節(jié)點的最大傳輸能量均為 pmax，pmax應足夠大以使得多播會話得以進行。求解最小能耗多播樹問題可表示為：對于給定的網(wǎng)絡(luò)G，以及多播會話指定的源節(jié)點s和目標節(jié)點集D，尋找一棵以源節(jié)點s為根并且可以到達所有目標節(jié)點D的樹T，在滿足節(jié)點傳輸能量 p≤pmax的條件下為節(jié)點分配合適的傳輸能量，使得樹的總能耗p(T)最小。

3 改進的離散粒子群算法

粒子群優(yōu)化(PSO, particle swarm optimization)[10,11]算法是一種利用粒子群體進行隨機搜索的智能優(yōu)化算法。PSO由一群粒子組成，每個粒子代表問題的一個潛在解，具有一個隨機速度，飛行于解空間執(zhí)行隨機搜索。搜索過程從問題的一個解集開始。PSO模擬社會行為，每個粒子記錄自身所經(jīng)歷的最好位置，并且學習群體所經(jīng)歷的最好位置。粒子在飛行過程中追蹤自身和群體迄今為止所經(jīng)歷的最好位置，并保持慣性，飛行速度具有隨機性，以盡力搜索到全局最優(yōu)解。PSO具有簡單高效，并行性好、收斂快等優(yōu)點。

假設(shè)在m維解空間中，執(zhí)行搜索的粒子群由n個粒子組成，向量Xi=(xi1, xi2, …, xim)T表示第i個粒子的位置，向量Vi=(vi1, vi2, …, vim)T表示第i個粒子的速度。粒子在解空間執(zhí)行搜索的過程中，向量Pi=(pi1, pi2, …, pim)T表示第i個粒子自身所經(jīng)歷的最好位置，Pi對應的適應度值為個體極值pbesti。每個粒子共享整個群體迄今為止所搜索到的最優(yōu)解，全局極值索引 g為所有粒子中個體極值最優(yōu)的那個粒子的索引，則向量Pg=(pg1, pg2, …, pgm)T表示所有粒子所經(jīng)歷的最好位置，Pg對應的適應度值 pbestg為全局極值。在連續(xù)粒子群算法中粒子的速度和位置按下式更新：

其中，c1、c2表示加速因子，通常取值為2；rand1()、rand2()為均勻分布在區(qū)間[0,1]上的隨機函數(shù)；粒子速度被限制在某個范圍之內(nèi)，即|vij|≤vmax，vmax表示粒子運動速度的最大值。

在離散粒子群優(yōu)化(DPSO，discrete particle swarm optimization)算法[12]中，粒子位置Xi的每一維 xij取值僅限于 0和 1，粒子速度 Vi的每一維vij表示xij取值為1的可能性，vmax通常取值為6.0。粒子速度仍按式(1)更新，粒子位置按下式更新：

其中，s(vij(t+1))為sigmoid函數(shù)，rand()產(chǎn)生服從在區(qū)間[0,1]上均勻分布的隨機數(shù)。

為了提高算法獲取最優(yōu)解的能力，通常在計算前期進行有效的全局搜索，以定位最優(yōu)解的大致位置，在計算后期進行局部搜索，以獲得精確度較高解[13～15]，然而DPSO算法不能有效地平衡全局搜索能力和局部搜索能力。令Δv=vij(t+1)-vij(t)=c1rand1()(pij-xij)+c2rand2()(pgj-xij)，當 pij=pgj=1，xij=0 時，Δv＞0，vij增大，s(vij)增大，xij=1的概率增大；當pij=pgj=0，xij=1 時，Δv＜0，vij減小，s(vij)減小，xij=0的概率增大；當xij=pij=pgj時，Δv=0，vij不變，s(vij)不變，xij以原有概率保持不變；當 pij≠pgj時，xij趨于pij或pgj。因此，在DPSO算法中，粒子追尋極值點的能力較強，算法的局部搜索能力較強，但算法容易早熟收斂，全局搜索能力較差。

在連續(xù)粒子群算法中，通常使用慣性權(quán)重w來平衡算法的全局搜索能力和局部搜索能力[13,14]，w通常初值為 0.9，隨著迭代的進行而線性下降至0.4[13～15]。然而這種逐漸遞減的慣性權(quán)重不能直接適用于DPSO算法。如果DPSO算法使用慣性權(quán)重w，則 vij(t+1)=wvij(t)+c1rand1()(pij-xij)+c2rand2()(pgj-xij)，Δv=vij(t+1)-vij(t)=(w-1)vij(t)+c1rand1()(pij-xij)+c2r and2()(pgj-xij)，c1rand1()(pij-xij)+c2rand2()(pgj-xij)使粒子具有局部搜索能力，(w-1)vij(t)具有隨機性和無記憶性，使粒子具有擴大搜索空間的趨勢、探索新區(qū)域的能力，從而使粒子具有全局搜索能力。當0≤ w≤1時，隨著w的減小，|(w-1) vij(t)|逐漸增大，全局搜索能力逐漸增強，反之，w越大，|(w-1) vij(t)|越小，局部搜索能力越強。因此，逐漸遞減的慣性權(quán)重不適用于DPSO算法。

為了克服DPSO算法易于早熟收斂、全局搜索能力較差的問題，在DPSO算法中引入一種逐漸遞增的慣性權(quán)重，以有效地平衡算法的全局搜索能力和局部搜索能力，提高算法獲取全局最優(yōu)解的能力。在計算前期，使慣性權(quán)重w由wa(wa[0,1])∈逐漸增大至wb(wb[0,1]∈，wb＞wa),從而使算法具有較強的全局搜索能力；在計算后期，使慣性權(quán)重w保持為 wb不變，從而使算法具有較強的局部搜索能力，以進行精細的局部搜索。在改進后的DPSO算法(MDPSO，modified DPSO)中，粒子速度按式(4)更新，慣性權(quán)重按式(5)更新：

其中，td為增強全局搜索能力的時期，wa、wb、 td需根據(jù)具體情況進行設(shè)定。

4 構(gòu)造最小能耗多播樹的粒子群算法

MIP(D-MIP)算法[2,3]是基于 BIP(D-BIP)算法的，利用了無線傳輸?shù)?WMA特性，首先由BIP(D-BIP)算法構(gòu)造一棵廣播樹，然后修剪該廣播樹來獲得多播樹，其步驟如下。

Step1 初始化多播樹T(VT,ET)只包含源節(jié)點s，VT←{s}，ET←?，初始化 V為網(wǎng)絡(luò)中所有節(jié)點的集合。

Step2 對于任意一對節(jié)點 i和節(jié)點 j，i∈VT，j∈V-VT，計算將j作為i的孩子節(jié)點后節(jié)點i的能耗pi,j，如果 pi,j≤pmax，計算節(jié)點i所增加的能耗Δi,j←pi,j-pi，其中，pi為j成為i的孩子之前節(jié)點i的能耗。

Step3 如果對于任意一對節(jié)點 i和節(jié)點 j，i∈VT，j∈V-VT，pi,j＞pmax，返回計算失敗。

Step4 找到最小的Δi,j對應的節(jié)點i和節(jié)點j，將節(jié)點j加入VT，將邊＜i, j＞加入ET。

Step5 如果 VT≠V，則轉(zhuǎn) Step2。

Step6 對T進行修剪，剪除對于到達目標節(jié)點所不需要的邊，即如果節(jié)點及其下游節(jié)點中不包含目標節(jié)點，就將其排除。

Step7 輸出多播樹T及其總能耗，返回計算成功。

可見，MIP(D-MIP)算法在構(gòu)造多播樹時，將網(wǎng)絡(luò)中除了源節(jié)點和目標節(jié)點之外的其他所有節(jié)點都作為中繼節(jié)點參與多播樹的構(gòu)造，未考慮對參與多播樹構(gòu)造的中繼節(jié)點進行篩選，導致算法結(jié)果誤差較大。如果節(jié)點的最大傳輸能量pmax較小，會導致網(wǎng)絡(luò)無法連通，算法將返回計算失敗。

圖1所示的一個實例演示了2種不同的中繼節(jié)點選擇對MIP算法計算結(jié)果的影響。在該實例中，網(wǎng)絡(luò)共有5個節(jié)點，各節(jié)點的坐標分別為n1(15,11)、n2(10,12)、n3(15,5)、n4(2,6)、n5(2,9)，其中，n2為源節(jié)點，n3、n4為目標節(jié)點，節(jié)點的最大傳輸能量無限制即pmax=∞。如果使用除了源節(jié)點和目標節(jié)點之外的其他所有節(jié)點（包括 n1、n5）作為中繼節(jié)點參與多播樹的構(gòu)造，使用MIP算法構(gòu)造多播樹：初始時 VT={n2}、V={n1,n2,n3,n4,n5}，首先選擇距離源節(jié)點n2最近的節(jié)點n1加入多播樹得到VT={n2,n1}，然后根據(jù)最小化能耗增加原則，依次選擇節(jié)點 n3、n5、n4加入多播樹，結(jié)果如圖 1(a)所示，節(jié)點 n2的能耗p2=max{,}=73，節(jié)點n5的能耗p5==9，節(jié)點 n1的能耗 p1==36，多播樹的總能耗為p2+p5+p1=118。如果僅使用節(jié)點n5作為中繼節(jié)點參與多播樹的構(gòu)造，使用MIP算法構(gòu)造多播樹：初始時 VT={n2}、V={n2,n3,n4,n5}，首先選擇距離源節(jié)點n2最近的節(jié)點，由于節(jié)點n1未參與多播樹的構(gòu)造，所以選擇節(jié)點 n5加入多播樹得到 VT={n2,n5}，然后根據(jù)最小化能耗增加原則依次選擇節(jié)點 n3、n4加入多播樹，結(jié)果如圖 1(b)所示，節(jié)點 n2的能耗p2=max{,}= 74，節(jié)點n5的能耗p5==9，多播樹的總能耗為p2+p5=83。

圖1 不同中繼節(jié)點選擇對MIP構(gòu)造最小能耗多播樹的影響

由此可見，選擇不同的中繼節(jié)點集對MIP算法的計算結(jié)果影響較大，可以通過比較MIP算法對不同中繼節(jié)點集求得的結(jié)果，來獲取一個最優(yōu)中繼節(jié)點集，從而降低 MIP算法的計算誤差。假設(shè)集合 R={u1,u2,…,um}表示網(wǎng)絡(luò)中除去源節(jié)點和目標節(jié)點之外其他所有節(jié)點的集合，則 R的冪集就表示該問題的解空間，由于MDPSO算法是對問題解空間的一次全局搜索過程，因而可以使用MDPSO算法求解最優(yōu)中繼節(jié)點集，從而優(yōu)化最小能耗多播樹的構(gòu)造。在MDPSO算法中，每個粒子的位置代表一個中繼節(jié)點集，粒子i位置Xi的第j維xij=1表示該維對應的中繼節(jié)點uj(uj∈R)參與多播樹的構(gòu)造，xij=0表示uj不參與多播樹的構(gòu)造，粒子的維數(shù)為網(wǎng)絡(luò)中除去源節(jié)點和目標節(jié)點之外其他所有節(jié)點的個數(shù)，即為|R|。在MDPSO算法中，在使用全向天線的情況下，使用MIP算法計算粒子的適應度值，在使用有向天線的情況下，使用D-MIP算法計算粒子的適應度值，即在選擇了特定中繼節(jié)點集的基礎(chǔ)上，使用MIP或D-MIP算法構(gòu)造多播樹，并計算樹的總能耗。對于選定的某個中繼節(jié)點集，由于pmax的限制，由中繼節(jié)點以及多播會話指定的源節(jié)點和目標節(jié)點構(gòu)成的子網(wǎng)絡(luò)不一定能連通，因而該中繼節(jié)點集不一定是可行解。求解最小能耗多播樹的MDPSO算法如下。

Step1 隨機初始化粒子位置X1，X2，…，Xn，xij{0,1}∈；隨機初始化粒子速度V1，V2，…，Vn，|vij|≤vmax；初始化粒子個體極值 pbest1←∞，pbest2←∞，…，pbestn←∞；初始化全局極值索引g←1；初始化總迭代次數(shù) duration；初始化迭代次數(shù)變量t←0；初始化粒子標識變量i←1。

Step2 如果t=duration，則轉(zhuǎn)Step12。

Step3 按式(5)更新慣性權(quán)重w。

Step4 如果 i＞n，則轉(zhuǎn) Step11。

Step5 使用 MIP(D-MIP)算法計算第 i個粒子的適應度值f(Xi)，如果計算失敗，轉(zhuǎn)Step8。

Step6 如果f(Xi)＜pbesti，那么更新個體極值點Pi←Xi，更新個體極值 pbesti←f(Xi)。

Step7 如果pbesti＜pbestg，那么更新全局極值索引g←i。

Step8 按式(4)更新粒子的速度Vi。

Step9 按式(3)更新粒子的位置Xi。

Step10 i←i+1，轉(zhuǎn) Step4。

Step11 t←t+1，i←1，轉(zhuǎn) Step2。

Step12 輸出全局極值點 Pg，輸出全局極值pbestg。

5 實驗結(jié)果

為了驗證MDPSO算法協(xié)調(diào)全局搜索能力和局部搜索能力的有效性，采用文獻[16]提出的二進制編碼的基因型多樣性的測度方法來度量粒子群的多樣性，粒子群多樣性，其中，n為粒子數(shù)，m為粒子的維數(shù)，hij為粒子 i到粒子 j的海明距離。以MIP算法計算粒子的適應度，比較MDPSO算法與DPSO算法在運行過程中粒子群多樣性的變化情況。隨機生成一個包含 50個節(jié)點的網(wǎng)絡(luò)，節(jié)點隨機分布在1 000m×1 000m的平面區(qū)域內(nèi)，目標節(jié)點數(shù)為總節(jié)點數(shù)的 1/3，隨機產(chǎn)生源節(jié)點s和目標節(jié)點集D，節(jié)點最大傳輸能量pmax=∞，對該網(wǎng)絡(luò)分別運行MDPSO算法與DPSO算法。在選取粒子群規(guī)模時，如果粒子數(shù)越多，算法的計算時間越長，如果粒子數(shù)越少，算法計算結(jié)果的精確度越低，因此應綜合考慮算法的計算精確度和計算時間，通過多次實驗測試得出取粒子群規(guī)模 n=30較合適。每個粒子的位置代表一個參與多播樹構(gòu)造的中繼節(jié)點集，粒子的維數(shù)為除去源節(jié)點和目標節(jié)點之外其余節(jié)點的個數(shù)，即m=50-1-50/3=33，算法總迭代次數(shù)duration=100，wa=0.4，wb=1.0，td=0.5duration。每種算法運行20次，統(tǒng)計每種算法在這 20次運行過程中每次迭代后粒子群的平均多樣性，算法的粒子群多樣性變化情況如圖2所示。在DPSO算法運行過程中，粒子群的多樣性很快降低，算法很快收斂，全局搜索能力較差。在MDPSO算法運行過程中，在計算前期，粒子群的多樣性較高，全局搜索能力較強，在計算后期，粒子群多樣性降低，局部搜索能力較強。因此，MDPSO算法有效地平衡了全局搜索能力和局部搜索能力。

圖2 MDPSO和DPSO粒子群多樣性變化情況比較

為了驗證MDPSO算法的優(yōu)化能力，對幾個不同規(guī)模的網(wǎng)絡(luò)分別運行 MDPSO算法和 DPSO算法。在使用全向天線時使用MIP算法計算粒子的適應度，在使用有向天線時使用DMIP算法計算粒子的適應度。每種算法對同一個網(wǎng)絡(luò)運行 20次，統(tǒng)計求得平均解。粒子群規(guī)模 n=30，算法總迭代次數(shù)duration=100，wa=0.4，wb=1.0，td=0.5duration。網(wǎng)絡(luò)節(jié)點隨機分布在 1 000m×1 000m的平面區(qū)域內(nèi)，目標節(jié)點數(shù)為總節(jié)點數(shù)的 1/3，隨機產(chǎn)生源節(jié)點s和目標節(jié)點集D，節(jié)點最大傳輸能量pmax=∞。實驗結(jié)果如表1所示，MDPSO算法求得的平均解普遍優(yōu)于DPSO算法，表明MDPSO算法的優(yōu)化能力要優(yōu)于DPSO算法。

為了驗證構(gòu)造最小能耗多播樹的MDPSO算法的性能，在基于Java 6.0的MyEclipse 8.5平臺上實現(xiàn)了MDPSO算法，并在處理器為Intel Q6600、內(nèi)存為2GB、操作系統(tǒng)為Microsoft Windows XP的主機上運行實驗程序。為了考慮MDPSO算法對不同節(jié)點最大傳輸能量 pmax的適應性，對多種不同的pmax分別進行了實驗。對于每一種pmax，與文獻[6]和文獻[17]類似，分別對30個不同的網(wǎng)絡(luò)，每個網(wǎng)絡(luò)進行30次實驗，統(tǒng)計所有計算結(jié)果的總平均值。每次實驗中隨機產(chǎn)生源節(jié)點s和目標節(jié)點集D，同一個網(wǎng)絡(luò)的30次實驗中，每10次實驗分別采用目標節(jié)點數(shù)為總節(jié)點數(shù)的 1/3、1/2、2/3。每個網(wǎng)絡(luò)包含 50個節(jié)點，隨機分布在1 000m×1 000m的平面區(qū)域內(nèi)。MDPSO算法的總迭代次數(shù) duration取為 30，wa=0.6，wb=1.0，td=0.5duration，和目標節(jié)點數(shù)分別為總節(jié)點數(shù)的1/3、1/2、2/3相對應，粒子數(shù)分別取為30、25、20。

表1 MDPSO和DPSO優(yōu)化能力比較

表2 MDPSO和MIP計算結(jié)果比較

表2顯示了在使用全向天線的情況下，對于多種pmax，MIP算法和MDPSO算法的運行結(jié)果。表3顯示了在使用有向天線的情況下并且最小波束寬度 θmin=90°時，對于多種 pmax，D-MIP算法和MDPSO算法的運行結(jié)果。實驗結(jié)果表明，對于不同的 pmax，MDPSO算法均能有效地優(yōu)化最小能耗多播樹的構(gòu)造。在使用全向天線的情況下，當pmax較小時MDPSO算法在計算過程中所遇到的不可行解較多，隨著pmax的增加不可行解逐漸減少；而在使用有向天線的情況下，由于有向天線減小了波束寬度，延長了通信距離，即使當pmax較小時不可行解也很少。與MIP(D-MIP)算法相比，MDPSO算法由于在計算過程中進行了多次迭代，其計算時間相對較長，然而，MDPSO算法本質(zhì)上是利用粒子群體進行并行尋優(yōu)，從而易于設(shè)計分布式并行程序來降低算法的執(zhí)行時間。

表3 MDPSO和D-MIP計算結(jié)果比較

6 結(jié)束語

在無線ad hoc網(wǎng)絡(luò)中如何構(gòu)造最小能耗多播路由樹是一個重要問題。本文首先分別分析了在使用全向天線和有向天線的情況下該問題的不同數(shù)學模型，針對不同的中繼節(jié)點選擇對構(gòu)造最小能耗多播樹的影響，提出了一種改進的離散粒子群算法，以優(yōu)化最小能耗多播樹的構(gòu)造，最后通過模擬實驗驗證了改進的離散粒子群算法有效地優(yōu)化了最小能耗多播樹的構(gòu)造。進一步的研究工作包括將MDPSO算法與一些局部優(yōu)化算法相結(jié)合，以及如何更好地設(shè)定MDPSO算法的控制參數(shù)，以獲取更優(yōu)的近似最小能耗多播樹。

[1] GUO S, YANG O. Energy-aware multicasting in wireless ad hoc networks: a survey and discussion[J]. Computer Communications,2007, 30(9):2129-2148.

[2] WIESELTHIER J E, NGUYEN G D, EPHREMIDES A. On the construction of energy-efficient broadcast and multicast trees in wireless networks[A]. Proceedings of IEEE INFOCOM’2000[C]. Tel Aviv, Israel, 2000. 585-594.

[3] WIESELTHIER J E, NGUYEN G D, EPHREMIDES A. Energy-aware wireless networking with directional antennas: the case of session-based broadcasting and multicasting[J]. IEEE Transactions on Mobile Computing, 2002, 1(3): 176-191.

[4] DAS A K，MARKS R J，EL-SHARKAWI M, et al. R-shrink: a heuristic for improving minimum power broadcast trees in wireless networks[A]. Proceedings of IEEE GLOBECOM’03[C]. San Francisco, CA, USA, 2003. 523-527.

[5] MONTEMANNI R, GAMBARDELLA L M, DAS A K. The minimum power broadcast problem in wireless networks: a simulated annealing approach[A]. Proceedings of the 2005 IEEE Wireless Communications and Networking Conference [C]. New Orleans, LA, USA, 2005. 2057-2062.

[6] HERNANDEZ H, BLUM C. Energy-efficient multicasting in wireless ad-hoc networks: an ant colony optimization approach[A]. Proceedings of the 2008 IEEE International Symposium on Wireless Communication Systems[C]. Reykjavik, Iceland, 2008. 667-671.

[7] MIN M, O'BRIEN A F, SHIN S Y. Partitioning-based SOR for minimum energy multicast tree problem in wireless ad hoc networks[A].Proceedings of the 18th International Conference on Computer Communications and Networks[C]. San Francisco, CA, USA, 2009. 1-6.

[8] ZHONG W L, HUANG J, ZHANG J. A novel particle swarm optimization for the Steiner tree problem in graphs[A]. Proceedings of the 2008 IEEE Congress on Evolutionary Computation[C]. Hong Kong,China, 2008. 2460-2467.

[9] YUAN P, JI C L, ZHANG Y, et al. Optimal multicast routing in wireless ad hoc sensor networks[A]. Proceedings of 2004 IEEE International Conference on Networking, Sensing and Control[C]. 2004.367-371.

[10] KENNEDY J, EBERHART R. Particle swarm optimization[A].Proceedings of the 1995 IEEE International Conference on Neural Networks[C]. Perth, Australia, 1995. 1942-1948.

[11] EBERHART R, KENNEDY J. A new optimizer using particle swarm theory[A]. Proceedings of the Sixth International Symposium on Micro Machine and Human Science[C]. Nagoya, Japan, 1995. 39-43.

[12] KENNEDY J, EBERHART R. A discrete binary version of the particle swarm algorithm[A]. Proceedings of the 1997 IEEE International Conference on Systems, Man, and Cybernetics[C]. Orlando, FL, USA,1997. 4104-4108.

[13] SHI Y, EBERHART R. A modified particle swarm optimizer[A].Proceedings of the 1998 IEEE International Conference on Evolutionary Computation[C]. 1998. 69-73.

[14] SHI Y, EBERHART R. Empirical study of particle swarm optimization[A]. Proceedings of the 1999 Congress on Evolutionary Computation[C]. Washington, DC, USA, 1999. 1945-1950.

[15] SHI Y, E-BERHART R. Parameter selection in particle swarm optimization[A]. Proceeding of the 1998 Annual Conference on Evolutionary Programming[C]. San Dingo, CA, USA, 1998.591-600.

[16] 武曉今，朱仲英. 遺傳算法多樣性測度問題研究[J]. 信息與控制,2005, 34(4): 416-422.WU X J, ZHU Z Y. Research on diversity measure of genetic algorithms[J]. Information and Control, 2005, 34(4): 416-422.

[17] AL-SHIHABI S, MERZ P, WOLF S. Nested partitioning for the minimum energy broadcast problem[A]. LIUN 2007 II, Learning and Intelligent Optimization[C]. 2007. 1-11.