朱曉建，沈軍

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

1 引言

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

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

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

2 問(wèn)題模型

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

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

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

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

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

3 改進(jìn)的離散粒子群算法

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

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

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

在離散粒子群優(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]上均勻分布的隨機(jī)數(shù)。

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

在連續(xù)粒子群算法中，通常使用慣性權(quán)重w來(lái)平衡算法的全局搜索能力和局部搜索能力[13,14]，w通常初值為 0.9，隨著迭代的進(jìn)行而線性下降至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)具有隨機(jī)性和無(wú)記憶性，使粒子具有擴(kuò)大搜索空間的趨勢(shì)、探索新區(qū)域的能力，從而使粒子具有全局搜索能力。當(dāng)0≤ w≤1時(shí)，隨著w的減小，|(w-1) vij(t)|逐漸增大，全局搜索能力逐漸增強(qiáng)，反之，w越大，|(w-1) vij(t)|越小，局部搜索能力越強(qiáng)。因此，逐漸遞減的慣性權(quán)重不適用于DPSO算法。

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

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

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

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

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

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

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

Step4 找到最小的Δi,j對(duì)應(yīng)的節(jié)點(diǎn)i和節(jié)點(diǎn)j，將節(jié)點(diǎn)j加入VT，將邊＜i, j＞加入ET。

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

Step6 對(duì)T進(jìn)行修剪，剪除對(duì)于到達(dá)目標(biāo)節(jié)點(diǎn)所不需要的邊，即如果節(jié)點(diǎn)及其下游節(jié)點(diǎn)中不包含目標(biāo)節(jié)點(diǎn)，就將其排除。

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

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

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

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

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

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

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

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

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

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

Step6 如果f(Xi)＜pbesti，那么更新個(gè)體極值點(diǎn)Pi←Xi，更新個(gè)體極值 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 輸出全局極值點(diǎn) Pg，輸出全局極值pbestg。

5 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

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

在無(wú)線ad hoc網(wǎng)絡(luò)中如何構(gòu)造最小能耗多播路由樹是一個(gè)重要問(wèn)題。本文首先分別分析了在使用全向天線和有向天線的情況下該問(wèn)題的不同數(shù)學(xué)模型，針對(duì)不同的中繼節(jié)點(diǎn)選擇對(duì)構(gòu)造最小能耗多播樹的影響，提出了一種改進(jìn)的離散粒子群算法，以優(yōu)化最小能耗多播樹的構(gòu)造，最后通過(guò)模擬實(shí)驗(yàn)驗(yàn)證了改進(jìn)的離散粒子群算法有效地優(yōu)化了最小能耗多播樹的構(gòu)造。進(jìn)一步的研究工作包括將MDPSO算法與一些局部?jī)?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] 武曉今，朱仲英. 遺傳算法多樣性測(cè)度問(wèn)題研究[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.