董文，方向，范磊，楊力，雷志剛

(1.解放軍理工大學(xué) 野戰(zhàn)工程學(xué)院，江蘇 南京210007;2.中華人民共和國公安部 警衛(wèi)局防爆安檢中心，北京100031)

0 引言

智能雷場(chǎng)一般通過人工布設(shè)預(yù)先設(shè)置在具有一定正面、縱深和布雷密度的場(chǎng)地。如圖1所示，以無線傳感器網(wǎng)絡(luò)為基礎(chǔ)的雷場(chǎng)網(wǎng)絡(luò)在戰(zhàn)場(chǎng)環(huán)境下易受到敵方爆破掃雷、電磁掃雷等破壞性攻擊，而導(dǎo)致大面積的雷場(chǎng)節(jié)點(diǎn)通信功能損壞，網(wǎng)絡(luò)被分割成若干個(gè)互不相連的部分，智能雷場(chǎng)失去了整體協(xié)調(diào)攻擊地面裝甲目標(biāo)的能力。

圖1 被分割為數(shù)個(gè)互不相連的部分的受損雷場(chǎng)網(wǎng)絡(luò)示意圖Fig.1 Articulation of a damaged minefield network that was partitioned into multiple disjoint segments

在傳統(tǒng)無線傳感器網(wǎng)絡(luò)中，當(dāng)少量節(jié)點(diǎn)損壞時(shí)，通常采用調(diào)大節(jié)點(diǎn)功率的方式來愈合失效拓?fù)?。然而遭受大面積節(jié)點(diǎn)損壞的雷場(chǎng)網(wǎng)絡(luò)卻無法通過該方式來愈合拓?fù)?。目前各國都在研制具有自主移?dòng)能力的節(jié)點(diǎn)［1-3］，稱之為中續(xù)節(jié)點(diǎn)。該類節(jié)點(diǎn)在網(wǎng)絡(luò)完好的情況下處于休眠狀態(tài)，當(dāng)網(wǎng)絡(luò)遭到破壞時(shí)，能夠按照特定策略遷移至指定位置替代受損節(jié)點(diǎn)，由該類節(jié)點(diǎn)進(jìn)行的拓?fù)湫迯?fù)不僅能夠使全局拓?fù)浠謴?fù)連通性，還能讓恢復(fù)的網(wǎng)絡(luò)通信路徑長(zhǎng)度變短，從而更加節(jié)省網(wǎng)絡(luò)能耗。目前關(guān)于網(wǎng)絡(luò)拓?fù)湫迯?fù)的研究較為薄弱，文獻(xiàn)［4］采用STP-MSP 算法建立一顆包含網(wǎng)絡(luò)節(jié)點(diǎn)和斯坦納(Steiner)點(diǎn)的Steiner 樹，選擇并調(diào)度一些節(jié)點(diǎn)移動(dòng)到這些Steiner 點(diǎn)上，從而修復(fù)網(wǎng)絡(luò)拓?fù)?。文獻(xiàn)［5］采用近似算法，首先找到各相鄰片區(qū)的最優(yōu)Steiner 點(diǎn)位置，再對(duì)各點(diǎn)使用質(zhì)心量算方法獲取最優(yōu)解，解決水下無線傳感器網(wǎng)絡(luò)的拓?fù)湫迯?fù)問題。文獻(xiàn)［6］針對(duì)網(wǎng)絡(luò)中某個(gè)節(jié)點(diǎn)失效而造成網(wǎng)絡(luò)連接中斷的情況，采用啟發(fā)式算法CRR 指導(dǎo)對(duì)失效節(jié)點(diǎn)的鄰居節(jié)點(diǎn)向指定地點(diǎn)移動(dòng)，從而恢復(fù)網(wǎng)絡(luò)連通性，并且恢復(fù)后的網(wǎng)絡(luò)擁有更好的負(fù)載均衡性。

離散量子粒子群優(yōu)化算法是由Yang 等于2004年提出的［7］，是量子粒子群優(yōu)化算法在離散問題上的改進(jìn)算法。算法將量子粒子群算法中的粒子離散化，成為離散的粒子矢量。蛙跳優(yōu)化算法在離散問題上的應(yīng)用是由Martinez-Garcia 等于2008年提出的［8］，蛙跳優(yōu)化算法的原理是，將整個(gè)青蛙群體按照一定規(guī)則劃分成若干個(gè)子群，子群獨(dú)立進(jìn)化，一定階段后，再融合在一起，重新劃分后再獨(dú)立進(jìn)化，直到滿足結(jié)束條件。二者都采用組織社會(huì)行為代替進(jìn)化算法的自然選擇機(jī)制，但在算法表現(xiàn)方面有著不同的特點(diǎn)。離散量子粒子群優(yōu)化算法(QDPSO)簡(jiǎn)潔效率高，局部搜索速度快，但會(huì)由于粒子在運(yùn)動(dòng)過程中產(chǎn)生惰性而發(fā)生早熟收斂，導(dǎo)致陷入局部最優(yōu)解。蛙跳優(yōu)化(JFO)的局部搜索速度較慢，但其采用多種群的進(jìn)化方法，擁有優(yōu)良的全局搜索性能。蛙跳和離散量子粒子群混合優(yōu)化(JF-QDPSO)算法采用二者相結(jié)合的方法，利用QDPSO 算法進(jìn)行子群內(nèi)部局部搜索，利用JFO 的多子群進(jìn)化方法進(jìn)行子群間的混選，跳出局部最優(yōu)，以達(dá)到收斂速度快及全局搜索性能好的目的。

本文針對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)受到大面積損壞的情況，將網(wǎng)絡(luò)拓?fù)溆蠁栴}映射到斯坦納最小樹(SMT)問題，通過引入JF-QDPSO 算法求解中續(xù)節(jié)點(diǎn)位置，修復(fù)網(wǎng)絡(luò)拓?fù)洹Ｔ摬呗圆捎萌后w智能算法，具有執(zhí)行簡(jiǎn)單、計(jì)算時(shí)間短以及恢復(fù)后的網(wǎng)絡(luò)平均通信鏈路小等優(yōu)點(diǎn)，具有較強(qiáng)的實(shí)用性。

1 問題描述及轉(zhuǎn)化

設(shè)智能雷場(chǎng)網(wǎng)絡(luò)中共有N 個(gè)具有移動(dòng)和定位能力的中續(xù)節(jié)點(diǎn)，當(dāng)網(wǎng)絡(luò)遭到攻擊被分割成數(shù)個(gè)互不連通的部分后，需要啟動(dòng)中續(xù)節(jié)點(diǎn)來代替受損節(jié)點(diǎn)修復(fù)網(wǎng)絡(luò)拓?fù)?。這里忽略智能雷場(chǎng)節(jié)點(diǎn)隨即拋灑布設(shè)的情況，僅考慮人工定點(diǎn)布設(shè)節(jié)點(diǎn)。就該問題而言，扮演替代角色的中續(xù)節(jié)點(diǎn)的位置選取至關(guān)重要，節(jié)點(diǎn)的遷移行為不僅需要恢復(fù)受損拓?fù)?，更能使修?fù)的網(wǎng)絡(luò)節(jié)省能耗，縮短網(wǎng)絡(luò)通信鏈路長(zhǎng)度，因此智能雷場(chǎng)網(wǎng)絡(luò)修復(fù)問題可歸結(jié)為最優(yōu)化網(wǎng)絡(luò)拓?fù)涞闹欣m(xù)節(jié)點(diǎn)位置選取問題。對(duì)于此類連通數(shù)個(gè)被分割的部分形成通路的最優(yōu)問題，通常都被歸為SMT［9-10］問題。

定義1 給定圖G =(V，E)，V 為圖G 的節(jié)點(diǎn)集，E 為圖G 的邊集，費(fèi)用函數(shù)C:E→R+，R+為正實(shí)數(shù)，目標(biāo)節(jié)點(diǎn)集D?V.則SMT 為從圖G 中找出連通D 中所有節(jié)點(diǎn)的最小生成樹，即使樹的費(fèi)用最小，則該最小生成樹稱為SMT.

然而，根據(jù)智能雷場(chǎng)網(wǎng)絡(luò)通信的特殊性，需要規(guī)定每個(gè)連通節(jié)點(diǎn)間的距離d(i，j)最多不能超過通信距離R，且費(fèi)用函數(shù)C 的最小值即為所形成的連通網(wǎng)絡(luò)通信鏈路長(zhǎng)度最小值。

定義2 抽象受損智能雷場(chǎng)網(wǎng)絡(luò)為圖G =(V，E，C).其中:V 表示節(jié)點(diǎn)集，E 表示節(jié)點(diǎn)間的無線鏈路集合，C 為費(fèi)用函數(shù)，表示所有無線鏈路的總長(zhǎng)度。滿足:eij表示節(jié)點(diǎn)i，j 之間的鏈路，目標(biāo)節(jié)點(diǎn)集D?V.因此，智能雷場(chǎng)網(wǎng)絡(luò)大面積受損修復(fù)問題被轉(zhuǎn)化為:確定中續(xù)節(jié)點(diǎn)的位置，使得在圖G 中能夠形成一個(gè)連通所有目標(biāo)節(jié)點(diǎn)的子樹T，且所有無線鏈路總長(zhǎng)度最小，即

2 基于區(qū)域網(wǎng)格模型的JF-QDPSO 算法

2.1 標(biāo)準(zhǔn)粒子群算法

粒子群算法是由Kennedy 等［11］提出的一種智能優(yōu)化算法，優(yōu)點(diǎn)為算法簡(jiǎn)潔，易于實(shí)現(xiàn)，且沒有梯度信息。該算法通過初始一群隨機(jī)粒子(每個(gè)粒子代表著一個(gè)潛在解)，并利用迭代方式，使每個(gè)粒子向自身找到的最好位置和群體中最好粒子靠近，從而搜索最優(yōu)解。標(biāo)準(zhǔn)粒子群算法迭代過程如下

式中:vij為第i 個(gè)粒子j 維的飛行速度;xij為粒子位置;k 為迭代次數(shù);r1和r2為［0，1］之間的隨機(jī)數(shù);c1和c2為加速因子;pbest是粒子i 迄今為止搜索到的最優(yōu)位置;gbest為整個(gè)粒子群迄今位置搜索到的最優(yōu)位置。

2.2 雷場(chǎng)網(wǎng)絡(luò)模型

本文關(guān)注的核心問題是中續(xù)節(jié)點(diǎn)的放置位置，假若雷場(chǎng)網(wǎng)絡(luò)中節(jié)點(diǎn)隨意放置，會(huì)使得算法的搜索空間無限大，不利于實(shí)際工程問題的解決。為了縮小算法搜索空間規(guī)模，本文將雷場(chǎng)網(wǎng)絡(luò)的節(jié)點(diǎn)放置網(wǎng)格化。圖2顯示了網(wǎng)格型的智能雷場(chǎng)網(wǎng)絡(luò)結(jié)構(gòu)，中續(xù)節(jié)點(diǎn)的可能放置位置必須在網(wǎng)格交點(diǎn)處，且單位網(wǎng)格長(zhǎng)度等于節(jié)點(diǎn)間通信距離R.

2.3 蛙跳和離散量子粒子群混合優(yōu)化算法

通過將雷場(chǎng)區(qū)域網(wǎng)格化，放置中續(xù)節(jié)點(diǎn)的位置由連續(xù)空間變?yōu)榭晒┻x擇的離散點(diǎn)，因此，本文采用QDPSO 和JFO 相結(jié)合的算法解決雷場(chǎng)網(wǎng)絡(luò)修復(fù)問題。

JF-QDPSO 算法的粒子群表述為

圖2 基于網(wǎng)格模型的雷場(chǎng)網(wǎng)絡(luò)結(jié)構(gòu)Fig.2 Grid-based minefield network architecture

式中:S 為整個(gè)青蛙種群;K 為子群數(shù)量;m 為單個(gè)子群所包含的粒子規(guī)模;Xki表示單個(gè)粒子位置。在智能雷場(chǎng)網(wǎng)絡(luò)大面積受損修復(fù)問題中，單個(gè)粒子位置由一串離散的二進(jìn)制碼表示Xki=［xki1，xki2，…，］，n 為中間節(jié)點(diǎn)的數(shù)量，此處xkij只能取0 或者1.當(dāng)xkij取1 時(shí)，表示中間節(jié)點(diǎn)j 被選擇為中續(xù)節(jié)點(diǎn)的放置位置，當(dāng)xkij取0 時(shí)，則在該節(jié)點(diǎn)處不放置中續(xù)節(jié)點(diǎn)。

JF-QDPSO 不采用標(biāo)準(zhǔn)粒子群算法的粒子飛行速度來更新粒子，取而代之的是粒子從一個(gè)可行解跳躍到另外一個(gè)可行解。每個(gè)粒子Xi跳躍到下一時(shí)刻位置Xi+1由以下3 種變量決定:該粒子迄今為止搜索到的最好位置b;子群內(nèi)部所有粒子迄今為止搜索到的最好位置gi;整個(gè)種群所有粒子迄今為止搜索到的最好位置g*.

本文提出的算法1～3 顯示了JF-QSPSO 求解雷場(chǎng)網(wǎng)絡(luò)大面積損壞修復(fù)問題的具體細(xì)節(jié)。算法1 是算法的主體結(jié)構(gòu)，算法2 保證經(jīng)過每次跳躍過程后Xi+1也是問題的可行解，算法3 起到本地搜索的作用，在滿足問題可行解的前提下盡可能多的除去被選中的中續(xù)節(jié)點(diǎn)。

算法首先產(chǎn)生一個(gè)規(guī)模為m 的子群S，初始化粒子X1為［1，1，…，1］，因此X1必然是該問題的一個(gè)可行解。在的每一次迭代過程中，原先粒子位置Xi經(jīng)過一次隨機(jī)跳躍，變成另外一個(gè)可行解Xi+1.隨機(jī)跳躍過程是由一個(gè)在0 和1 之間的隨機(jī)數(shù)ξ 控制的，算法等概率的在Xi、bi、gi、g*之中選擇一個(gè)數(shù)為selected.隨后執(zhí)行Combine(Xi，selected)(見算法2)將粒子Xi與被選擇粒子selected 結(jié)合起來。這里運(yùn)用到了comp(Xi)的概念［12］，它表示至少包含一個(gè)目標(biāo)節(jié)點(diǎn)的斯坦納連通圖，當(dāng)且僅當(dāng)comp(Xi)=1 時(shí)，Xi才是問題的一個(gè)可行解。算法2 首先在［0，num(|Xi|)］之間選擇一個(gè)隨機(jī)數(shù)ψ，隨后從集合|Xi|隨機(jī)刪除一個(gè)中續(xù)節(jié)點(diǎn)，或者從集合selected 中隨機(jī)增加一個(gè)節(jié)點(diǎn)為中續(xù)節(jié)點(diǎn)，此操作循環(huán)ψ 次后終止。隨后更新Xi及comp(Xi)，如果Xi是非可行解時(shí)(comp(Xi)＞1)，隨機(jī)添加一個(gè)節(jié)點(diǎn)為中續(xù)節(jié)點(diǎn)，直到得到可行解(comp(Xi)=1).算法3 起到了一個(gè)本地搜索的作用，在不影響解可行性的前提下，盡量縮小中續(xù)節(jié)點(diǎn)數(shù)量。本地搜索之后，變量(bi，gi，g*)都會(huì)被更新，用到下一次循環(huán)當(dāng)中。這里，循環(huán)的次數(shù)可以理解為子群的數(shù)量，當(dāng)循環(huán)次數(shù)達(dá)到指定的子群數(shù)量或者得到了滿意的g*，則循環(huán)中止，輸出斯坦納樹T.

1)算法1:蛙跳和離散量子粒子群混合優(yōu)化算法求解雷場(chǎng)網(wǎng)絡(luò)大面積損壞快速修復(fù)問題。

輸入:網(wǎng)格劃分后的連通權(quán)重圖G =(V，E，C)，其中包含了n 個(gè)頂點(diǎn)，l 條邊，以及Q?V 個(gè)目標(biāo)節(jié)點(diǎn);

輸出:連通所有目標(biāo)節(jié)點(diǎn)且權(quán)重值最小的斯坦納樹T;

初始化:令|Xi|為中續(xù)節(jié)點(diǎn)的集合，即|Xi| ={xij=1/xij，j =［1，n］};令C(Xi)為粒子Xi的適應(yīng)度函數(shù)，C(Xi)=隨機(jī)產(chǎn)生子群Sk粒子規(guī)模m，Sk=［Xk1，Xk2，…，Xkm］.

-運(yùn)行算法2Combine(Xi，selected)，將粒子Xi與被選擇粒子selected 結(jié)合起來;

-運(yùn)行算法3Local-Search(i，Xi)，進(jìn)行本地局部搜索;

until 達(dá)到循環(huán)中止條件;

-輸出斯坦納樹T=G(|g*|，E(|g*|))，其中E(|g*|)為連接g*中的中續(xù)節(jié)點(diǎn)且邊長(zhǎng)小于等于通信距離R 的邊。

2)算法2:Combine(Xi，selected)

-令comp(Xi)為至少包含一個(gè)目標(biāo)節(jié)點(diǎn)的斯坦納連通圖;令num(|Xi|)為集合|Xi|中中續(xù)節(jié)點(diǎn)的數(shù)量;在［0，num(|Xi|)］之間選擇一個(gè)隨機(jī)數(shù):ψ←Random(0，num(|Xi|));

3 仿真實(shí)驗(yàn)

平均鏈路長(zhǎng)度和平均計(jì)算時(shí)間是評(píng)價(jià)雷場(chǎng)網(wǎng)絡(luò)修復(fù)算法的重要參數(shù)。鏈路長(zhǎng)度短說明在能夠保證重建網(wǎng)絡(luò)連通的前提下，運(yùn)用的節(jié)點(diǎn)數(shù)量少，且修復(fù)后的網(wǎng)絡(luò)通信能耗小，生存周期長(zhǎng);計(jì)算時(shí)間少則表明算法執(zhí)行時(shí)間短，算法效率高。

為了驗(yàn)證JF-QDPSO 的性能，針對(duì)中間節(jié)點(diǎn)數(shù){100，400}和目標(biāo)節(jié)點(diǎn)數(shù){5，8，10}6 個(gè)樣本，對(duì)SMT-MSP［10］(Steiner minimum tree with minimum number of Steiner points)、QDPSO 和JF-QDPSO 進(jìn)行比較，其中JF-QDPSO 的種群規(guī)模為100，分成20 個(gè)子群，最大迭代數(shù)1 000.PC 機(jī)平臺(tái)為Pentium 4 CPU，主頻1.43 GHz，內(nèi)存1 GB，操作系統(tǒng)使用Windows XP，利用Visual C + +6.0 語言編程實(shí)現(xiàn)。表1給出了SMT-MSP、QDPSO 和JF-QDPSO 對(duì)六個(gè)樣本仿真計(jì)算100 次得出的平均網(wǎng)路鏈路長(zhǎng)度和平均計(jì)算時(shí)間。從表1中可以看出:JF-QDPSO 和QDPSO 不僅從計(jì)算結(jié)果，而且在計(jì)算時(shí)間上也遠(yuǎn)遠(yuǎn)勝過SMT-MSP，這表明離散量子粒子群算法比啟發(fā)式算法SMT-MSP 簡(jiǎn)潔高效，且能夠更好的應(yīng)用于雷場(chǎng)網(wǎng)路拓?fù)湫迯?fù)中。此外，從JF-QDPSO 與QDPSO的比較來看，JF-QDPSO 在求解結(jié)果上比QDPSO 更優(yōu)，然后求解速度上卻因多子群間的協(xié)作進(jìn)化而略低于QDPSO.

表1 3 種算法對(duì)不同樣本的平均鏈路長(zhǎng)度和計(jì)算時(shí)間Tab.1 Average link length and computational times with different samples for three algorithms

圖3給出了在中間節(jié)點(diǎn)數(shù)為100，目標(biāo)節(jié)點(diǎn)數(shù)為5 的情況下3 種算法的收斂曲線。圖中，SMTMSP 在95 代左右才趨近于收斂，且結(jié)果最差;QDPSO 在40 代左右就趨近于收斂，但效果一般;JFQDPSO 在60 代左右趨近于收斂，且效果最好，這說明蛙跳算法與離散量子粒子群算法的結(jié)合，有效克服了算法陷入局部最優(yōu)解，體現(xiàn)了其收斂速度快及全局搜索性能好的特點(diǎn)。

圖3 3 種算法的收斂曲線Fig.3 Convergence performance for three algorithm

4 結(jié)論

本文研究了以無線傳感器網(wǎng)絡(luò)為基礎(chǔ)的智能雷場(chǎng)網(wǎng)絡(luò)大面積損壞拓?fù)湫迯?fù)問題。將該問題抽象為求解斯坦納最小樹問題，提出了蛙跳和離散量子粒子群混合優(yōu)化算法。理論和數(shù)值仿真證明，該算法充分利用了粒子群算法收斂速度快、局部搜索能力強(qiáng)以及混合蛙跳算法全局尋優(yōu)能力強(qiáng)、跳出局部最優(yōu)能力好的特點(diǎn)，較SMT-MSP 算法在平均鏈路長(zhǎng)度上較低了43.2%，在平均計(jì)算時(shí)間上降低了51.4%.可見，本文所提算法在有效恢復(fù)網(wǎng)絡(luò)拓?fù)涞耐瑫r(shí)，降低了恢復(fù)后網(wǎng)絡(luò)的通信荷載，延長(zhǎng)了網(wǎng)絡(luò)生存周期。

References)

［1］ Mattias S，Mathias B，Alessandro Si，et al.An autonomous spherical robot for security tasks［C］∥2006 IEEE International Conference on Computational Intelligence for Homeland Security and Personal Safety.AV Alexandria，AV:IEEE，2006:1233 -1236.

［2］ Sugiyama Y，Hirai S.Crawling and jumping by a deformable robot［J］.International Journal of Robotics Research，2006，25(5):603 -620.

［3］ 付夢(mèng)印，楊毅，朱昊，等.移動(dòng)機(jī)器人組合感知系統(tǒng)及其配準(zhǔn)方法改進(jìn)［J］.兵工學(xué)報(bào)，2011，32(6):712 -718.FU Meng-yin，YANG Yi，ZHU Hao，et al.Integrated perception system for mobile robot and its improved registration［J］.Acta Armamentarii，2011，32(6):712 -718.(in Chinese)

［4］ Cheng X Z，Du D Z，Wang L S，et al.Relay sensor placement in wireless sensor networks［J］.Wireless Netwroks，2008，14(3):347 -355.

［5］ 劉林峰，劉業(yè).基于滿Steiner 樹問題的水下無線傳感器網(wǎng)絡(luò)拓?fù)溆纤惴ㄑ芯浚跩］.通信學(xué)報(bào)，2010，31(9):30 -45.LIU Lin-feng，LIU Ye.Study of topology recovery algorithm based on full Steiner minimum tree problem in underwater wireless sensor networks［J］.Journal of Communications，2010，31(9):30 -45.(in Chinese)

［6］ Mohamed Y，Rahul W.Connectivity restoration in wireless sensor networks using Steiner tree approximations［C］∥IEEE Global Telecommunications Conference.Miami:IEEE，2010:1 -5.

［7］ Yang S，Wang M，Jiao L.A quantum particle swarm optimization［C］∥Proceeding of the 2004 IEEE Congress on Evolutionary Computation.Alexandria:IEEE，2004:320 -324.

［8］ Martunez-Garcia F J，Moreno-Perez J A.Jumping frogs optimization:a new swarm method for discrete optimization［C］∥Teth.Rep.DEIOC 3/2008，Dep.Of Statistics，O.R.and Computing.Spain:University of La Laguna，2008:29 -46.

［9］ Lin G，Xue G.Steiner tree problem with minimum number of Steiner points and bounded edge length［J］.Information on Processing Letters，1999，69(2):53 -57.

［10］ Lloyd E L，Xue G.Relay node placement in wireless sensor networks［J］.IEEE Transcations on Computers，2007，56(1):134 -138.

［11］ Eberhart R，Kennedy J.A new optimizer using particle swarm theory［C］∥Proceeding of the Sixth International Symposium on Micro Machine and Human Science.Nagoya:Indianapolis Press，1995:39 -43.

［12］ Cerulli R，F(xiàn)ink A.Extensions of the minimum labelling spanning tree problem［J］.Journal of Telecommunications and Information Technology，2006，32(4):39 -45.