沈 軍 朱曉建

(東南大學計算機科學與工程學院,南京 211189)

在使用電池提供能量的無線自組網中,節(jié)能問題至關重要.使用定向天線可以使得波束集中在需要被覆蓋的區(qū)域,從而可以節(jié)省節(jié)點能耗和減少傳輸干擾.在構造廣播路由時,僅最小化總能耗可能會導致某些節(jié)點因能量消耗過快而較早地停止工作,為了最大化網絡生命期需要考慮如何均衡各節(jié)點的能量消耗[1].網絡生命期通常定義為直至網絡中首次出現(xiàn)能量耗盡的節(jié)點所持續(xù)的時間[2].

文獻[2-3]針對在使用全向天線時的最大生命期廣播問題,提出了構造最大生命期廣播樹的多項式時間算法,并證明了所提算法可計算出全局最優(yōu)解.雖然在使用全向天線時的最大生命期廣播/多播問題是P問題,但是在使用定向天線時的最大生命期廣播/多播問題卻是NP完全問題[1,4].文獻[4]首先證明了使用單波束定向天線的靜態(tài)最大生命期多播樹構造問題是一個NP完全問題,提出了一種后處理算法MLR-MD,該算法以一棵由源節(jié)點一跳直接覆蓋所有目標節(jié)點的多播樹開始,然后啟發(fā)式地迭代改進多播樹的生命期,但當在最大傳輸功率的限制下源節(jié)點不能直接覆蓋所有目標節(jié)點時MLR-MD無法得到初始多播樹.文獻[5]討論了使用定向天線的無線自組網中能量有效的多播問題,在構造最小功率多播樹時考慮節(jié)點的剩余能量,增大剩余能量較少的節(jié)點的使用代價,以避免使用剩余能量較少的節(jié)點,從而延長網絡生命期.文獻[6]給出了在使用定向天線時的最大生命期多播樹的混合整數線性規(guī)劃,可用來評價啟發(fā)式算法的求解質量.文獻[7]提出了一種構造使用定向天線時的最大生命期多播樹的D-DPMT算法，該算法在構造多播樹的過程中考慮節(jié)點波束寬度最小化，在每次迭代時選擇一條權重(考慮波束寬度的鏈路功率與節(jié)點剩余能量之比)最小的邊加入多播樹.D-DPMT由于直接考慮了鏈路生命期，所以求解質量優(yōu)于文獻[5]的算法.文獻[8]提出了一種構造最大生命期多播樹的MMT-DA算法，該算法是基于搜索-增長操作，但有向邊的權重僅考慮了該有向邊對應的傳輸半徑.文獻[9-10]提出了一種以節(jié)點為中心的DMMT-DA-NC算法，它是由MMT-DA發(fā)展而來，與MMT-DA以邊為中心不同，有向邊的權重考慮了傳輸節(jié)點的傳輸半徑，在構造多播樹時以節(jié)點權重為依據，其求解質量要優(yōu)于MMT-DA和D-DPMT.文獻[11]運用二進制離散粒子群優(yōu)化算法優(yōu)化最小能耗多播樹的中繼節(jié)點集,而最大生命期廣播問題不同于最小能耗多播問題.文獻[12]運用粒子群優(yōu)化算法求解無線自組網中的最小能耗廣播問題,而最大生命期廣播問題不同于最小能耗廣播問題，最大生命期是使得最小節(jié)點生命期最大化，而最小能耗是使得所有節(jié)點的能耗之和最小化.文獻[13]使用粒子群優(yōu)化算法求解無線自組網中的QoS多播問題,未考慮能量有效的多播生命期問題.

本文針對在使用單波束定向天線時在線的最大生命期廣播路由問題,提出了一種構造最大生命期廣播樹的粒子群算法MLBPSO (maximum lifetime broadcast based on particle swarm optimization).該算法運用一種使用了阻尼邊界條件[14-15]、EPUS-PSO[16]的粒子群體管理和解信息共享策略的粒子群算法優(yōu)化最大生命期廣播樹的構造,并結合了DMMT-DA-NC算法構造粒子的初始位置和MLR-MD算法對粒子位置進行局部優(yōu)化,有效地延長了廣播樹的生命期.

1 問題描述

2 粒子群優(yōu)化

粒子群優(yōu)化算法PSO(particle swarm optimization)[17-19]是一種隨機的群體智能優(yōu)化算法,每個粒子在多維空間執(zhí)行搜索的過程中積累并參考自身的搜索經驗和群體的搜索經驗,調整自身的移動,以盡可能搜索到全局最優(yōu)解.

令向量Xi={xi,1,xi,2,…,xi,D}T表示粒子i的位置,Vi={vi,1,vi,2,…,vi,D}T表示粒子i的速度,其中D表示維數.令fit(Xi)表示粒子i的適應度值,Yi={yi,1,yi,2,…,yi,D}T表示粒子i的個體極值點,即粒子i自身所經歷的最好位置,則fit(Yi)表示粒子i的個體極值.所有粒子個體極值中的最優(yōu)者為全局極值,令b表示個體極值最優(yōu)的粒子,則Yb表示全局極值點,即所有粒子所經歷的最好位置,fit(Yb)表示全局極值.在PSO[17-18]中,粒子速度Vi和粒子位置Xi按下式更新:

vi,d(t+1)=wvi,d(t)+c1rand()(yi,d(t)-xi,d(t))+
c2rand()(yb,d(t)-xi,d(t))

(1)

xi,d(t+1)=xi,d(t)+vi,d(t+1)

(2)

式中,w為慣性權重[20],用于平衡粒子群優(yōu)化算法的全局探索能力和局部開發(fā)能力;c1,c2為加速因子;隨機函數rand()生成在區(qū)間[0,1]上均勻分布的隨機數.

為了提高粒子群優(yōu)化的搜索能力和效率,文獻[16]提出了一種基于粒子群高效利用策略的粒子群優(yōu)化算法EPUS-PSO (efficient population utilization strategy for PSO). EPUS-PSO根據搜索狀態(tài)動態(tài)調整粒子群體,當搜索狀態(tài)良好時,表明當前的粒子數可能太多反而不能處理好當前的搜索步驟,應排除冗余粒子以節(jié)省進化時間,加速尋找最優(yōu)解的進程,使得全局極值能夠不斷地進化;當搜索狀態(tài)惡劣時,應新增粒子進行搜索以擴大搜索空間,增強尋優(yōu)能力.令M表示當前粒子群規(guī)模.具體來講,當全局極值在連續(xù)的λmax代內發(fā)生了一次或多次進化并且當前粒子數M>1,就排除一個較差的粒子;當全局極值連續(xù)μmax代都未進化并且粒子數量M

vi,d(t+1)=wvi,d(t)+c1rand()(yi,d(t)-xi,d(t))+
c2rand()(yk,d(t)-xi,d(t))

(3)

式中,k以概率ρi取為從除i之外的其他粒子中隨機選擇的2個粒子中的個體極值較優(yōu)者,以概率1-ρi取為b,其中ρi=0.5((D-1)exp((i-1)/(M-1))-1)/(2D).

3 最大生命期廣播樹的粒子群算法構造

運用EPUS-PSO[16]來求解MLB問題.在求解過程中,對粒子位置取整[21],使用EPUS-PSO的粒子群體管理策略動態(tài)地調整粒子群體,使用EPUS-PSO的解共享機制更新粒子速度,使用阻尼邊界條件[14-15]處理粒子的越界,同時使用簡化的MLR-MD算法對粒子在執(zhí)行搜索過程中發(fā)現(xiàn)的新廣播樹進行局部優(yōu)化以提高收斂的質量和速度.

3.1 粒子定義

3.2 粒子位置更新

在更新粒子位置時,通過對原粒子位置Xi(t)進行調整來得到新粒子位置Xi(t+1).首先賦值Xi(t+1)=Xi(t),然后按隨機順序處理Xi(t+1)的各維.令exrfp(Xi,u,v)表示在粒子位置Xi所表示的廣播樹中當節(jié)點v成為節(jié)點u的孩子節(jié)點后節(jié)點u的傳輸功率.令exl(Xi,u,v)表示在粒子位置Xi所表示的廣播樹中當節(jié)點v成為節(jié)點u的孩子節(jié)點后節(jié)點u的生命期.在粒子進行搜索的過程中,可能會出現(xiàn)較差的粒子位置,這些較差的粒子位置不僅不會促進全局極值的進化還會增加計算時間.因此,在更新粒子位置的過程中,對新粒子位置進行一定的限制,如果新粒子位置xi,d(t+1)對應的節(jié)點Ωd[xi,d(t+1)]滿足exl(Xi(t+1),Ωd[xi,d(t+1)], vtx(d))≥η,則新粒子位置xi,d(t+1)才可能有效,否則xi,d(t+1)=xi,d(t).η為預先設定的某個閾值.對粒子位置按四舍五入取整.如果粒子位置Xi發(fā)生變化,就返回true表示更新成功,否則返回false表示更新失敗.更新粒子位置Xi的VaryX算法如下:

①Xi(t+1)←Xi(t);Z←{1, 2, …,N-1}, change←false.

② 如果Z=?,轉步驟⑥.

③ 從Z中隨機選擇一個維度d,Z←Z-syggg00;按式(2)計算xi,d(t+1),當xi,d(t+1)越界時使用阻尼墻[14-15]進行處理,xi,d(t+1) ←xi,d(t+1)+0.5;如果xi,d(t+1)=xi,d(t),轉步驟②.

⑤xi,d(t+1)←xi,d(t),轉步驟②.

⑥ 返回Xi(t+1)和change.

3.3 粒子位置局部優(yōu)化

文獻[4]的MLR-MD算法是對已有的一棵多播樹進行局部優(yōu)化.首先將多播樹中各節(jié)點按生命期升序排列,然后按此順序對各節(jié)點進行處理.在處理每個傳輸節(jié)點u時,按照其波束邊界節(jié)點對應的生命期增益遞減的順序依次處理其各個波束邊界節(jié)點,u的波束邊界節(jié)點v對應的生命期增益為節(jié)點u在移除孩子節(jié)點v后的生命期增加量.在某個節(jié)點的生命期得到提高后重新對多播樹中的各節(jié)點按生命期進行升序排列,并開始新的循環(huán).在使用MLR-MD算法局部優(yōu)化廣播樹時,由于廣播樹包含了所有網絡節(jié)點,因此不存在使用樹外節(jié)點調整樹結構的情況.在迭代更新粒子位置的過程中使用簡化的MLR-MD(simplified MLR-MD, SMLR-MD)對粒子位置進行局部優(yōu)化,SMLR-MD在每輪循環(huán)中只對最小生命期節(jié)點進行處理,以減少計算時間.

3.4 新增粒子構造

當搜索狀態(tài)較差時需要新增粒子以提高全局極值發(fā)生進化的可能性.文獻[16]指出,在新增粒子時通過交叉組合隨機選擇的2個粒子的個體極值點,可以構造出較好的粒子初始位置,從而有利于全局極值的進化.若粒子數M=1,即當前只有1個粒子,假設該粒子為i,則新粒子k的位置Xk取為粒子i的個體極值點Yi;若粒子數M>1,首先隨機選擇2個粒子,然后對它們的個體極值點進行交叉組合來構造新粒子k的位置Xk.

假設被隨機選擇用來交叉組合個體極值點的2個粒子為i和j,令E(Yi)表示粒子i的個體極值點Yi所表示的廣播樹的邊集,E(Yj)表示粒子j的個體極值點Yj所表示的廣播樹的邊集,在E(Yi)和E(Yj)的基礎上使用DMMT-DA-NC算法構造新粒子k的位置Xk.DMMT-DA-NC是從源節(jié)點開始自上而下地構造廣播樹,對于構造過程中的每次迭代,如果E(Yi)∪E(Yj)中存在連接中間樹(已形成的部分樹)內的節(jié)點到中間樹外的節(jié)點的邊,則使用這些邊進行構造,否則,使用E(Yi)∪E(Yj)以外的邊進行構造.

在初始化新粒子k的位置Xk之后,新粒子k的個體極值點Yk初始化為Xk.隨機初始化新粒子k的速度為Vk.

3.5 MLBPSO算法描述

設粒子群共包含Minit個初始粒子.貪心初始化粒子位置可以加快收斂速度[22],在算法的初始化階段,對每個粒子的位置使用DMMT-DA-NC算法[10]進行構造并使用MLR-MD算法[4]進行局部優(yōu)化,這樣可使得粒子從一個較好的位置開始進行搜索,MLBPSO算法從一個較好的解開始.令δ表示總迭代次數.MLBPSO算法是基于使用了阻尼邊界條件[14-15]、EPUS-PSO[16]的粒子群體管理和解信息共享策略的粒子群優(yōu)化,并使用MLR-MD局部優(yōu)化粒子位置以及使用DMMT-DA-NC構造粒子的初始位置.求解最大生命期廣播樹的MLBPSO算法如下:

② 更新慣性權重w,evol←false,i←1.

③ 按式(3)更新粒子i的速度Vi;使用VaryX算法更新粒子i的位置Xi,如果Xi更新失敗,轉步驟⑦.

④ 使用SMLR-MD算法對Xi進行局部優(yōu)化;計算粒子i的適應度值fit(Xi);如果fit(Xi)>fit(Yi),Yi←Xi,否則,轉步驟⑦.

⑤ 如果i=b,evol←true,轉步驟⑦.

⑥ 如果fit(Yi)>fit(Yb),evol←true,b←i.

⑦i←i+1;如果i≤M,轉步驟③.

⑧λ←λ+1;如果evol=true,μ←0,impr←true,轉步驟⑩.

⑨μ←μ+1;如果M≥Mmax,轉步驟.

⑩ 如果λ<λmax,轉步驟;如果impr=false或者M≤1,轉步驟.

4 仿真結果

令A1表示DMMT-DA-NC算法,A2表示DMMT-DA-NC+MLR-MD算法,A3表示MLBPSO算法.實驗結果如表1～表4所示,其中對A2的廣播生命期比A1的平均提高率、A3的廣播生命期比A1及A2的平均提高率進行了統(tǒng)計.由實驗結果可知,MLBPSO算法的計算結果優(yōu)于DMMT-DA-NC算法和DMMT-DA-NC+MLR-MD算法.MLBPSO是基于群體迭代尋優(yōu)因而運行時間長于DMMT-DA-NC和DMMT-DA-NC+MLR-MD.

MLBPSO較DMMT-DA-NC和DMMT-DA-NC+MLR-MD的平均提高率在θmin=π/3時比在θmin=π/12時低.這是由于θmin越大,節(jié)點波束寬度可優(yōu)化的空間越小,問題可優(yōu)化的空間越小,DMMT-DA-NC求得的解越接近于最優(yōu)解(當θmin=2π即為全向天線時，DMMT-DA-NC求得的解為最優(yōu)解),相應地MLBPSO較DMMT-DA-NC和DMMT-DA-NC+MLR-MD的平均提高率會降低.

網絡規(guī)模越大,MLBPSO的運行時間越長,這是因為網絡規(guī)模越大,維數D就越大,平均可以傳輸到達每個節(jié)點的其他節(jié)點越多.

表1 當時的實驗結果

表2 當時的實驗結果

表3 當時的實驗結果

表4 當時的實驗結果

5 結語

在無線自組網中,能量受限的特性制約著網絡的生命期.本文針對在使用單波束定向天線時的最大生命期廣播路由問題,提出了一個構造最大生命期廣播樹的粒子群算法MLBPSO.該算法在計算過程中動態(tài)地調整粒子群體、增強粒子間解信息交流、使用阻尼墻處理粒子越界,粒子在已有搜索經驗的指導下隨機地變換廣播樹結構,以盡可能搜索到最優(yōu)的最大生命期廣播樹.同時,MLBPSO算法結合MLR-MD算法對粒子位置進行局部優(yōu)化,結合DMMT-DA-NC算法構造粒子的初始位置,以提高求解效率.由于MLBPSO能夠搜索出更優(yōu)的廣播樹結構，因而可以更有效地提高廣播生命期.

)

[1]李政,李德英. 無線自組織網絡中能量有效的廣播與組播[J]. 軟件學報,2010,21(8): 2023-2036.

Li Zheng, Li Deying. Energy-efficient broadcast and multicast in wireless ad hoc networks [J].JournalofSoftware, 2010,21(8): 2023-2036. (in Chinese)

[2]Das A K, Marks R J, El-Sharkawi M, et al. MDLT: a polynomial time optimal algorithm for maximization of time-to-first-failure in energy constrained wireless broadcast networks [C]//ProceedingsoftheIEEEGlobalTelecommunicationsConference. San Francisco, California, USA, 2003: 362-366.

[3]Kang I, Poovendran R. Maximizing static network lifetime of wireless broadcast ad hoc networks [C]//ProceedingsoftheIEEEInternationalConferenceonCommunications. Anchorage, Alaska, USA, 2003: 2256-2261.

[4]Hou Y T, Shi Y, Sherali H D, et al. Multicast communications in ad hoc networks using directional antennas: a lifetime-centric approach [J].IEEETransactionsonVehicularTechnology, 2007,56(3): 1333-1344.

[5]Wieselthier J E, Nguyen G D, Ephremides A. Energy-aware wireless networking with directional antennas: the case of session-based broadcasting and multicasting [J].IEEETransactionsonMobileComputing, 2002,1(3): 176-191.

[6]Guo S, Yang O. Formulation of optimal tree construction for maximum lifetime multicasting in wireless ad-hoc networks with adaptive antennas [C]//ProceedingsoftheIEEEInternationalConferenceonCommunications. Seoul, Korea, 2005: 3370-3374.

[7]Guo S, Yang O. Multicast lifetime maximization for energy-constrained wireless ad-hoc networks with directional antennas [C]//ProceedingsoftheIEEEGlobalTelecommunicationsConference. Dallas, Texas, USA, 2004: 4120-4124.

[8]Guo S, Leung V C M, Yang O W W. Distributed multicast algorithms for lifetime maximization in wireless ad hoc networks with omni-directional and directional antennas [C]//ProceedingsoftheIEEEGlobalTelecommunicationsConference. San Francisco, California, USA, 2006: 4151642.

[9]Guo S, Yang O, Leung V. Approximation algorithms for longest-lived directional multicast communications in WANETs [C]//Proceedingsofthe8thACMInternationalSymposiumonMobileAdHocNetworkingandComputing. Montreal, Quebec, Canada, 2007: 190-198.

[10]Guo S, Leung V, Jiang X. Distributed approximation algorithms for longest-lived multicast in WANETs with directional antennas [J].IEEETransactionsonWirelessCommunications, 2010,9(7): 2227-2237.

[11]朱曉建,沈軍. 基于粒子群優(yōu)化的ad hoc網絡最小能耗多播路由算法[J]. 通信學報,2012,33(3):52-58.

Zhu Xiaojian, Shen Jun. Minimum energy consumption multicast routing in ad hoc networks based on particle swarm optimization [J].JournalonCommunications, 2012,33(3): 52-58. (in Chinese)

[12]Hsiao P C, Chiang T C, Fu L C. Particle swarm optimization for the minimum energy broadcast problem in wireless ad-hoc networks [C]//ProceedingsoftheIEEECongressonEvolutionaryComputation. Brisbane, Australia, 2012: 6252949.

[13]王楷. 基于粒子群優(yōu)化的Ad Hoc網絡多播路由研究[D]. 武漢:華中師范大學計算機科學系,2007.

[14]Huang T, Mohan A S. A hybrid boundary condition for robust particle swarm optimization [J].IEEEAntennasandWirelessPropagationLetters, 2005,4: 112-117.

[15]Xu S, Rahmat-Samii Y. Boundary conditions in particle swarm optimization revisited [J].IEEETransactionsonAntennasandPropagation, 2007,55(3): 760-765.

[16]Hsieh S T, Sun T Y, Liu C C, et al. Efficient population utilization strategy for particle swarm optimizer [J].IEEETransactionsonSystems,Man,andCybernetics—PartB:Cybernetics, 2009,39(2): 444-456.

[17]Kennedy J, Eberhart R. Particle swarm optimization [C]//ProceedingsoftheIEEEInternationalConferenceonNeuralNetworks. Perth, Australia, 1995: 1942-1948.

[18]Eberhart R, Kennedy J. A new optimizer using particle swarm theory [C]//ProceedingsoftheSixthInternationalSymposiumonMicroMachineandHumanScience. Nagoya, Japan, 1995: 39-43.

[19]Robinson J, Rahmat-Samii Y. Particle swarm optimization in electromagnetics [J].IEEETransactionsonAntennasandPropagation, 2004,52(2): 397-407.

[20]Shi Y, Eberhart R. A modified particle swarm optimizer [C]//ProceedingsoftheIEEEInternationalConferenceonEvolutionaryComputation. Anchorage, Alaska, USA, 1998: 69-73.

[21]Salman A, Ahmad I, Al-Madani S. Particle swarm optimization for task assignment problem [J].MicroprocessorsandMicrosystems, 2002,26(8): 363-371.

[22]Liu X, Su J, Han Y. An improved particle swarm optimization for traveling salesman problem [C]//Proceedingsofthe3rdInternationalConferenceonIntelligentComputing. Qingdao, China, 2007: 803-812.