移動傳感器網(wǎng)絡(luò)編隊(duì)覆蓋搜索控制算法

薛志斌，曾建潮，胡豁生，薛頌東

（1.青海大學(xué)智能系統(tǒng)與控制實(shí)驗(yàn)室，西寧 810016；2.太原科技大學(xué)復(fù)雜系統(tǒng)與計(jì)算智能實(shí)驗(yàn)室，太原 030024；3.埃塞克斯大學(xué)以人為本機(jī)器人研究室，埃塞克斯郡科爾切斯特C04 3SQ）

移動傳感器網(wǎng)絡(luò)編隊(duì)覆蓋搜索控制算法

薛志斌1，曾建潮2，胡豁生3，薛頌東2

（1.青海大學(xué)智能系統(tǒng)與控制實(shí)驗(yàn)室，西寧 810016；2.太原科技大學(xué)復(fù)雜系統(tǒng)與計(jì)算智能實(shí)驗(yàn)室，太原 030024；3.埃塞克斯大學(xué)以人為本機(jī)器人研究室，埃塞克斯郡科爾切斯特C04 3SQ）

受生物群體聚集機(jī)理的啟發(fā)，運(yùn)用勢場理論與牛頓——拉夫遜迭代技術(shù)，借助具有碰撞規(guī)避功能的有限感知群體動力學(xué)模型，實(shí)現(xiàn)了動態(tài)未知環(huán)境下無線傳感器網(wǎng)絡(luò)分布式節(jié)點(diǎn)的編隊(duì)部署及其在執(zhí)行區(qū)域內(nèi)的編隊(duì)覆蓋搜索，豐富了已有的覆蓋搜索控制算法。以盡可能少的工作節(jié)點(diǎn)達(dá)到了網(wǎng)絡(luò)的連通性覆蓋要求，原理簡單，節(jié)能性好，實(shí)用，仿真結(jié)果驗(yàn)證了該算法的有效性。

人工勢場；無線傳感器網(wǎng)絡(luò)；有限感知群體；編隊(duì)；節(jié)點(diǎn)部署；覆蓋搜索

0 引言

近年來，隨著微機(jī)電系統(tǒng)（Micro-Elect ro-Mechanism System，MEMS）、無線通信、信息網(wǎng)絡(luò)與集成電路等技術(shù)的迅速發(fā)展，新興的無線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks，WSNs）應(yīng)運(yùn)而生，并逐漸成為研究熱點(diǎn)，已廣泛應(yīng)用于軍事、環(huán)境監(jiān)測和保護(hù)、交通運(yùn)輸管理、醫(yī)療護(hù)理、工業(yè)生產(chǎn)、物流控制、空間探索、家庭和商業(yè)等領(lǐng)域中，來完成針對各種用途時(shí)的多種物理量的測量［1-4］。

無線傳感器網(wǎng)絡(luò)是由部署在監(jiān)測區(qū)域內(nèi)的、大量的、可協(xié)作地感知對象信息的微型傳感器節(jié)點(diǎn)組成的集數(shù)據(jù)采集、數(shù)據(jù)處理、數(shù)據(jù)傳輸及信息傳遞功能于一體的復(fù)雜系統(tǒng)，已成為近期國內(nèi)外網(wǎng)絡(luò)研究的熱點(diǎn)［5-8］。

伴隨著WSN的迅速發(fā)展，衍生出許多有關(guān)WSN的研究領(lǐng)域，WSN的覆蓋優(yōu)化理論和技術(shù)就是其中的重要組成部分之一，此類研究的內(nèi)容包括WSN節(jié)點(diǎn)定位［2，9］、WSN網(wǎng)絡(luò)覆蓋控制［10-12］等基本且亟待解決的問題。其中，WSN中網(wǎng)絡(luò)節(jié)點(diǎn)的空間位置分布決定著網(wǎng)絡(luò)的感知質(zhì)量、性能和使用壽命。WSN中節(jié)點(diǎn)的感知范圍是圓形區(qū)域，各節(jié)點(diǎn)的感知能力有限，只有通過多節(jié)點(diǎn)的協(xié)作才能完成對感知對象的信息采集；覆蓋研究旨在優(yōu)化網(wǎng)絡(luò)空間資源，以更好地完成環(huán)境感知、信息獲取，是實(shí)現(xiàn)整個(gè)監(jiān)測任務(wù)的基礎(chǔ)。就WSN的覆蓋控制問題的研究進(jìn)展而言，絕大多數(shù)國內(nèi)外既得研究成果是針對滿足全局感知模型的傳統(tǒng)無線傳感器網(wǎng)絡(luò)展開的，而針對隨機(jī)大規(guī)模規(guī)則部署的傳感器節(jié)點(diǎn)的連通性網(wǎng)絡(luò)覆蓋控制的分布式編隊(duì)算法的既得研究成果的已見報(bào)導(dǎo)甚少［13-19］。

為了解決這一覆蓋連通性問題，通過引入群智能理論，以群集行為中的涌現(xiàn)機(jī)理為基礎(chǔ)，借助筆者在前期工作中提出的有限感知群體動力學(xué)模型［20］，用于設(shè)計(jì)無線傳感器網(wǎng)絡(luò)的優(yōu)化覆蓋策略，實(shí)現(xiàn)了WSN的編隊(duì)最優(yōu)覆蓋搜索算法。最后，一系列仿真實(shí)驗(yàn)驗(yàn)證了該算法的有效性，在保證監(jiān)測區(qū)域內(nèi)整個(gè)網(wǎng)絡(luò)的連通性覆蓋性能的同時(shí)，兼顧了網(wǎng)絡(luò)覆蓋質(zhì)量和網(wǎng)絡(luò)資源的優(yōu)化。算法簡單、運(yùn)行速度快，能有效收斂于最優(yōu)解，降低了網(wǎng)絡(luò)能耗，為設(shè)計(jì)更加實(shí)用的覆蓋控制算法提供了依據(jù)。

1 相關(guān)工作

1.1 WSN覆蓋優(yōu)化

WSN覆蓋優(yōu)化問題的研究現(xiàn)狀是結(jié)合不同應(yīng)用環(huán)境的需求，設(shè)計(jì)、應(yīng)用切實(shí)可行的、合理的覆蓋控制策略，使各種資源得到優(yōu)化分配，是當(dāng)前無線傳感器網(wǎng)絡(luò)領(lǐng)域的一個(gè)研究熱點(diǎn)［21］。此類覆蓋優(yōu)化問題依據(jù)節(jié)點(diǎn)的配置方式可以分為確定性覆蓋和隨機(jī)性覆蓋兩類子問題；同時(shí)，依據(jù)WSN的應(yīng)用屬性可將此類覆蓋優(yōu)化問題劃分為節(jié)能覆蓋、柵欄覆蓋、連通性覆蓋和目標(biāo)定位覆蓋等子問題［17］。

鑒于此，本文的設(shè)計(jì)目標(biāo)是實(shí)現(xiàn)WSN節(jié)點(diǎn)的隨機(jī)連通性編隊(duì)覆蓋搜索控制。

1.2 虛擬勢場法

虛擬勢場方法是解決傳感器網(wǎng)絡(luò)覆蓋控制問題的典型方法之一。利用虛擬勢場方法時(shí)，假定節(jié)點(diǎn)間存在兩種虛擬力：1）斥力，使節(jié)點(diǎn)足夠稀疏，避免過分密集的節(jié)點(diǎn)造成感知重疊區(qū)域；2）引力，使節(jié)點(diǎn)保持一定的密度，避免過于分離而形成感知盲區(qū)。最終利用節(jié)點(diǎn)的位置移動優(yōu)化傳感器網(wǎng)絡(luò)的覆蓋性能［22］。

人工虛擬勢場最早是由Khatib［23］提出，其基本思想是引入一個(gè)稱為勢場的數(shù)值函數(shù)來描述機(jī)器人空間的幾何結(jié)構(gòu)，通過搜索勢場的下降方向來完成運(yùn)動規(guī)劃［24］；并通過把機(jī)器人的運(yùn)動環(huán)境假想成某種抽象勢場，應(yīng)用于移動機(jī)器人的路徑規(guī)劃中。勢場源包含兩類：障礙物對應(yīng)的斥力極和目標(biāo)對應(yīng)的引力極。進(jìn)而設(shè)計(jì)實(shí)現(xiàn)多（或群）機(jī)器人的覆蓋路徑規(guī)劃算法［25］。

路徑規(guī)劃是機(jī)器人研究的一個(gè)重要內(nèi)容。常規(guī)的路徑規(guī)劃是指點(diǎn)到點(diǎn)的最優(yōu)路徑規(guī)劃，其目標(biāo)是尋找一條從起始點(diǎn)到目標(biāo)點(diǎn)的無碰撞最優(yōu)（最短或代價(jià)最?。┞窂?。而覆蓋任務(wù)中的路徑規(guī)劃要求路徑能保證機(jī)器人遍歷整個(gè)目標(biāo)區(qū)域，其目的有兩個(gè)方面：保證遍歷每一點(diǎn)達(dá)到完全覆蓋和盡量避免重復(fù)路徑提高覆蓋效率。多機(jī)器人覆蓋是指多個(gè)機(jī)器人協(xié)作、快速高效地遍歷一個(gè)含障區(qū)域內(nèi)的全部自由空間［26］。正是由于移動機(jī)器人運(yùn)動路徑規(guī)劃應(yīng)用研究的需要，物理學(xué)中的場的概念才被引進(jìn)來描述機(jī)器人在空間中的幾何結(jié)構(gòu)，引導(dǎo)機(jī)器人向目標(biāo)行進(jìn)。這些場包括常見的勢場，還有距離場以及來自于水力分析的基于流函數(shù)的規(guī)劃算法。國內(nèi)對后兩種算法研究甚少［24］。

在傳感器網(wǎng)絡(luò)路徑覆蓋計(jì)算中，路徑軌跡點(diǎn)對傳感器節(jié)點(diǎn)具有引力，并且在感知半徑r范圍內(nèi)，距離越遠(yuǎn)引力函數(shù)值越大，反之越小。當(dāng)距離為零時(shí)，路徑軌跡點(diǎn)對傳感器節(jié)點(diǎn)的引力勢函數(shù)為零，斥力勢函數(shù)為無窮大以免發(fā)生節(jié)點(diǎn)間的碰撞。此時(shí)路徑軌跡點(diǎn)與傳感器節(jié)點(diǎn)處于同一位置［25］。

1.3 感知模型

受生物群體聚集行為啟發(fā)，針對生物群體中個(gè)體成員的感知范圍是有限的這一事實(shí)，文獻(xiàn)［20］中提出了一個(gè)有限感知群體模型。群內(nèi)任意個(gè)體i的運(yùn)動方程可以如式（1）形式進(jìn)行描述：

相應(yīng)的引力/斥力相互作用函數(shù)關(guān)系式可描述為

環(huán)境的動態(tài)變化、局部感知和非線性特性是自然界群集過程中普遍存在的現(xiàn)象，筆者提出的有限感知群體動力學(xué)模型確能較好地體現(xiàn)出這些接近于實(shí)情的特點(diǎn)［20］。其數(shù)值仿真結(jié)果表明，群內(nèi)個(gè)體在協(xié)調(diào)運(yùn)動過程中個(gè)體間可實(shí)現(xiàn)碰撞規(guī)避而完成相互聚集，收斂性優(yōu)良。群體中個(gè)體成員的相互協(xié)調(diào)運(yùn)動促成了群體運(yùn)動的涌現(xiàn)行為，是個(gè)體間的交互作用和個(gè)體與所處環(huán)境間相互作用的結(jié)果［27］。上述結(jié)論有助于將該模型應(yīng)用于大規(guī)模智能群體系統(tǒng)和WSN節(jié)點(diǎn)的分布式協(xié)調(diào)控制中進(jìn)行推廣并驗(yàn)證其實(shí)用性。

2 覆蓋數(shù)學(xué)模型

2.1 節(jié)點(diǎn)部署

所謂節(jié)點(diǎn)部署，即通過一定的算法布置網(wǎng)絡(luò)節(jié)點(diǎn)，優(yōu)化現(xiàn)有的網(wǎng)絡(luò)資源。通常，選用的網(wǎng)絡(luò)節(jié)點(diǎn)部署方法需要在完成監(jiān)測任務(wù)的前提下，盡量節(jié)省能耗以延長網(wǎng)絡(luò)壽命［7］。

筆者的目標(biāo)是就節(jié)點(diǎn)不規(guī)則部署的WSN覆蓋模型展開討論；并假定，在可移動節(jié)點(diǎn)執(zhí)行的監(jiān)測區(qū)域內(nèi)，其初始空間位置隨機(jī)分布。通過借助運(yùn)算規(guī)則重新配置節(jié)點(diǎn)，以最大化覆蓋范圍［21］。

借鑒文獻(xiàn)［28］的研究思路，文中引入虛擬勢場和虛擬力概念，提出了一種基于節(jié)點(diǎn)可移動假設(shè)的編隊(duì)覆蓋搜索算法，促使節(jié)點(diǎn)遵循“近則排斥，遠(yuǎn)則吸引”［27］的相互作用原則，達(dá)成任意幾何形狀編隊(duì)部署，并在盡力提高覆蓋程度和覆蓋效率的前提下，有效節(jié)約能耗、延長網(wǎng)絡(luò)使用壽命。

區(qū)域覆蓋要求工作節(jié)點(diǎn)的傳感范圍完全覆蓋整個(gè)區(qū)域，即區(qū)域中的任意一點(diǎn)能夠至少被一個(gè)工作節(jié)點(diǎn)覆蓋。文中運(yùn)用虛擬力算法理論，實(shí)時(shí)計(jì)算出各節(jié)點(diǎn)所受的合力，并將相應(yīng)節(jié)點(diǎn)移動到適當(dāng)?shù)奈恢?，促成整個(gè)監(jiān)測區(qū)域內(nèi)節(jié)點(diǎn)的均勻部署［16］。顯然，該理論與文獻(xiàn)［20］的建模思路是一致的，進(jìn)而驗(yàn)證了筆者擬定的研究方案是可行的。

2.2 節(jié)點(diǎn)覆蓋系統(tǒng)模型

不妨設(shè)監(jiān)測區(qū)域Acov為二維歐式空間（平面），在該區(qū)域上投放參數(shù)相同的傳感器節(jié)點(diǎn)數(shù)目為M，每個(gè)節(jié)點(diǎn)的坐標(biāo)均已知，且感知半徑均為r，通信半徑均為R。為了保證網(wǎng)絡(luò)連通性并兼顧無線干擾，設(shè)置通信半徑R為感知半徑r的兩倍，即R=2r［29］。為簡化問題分析，對傳感器節(jié)點(diǎn)做了6點(diǎn)假設(shè)［4］：1）探測區(qū)域內(nèi)所有節(jié)點(diǎn)處于同一個(gè)二維平面內(nèi)，且將整個(gè)目標(biāo)區(qū)域視為一個(gè)凸區(qū)域；2）探測區(qū)域內(nèi)節(jié)點(diǎn)為同構(gòu)節(jié)點(diǎn)，即每個(gè)節(jié)點(diǎn)具有相同的傳感半徑r，節(jié)點(diǎn)的傳感覆蓋范圍是以r為半徑的圓，傳感覆蓋面積是πr2；3）節(jié)點(diǎn)感知半徑r與節(jié)點(diǎn)無線通信半徑R滿足R≥2r，以確保網(wǎng)絡(luò)中覆蓋即全連通；4）πr2?Acov的面積；5）所有節(jié)點(diǎn)同構(gòu)，即感知半徑與通信半徑分別相同；6）節(jié)點(diǎn)能通過測量或定位方法獲得其具體位置。

目前提出的無線傳感器網(wǎng)絡(luò)覆蓋模型大都基于以下假設(shè)：每個(gè)節(jié)點(diǎn)能對其周圍環(huán)境進(jìn)行全方向探測，其覆蓋范圍是一個(gè)以節(jié)點(diǎn)為圓心，以節(jié)點(diǎn)感知距離為半徑的圓形區(qū)域；區(qū)域內(nèi)所有節(jié)點(diǎn)的探測半徑均相等；監(jiān)測區(qū)域所有傳感器節(jié)點(diǎn)都在同一個(gè)平面內(nèi)［21］；研究發(fā)現(xiàn)，當(dāng)通信半徑達(dá)到探測半徑的2倍以上時(shí)，全覆蓋即保證了全連通。從而該問題可簡化為最小區(qū)域覆蓋問題，即如何使用最少的活躍節(jié)點(diǎn)保證對目標(biāo)區(qū)域的全覆蓋［30］。

2.3 網(wǎng)絡(luò)的連通性保持

傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署以后，就要盡量保證網(wǎng)絡(luò)的連通性。鑒于在第2.2小節(jié)中的分析，可歸納出網(wǎng)絡(luò)保持連通的充分條件是：節(jié)點(diǎn)通信半徑R滿足R≥2r，即要求通信半徑R達(dá)到感知半徑r的2倍以上。

3 網(wǎng)絡(luò)的編隊(duì)覆蓋連通性

3.1 節(jié)點(diǎn)的編隊(duì)部署

編隊(duì)概念的首次探究源于1980年的多個(gè)同步衛(wèi)星簇的軌道共享問題［27，31］。工程中編隊(duì)行為控制可被視為一個(gè)分布式控制問題，于是像李亞普諾夫等系統(tǒng)的穩(wěn)定性分析理論可被有效利用進(jìn)而去分析群體系統(tǒng)的編隊(duì)導(dǎo)航特征及其編隊(duì)集結(jié)行進(jìn)控制［27，32］。若多個(gè)體之間的通信采用通過傳感器互相感知來交流信息的方式，則編隊(duì)現(xiàn)象可被理解為多個(gè)體系統(tǒng)通過各種方式的傳感或通信技術(shù)（基于信息融合）的個(gè)體間相互作用的結(jié)果。

已出現(xiàn)的有關(guān)編隊(duì)的分布式控制方式本質(zhì)上屬于人工勢場法，且該法易于實(shí)際應(yīng)用。分布式控制方式對多個(gè)個(gè)體、障礙和渴望得到的編隊(duì)形式的凸多邊形的頂點(diǎn)施于不同的虛擬力，多個(gè)虛擬力的組合促成了群體中每個(gè)個(gè)體沿著各自的運(yùn)動軌跡行進(jìn)，從而達(dá)到預(yù)期的幾何形狀編隊(duì)位置的各自應(yīng)該占據(jù)的實(shí)際局部極小的專屬空間頂點(diǎn)位置，結(jié)果使得群內(nèi)個(gè)體的最終聚集形式是形成一個(gè)特殊的預(yù)先定義的幾何學(xué)的外形結(jié)構(gòu)，結(jié)構(gòu)的定義可通過一組渴望獲得的交互的智能體間的距離值來表示。

在實(shí)際工程應(yīng)用中，群體中的一族自治的個(gè)體被要求沿著預(yù)先制定的參考軌跡而維持一個(gè)渴望的空間幾何圖形行進(jìn)。與傳統(tǒng)的行進(jìn)方式相比，以編隊(duì)形式行進(jìn)有很多有利條件，例如，它可縮減系統(tǒng)的成本、增強(qiáng)系統(tǒng)的魯棒性和有效性，同時(shí)兼顧容錯(cuò)性，可裝配性和系統(tǒng)結(jié)構(gòu)的柔性。編隊(duì)控制已得以廣泛應(yīng)用，例如，WSN的覆蓋優(yōu)化問題，這是單個(gè)智能體所無法完成的工作。群體編隊(duì)行為控制的研究工作還有助于人們更好地理解昆蟲群體和鳥群等自然界中若干生物群體的社會群居涌現(xiàn)行為［27，33］。

文中對智能群體的編隊(duì)行為進(jìn)行控制時(shí)采用局部優(yōu)化取代傳統(tǒng)的全局優(yōu)化的策略。于是，每一個(gè)體在任一時(shí)刻的位置、速度信息可由迭代計(jì)算得出［27］。從而任一群內(nèi)個(gè)體在每一采樣時(shí)刻均可利用自己的和同伴的位置、速度信息不斷更新得出自己在下一采樣時(shí)刻來臨之前應(yīng)該達(dá)到的空間位置和所需的運(yùn)動速度，進(jìn)行每一步長內(nèi)的空間位置更新（即運(yùn)動）［27］。

針對頭腦中業(yè)已形成的這一研究目標(biāo)，在定義群體的目標(biāo)集時(shí)，認(rèn)為每一群內(nèi)個(gè)體為該集合中相應(yīng)的一個(gè)點(diǎn)集元素，而該元素相應(yīng)的位置、速度信息可用群體中的任意一個(gè)智能個(gè)體與其它個(gè)體間（發(fā)生交互作用的）預(yù)期保持的空間距離值來表征。在此情形下，需要注意的是群內(nèi)個(gè)體每運(yùn)動一個(gè)步長的時(shí)間即會引起下一采樣時(shí)刻個(gè)體元素的位置、速度信息的變化，因此目標(biāo)集是時(shí)變的且需要不斷更新方能保證預(yù)期控制目標(biāo)的實(shí)現(xiàn)。而其控制目標(biāo)經(jīng)由群內(nèi)任一個(gè)體與其它個(gè)體成員間保持渴望的距離值來最終達(dá)成渴望的編隊(duì)形式得以實(shí)現(xiàn)。因此，牛頓迭代法可用于WSN的節(jié)點(diǎn)等不同類型智能群體的編隊(duì)控制。

在這一小節(jié)，將運(yùn)用人工勢場、牛頓 -拉夫遜迭代更新規(guī)則等技術(shù)來數(shù)值仿真分析大規(guī)模智能群體系統(tǒng)如何在形成近似的任意簡單凸多邊形編隊(duì)過程中保持編隊(duì)的穩(wěn)定性。

計(jì)算群內(nèi)個(gè)體i下一時(shí)刻空間位置的“牛頓 -拉夫遜”迭代公式為

其中，λ＞0，為設(shè)計(jì)者對群內(nèi)個(gè)體設(shè)定的步幅增益值；ΔXi（k）為確定個(gè)體運(yùn)動方向的單位運(yùn)動步長矢量［32］。

相應(yīng)的仿真結(jié)果如圖1所示。

圖1表明了渴望的幾何形式編隊(duì)結(jié)構(gòu)中任意兩個(gè)WSN節(jié)點(diǎn)間的邊角關(guān)系，其中黑球代表個(gè)體的最終收斂位置，Vi，i=1，…，M各自代表WSN中不同的節(jié)點(diǎn)構(gòu)成預(yù)期形式的凸多邊形時(shí)各個(gè)節(jié)點(diǎn)應(yīng)占據(jù)的空間位置。

圖2中，多邊形各頂點(diǎn)之間的連線用“﹒”線表示；多邊形的頂點(diǎn)位置用“?！北硎?，表明了WSN在進(jìn)行可移動節(jié)點(diǎn)重新配置后經(jīng)由數(shù)值仿真實(shí)驗(yàn)得出的收斂終態(tài)時(shí)刻各個(gè)節(jié)點(diǎn)應(yīng)占據(jù)的空間局部極小值位置分布點(diǎn)。

圖1 6個(gè)傳感器節(jié)點(diǎn)的預(yù)期等邊三角形編隊(duì)結(jié)構(gòu)Fig.1 The ideal formation configuration of six sensor nodes

圖2 收斂終態(tài)時(shí)刻6個(gè)傳感器節(jié)點(diǎn)的空間分布Fig.2 Congregated positions distribution of six sensor nodes

由上述仿真結(jié)果可見，WSN的節(jié)點(diǎn)在形成任意近似的簡單凸多邊形幾何形式編隊(duì)時(shí)保持穩(wěn)定性的性能優(yōu)良。

3.2 網(wǎng)絡(luò)節(jié)點(diǎn)的編隊(duì)覆蓋搜索

3.2.1 算法仿真示例

在WSN中，假設(shè)每個(gè)節(jié)點(diǎn)的傳感范圍為圓，而且網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的傳感范圍相同。這樣，網(wǎng)絡(luò)對監(jiān)測區(qū)域的覆蓋可抽象成圓覆蓋問題，即用若干數(shù)量的等半徑的圓來覆蓋某固定區(qū)域。節(jié)點(diǎn)的覆蓋區(qū)域可以重疊，以達(dá)到完全覆蓋被監(jiān)測區(qū)域的要求。從節(jié)約網(wǎng)絡(luò)能量、延長網(wǎng)絡(luò)壽命的角度考慮，要用最少的圓最大程度地覆蓋某固定區(qū)域。這里假設(shè)被覆蓋區(qū)域無限大，不考慮邊界的影響，在保證完全覆蓋的要求下節(jié)約能量就是使得覆蓋效率最大［7］。

為檢驗(yàn)該區(qū)域覆蓋算法在目標(biāo)的檢測與移動搜索方面的連通性能，給出WSN編隊(duì)覆蓋搜索的仿真結(jié)果示例。圖3中，“＊”表示隨機(jī)部署的各WSN節(jié)點(diǎn)的初始位置，“。”表示其收斂終態(tài)位置，“﹒”表征各節(jié)點(diǎn)形成預(yù)期編隊(duì)形式的動態(tài)行進(jìn)路徑軌跡。圖4中，“﹒”表征傳感器的節(jié)點(diǎn)及每個(gè)圓的圓心，“-﹒”線圓表征以r為傳感半徑的輻射圓。

上述仿真結(jié)果表明，只要適當(dāng)選取合理的節(jié)點(diǎn)參數(shù)值即感知半徑r，就能保證使WSN的節(jié)點(diǎn)保持對目標(biāo)區(qū)域的全連通和全覆蓋。

圖3 6個(gè)傳感器節(jié)點(diǎn)實(shí)時(shí)動態(tài)編隊(duì)收斂軌跡路徑Fig.3 Convergent trajectories paths of six sensor nodes

圖4 6個(gè)傳感器節(jié)點(diǎn)動態(tài)編隊(duì)覆蓋搜索效果演示Fig.4 Formation coverage search capabilities of six sensor nodes

3.2.2 仿真分析

以上仿真結(jié)果表明在執(zhí)行區(qū)域內(nèi)WSN中的各節(jié)點(diǎn)在交互協(xié)作、協(xié)調(diào)運(yùn)動覆蓋搜索過程中均能以有效的動態(tài)編隊(duì)行進(jìn)形式達(dá)到全連通、全覆蓋，達(dá)到了預(yù)期效果。移動傳感器網(wǎng)絡(luò)的編隊(duì)覆蓋搜索屬于路徑規(guī)劃算法的研究范疇，而路徑規(guī)劃算法是多個(gè)體系統(tǒng)覆蓋研究的核心內(nèi)容，其研究目的均是為了方便進(jìn)行路徑規(guī)劃，以期達(dá)到較好的覆蓋效果。同時(shí)，可以把覆蓋看成是一類WSN對目標(biāo)環(huán)境進(jìn)行無遺漏的完全搜索過程。

4 結(jié)語

文中，首先，詮釋了WSN的覆蓋問題與連通問題間的內(nèi)在聯(lián)系；接著，從理論上分析了所提引入“虛擬力”的WSN可移動節(jié)點(diǎn)的編隊(duì)覆蓋搜索控制算法的可行性；最后，運(yùn)用牛頓-拉夫遜迭代技術(shù)仿真驗(yàn)證了該算法的有效性，豐富了WSN覆蓋理論的既有研究內(nèi)容。

［1］Akyildiz I F，Su W，Sankarasubramaniam Y，et al.Wireless sensor networks：a survey［J］.Computer Networks：The International Journal of Computer and Telecommunications Networking，2002，38（4）：393-422.

［2］任彥，王博，張思東.動態(tài)無線傳感器網(wǎng)絡(luò)基礎(chǔ)設(shè)施建模方法及分析［J］.鐵道學(xué)報(bào)，2009，31（2）：54-58.

Ren Yan，Wang Bo，Zhang Sidong.Modeling and analyzing of dynamic wireless sensor network infrastructures［J］.Journal of the China Railway Society，2009，31（2）：54-58.

［3］田瑩，張淑芳，王瑩.無線傳感器網(wǎng)絡(luò)分布式概率覆蓋保持協(xié)議［J］.通信學(xué)報(bào)，2009，30（1）：70-75.

Tian Ying，Zhang Shufang，Wang Ying.Distributed probabilistic coverage-preserving configuration protocol for wireless sensor network［J］.Journal on Communications，2009，30（1）：70-75.

［4］趙國炳，陳國定，張奇?zhèn)?一種無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化方法［J］.機(jī)電工程，2009，26（6）：80-82.

Zhao Guobing，Chen Guoding，Zhang Qiwei.Coverage optimization of wireless sensor network［J］.Mechanical &Electrical Engineering Magazine，2009，26（6）：80-82.

［5］孫利明，李建中，陳渝.無線傳感器網(wǎng)絡(luò)［M］.北京：清華大學(xué)出版社，2005：3-26.

［6］李曉維，徐勇軍，任豐原.無線傳感器網(wǎng)絡(luò)技術(shù)［M］.北京：北京理工大學(xué)出版社，2007：10-32.

［7］曹峰，劉麗萍，王智.能量有效的無線傳感器網(wǎng)絡(luò)部署［J］.信息與控制，2006，35（2）：147-153.

Cao Feng，Liu Liping，Wang Zhi.A new energy-efficient WSN deployment algorithm ［J］.Information and Control，2006，35（2）：147-153.

［8］于海斌，曾鵬，王忠鋒，等.分布式無線傳感器網(wǎng)絡(luò)通信協(xié)議研究［J］.通信學(xué)報(bào)，2004，25（10）：102-110.

Yu Haibin，Zeng Peng，Wang Zhongfeng，et al.Study of communication protocol of distributed sensor network［J］.Journal of China Institute of Communications，2004，25（10）：102-110.

［9］李建峰，程詠梅.無線傳感器網(wǎng)絡(luò)的研究與發(fā)展［J］.微處理機(jī)，2008，30（5）：48-50.

Li Jianfeng，Cheng Yongmei.The research and development of wireless sensor networks［J］.Microprocessors，2008，30（5）：48-50.

［10］Zhang H，Hou J C.Maintaining sensing coverage and connectivity in large sensor networks［R］.University of Illinois at Urbana Champaign UIUC Computer Science Technical Report，2003，UIUCDCS-R：23-51.

［11］林祝亮，馮遠(yuǎn)靜，俞立.無線傳感網(wǎng)絡(luò)覆蓋的粒子進(jìn)化優(yōu)化策略研究［J］.傳感技術(shù)學(xué)報(bào)，2009，22（6）：873-877.

Lin Zhuliang，F(xiàn)eng Yuanjing，Yu Li.Research on the strategy of wireless sensor networks coverage by the particle optimization evolutionary［J］.Chinese Journal of Sensors and Actuators，2009，22（6）：873-877.

［12］王燕莉，安世全.無線傳感器網(wǎng)絡(luò)的覆蓋問題研究［J］.傳感技術(shù)學(xué)報(bào)，2005，18（2）：307-312.

Wang Yanli，An Shiquan.Research on the coverage of wireless sensor network［J］.Chinese Journal of Sensors and Actuators，2005，18（2）：307-312.

［13］陶丹，孫巖，陳后金.視頻傳感器網(wǎng)絡(luò)中最壞情況覆蓋檢測與修補(bǔ)算法［J］.電子學(xué)報(bào)，2009，37（10）：2284-2290.

Tao Dan，Sun Yan，Chen Houjin.Worst-case coverage detection and repair algorithm for video sensor networks［J］.Acta Electronica Sinica，2009，37（10）：2284-2290.

［14］馬華東，陶丹.多媒體傳感器網(wǎng)絡(luò)及其研究發(fā)展［J］.軟件學(xué)報(bào)，2006，17（9）：2013-2028.

Ma Huadong，Tao Dan.Multimedia sensor network and its research progresses［J］.Journal of Software，2006，17（9）：2013-2028.

［15］Wang B.A survey on coverage problem in wireless sensor networks［R］.ECE Technical Report，ECE Dept，National U-niversity of Singapore，2006.

［16］劉麗萍，李桂丹，王智，等.無線傳感器網(wǎng)絡(luò)多重覆蓋算法［J］.天津大學(xué)學(xué)報(bào)，2009，42（4）：311-315.

Liu Liping，Li Guidan，Wang Zhi，et al.A weighted multiple coverage algorithm in wireless sensor networks［J］.Journal of Tianjin University，2009，42（4）：311-315.

［17］任彥，張思東，張宏科.無線傳感器網(wǎng)絡(luò)中覆蓋控制理論與算法［J］.軟件學(xué)報(bào)，2006，17（3）：422-433.

Ren Yan，Zhang Sidong，Zhang Hongke.Theories and algorithms of coverage control for wireless sensor networks［J］.Journal of Software，2006，17（3）：422-433.

［18］陶丹，馬華東，劉亮.基于虛擬勢場的有向傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)算法［J］.軟件學(xué)報(bào)，2007，18（5）：1152-1163.

Tao Dan，Ma Huadong，Liu Liang.A virtual potential field based coverage-enhancing algorithm for directional sensor networks［J］.Journal of Software，2007，18（5）：1152-1163.

［19］郭怡婷，王俊年.無線傳感器網(wǎng)絡(luò)中基于微粒群算法的優(yōu)化覆蓋機(jī)制［J］.計(jì)算機(jī)與現(xiàn)代化，2009，25（6）：1-4.

Guo Yiting，Wang Junnian.Optimal coverage mechanism based on PSO algorithm in wireless sensor networks［J］.Computer and Modernization，2009，25（6）：1-4.

［20］薛志斌，曾建潮.有限感知群體的動力學(xué)仿真建模與分析［J］.系統(tǒng)仿真學(xué)報(bào)，2009，21（20）：6352-6355.

Xue Zhibing，Zeng Jianchao.Simulation modeling and analysis of dynamics of range limit perceived group［J］.Journal of System Simulation，2009，21（20）：6352-6355.

［21］朱寅寅.無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化方法研究［D］.南京：南京理工大學(xué)，2009：2-17.

Zhu Yinyin.Research on coverage optimization method of wireless sensor network［D］.Nanjing：Nanjing University of Science and Technology，2009：2-17.

［22］陶丹，馬華東，劉亮.視頻傳感器網(wǎng)絡(luò)中路徑覆蓋增強(qiáng)算法研究［J］.電子學(xué)報(bào)，2008，36（7）：1291-1296.

Tao Dan，Ma Huadong，Liu Liang.Study on path coverage enhancement algorithm for video sensor networks［J］.Acta Electronica Sinica，2008，36（7）：1291-1296.

［23］Khatib O.Real-time obstacle avoidance for manipulators and mobile robots［J］.The International Journal of Robotics Research，1986，5（1）：90-98.

［24］劉華軍，楊靜宇，陸建峰，等.移動機(jī)器人運(yùn)動規(guī)劃研究綜述［J］.中國工程科學(xué)，2006，8（1）：85-94.

Liu Huajun，Yang Jingyu，Lu Jianfeng，et al.Research on mobile robots motion planning：a survey［J］.Engineering Sci-ence，2006，8（1）：85-94.

［25］肖甫，王汝傳，葉曉國，等.基于改進(jìn)勢場的有向傳感器網(wǎng)絡(luò)路徑覆蓋增強(qiáng)算法［J］.計(jì)算機(jī)研究與發(fā)展，2009，46（12）：2126-2133.

Xiao Fu，Wang Ruchuan，Ye Xiaoguo，et al.A path coverage-enhancing algorithm for directional sensor network based on improved potential field［J］.Journal of Computer Research and Development，2009，46（12）：2126-2133.

［26］崔益安.多機(jī)器人協(xié)同覆蓋技術(shù)研究［D］.長沙：中南大學(xué)，2008：3-71.

Cui Yi′an.Research on multi-robot coverage based on cooperation［D］.Changsha：Central South University，2008：3-71.

［27］曾建潮，薛志斌.智能群體的微分動力模型描述與仿真［J］.系統(tǒng)仿真技術(shù)及其應(yīng)用，2010，12（1）：176-181.

Zeng Jianchao，Xue Zhibing.Differential dynamic model description and simulation of intelligent swarm：a survey［J］.System Simulation Technology and Application，2010，12（1）：176-181.

［28］Howard A，Mataric M J，Sukhatme G S.Mobile sensor network deployment using potential fields：a distributed，scalable solution to tile area coverage problem ［C］//The 6th International Conference on Distributed Autonomous Robotic System（DARS02）.Tokyo：Springer-Verlag Press，2002：299-308.

［29］林祝亮，馮遠(yuǎn)靜.基于粒子群算法的無線傳感網(wǎng)絡(luò)覆蓋優(yōu)化策略［J］.計(jì)算機(jī)仿真，2009，26（4）：190-193.

Lin Zhuliang，F(xiàn)eng Yuanjing.Optimization strategy of wireless sensor networks coverage based on particle swarm algorithm ［J］.Computer Simulation，2009，26（4）：190-193.

［30］Zhang H，Hou J C.Maintaining sensing coverage and connectivity in large sensor networks［J］.Ad Hoc and Sensor Wireless Networks，2005，1（1/2）：89-124.

［31］Walker J G.The geometry of cluster orbits［J］.J Brit Interplan Soc，1982，35（1）：345-345.

［32］Chen X，Li Y M.Smooth formation navigation of multiple mobile robots for avoiding moving obstacles［J］.International Journal of Control，Automation，and System，2006，4（4）：466-479.

［33］Chen Y Q，Wang Z M.Formation control：a review and a new consideration［C］//IEEE/RSJ，International Conference on Intelligent Robots and Systems（IROS 2005）.Alberta：IEEE Press，2005：3181-3186.

Mobile Sensor Network Formation Coverage Search Control Algorithm

XUE Zhi-bin1，ZENG Jian-chao2，HU Huo-sheng2，XUE Song-dong2
（1.Intelligence System and Control Laboratory，Qinghai University，Xining 810016，China；2.Complex System and Computational Intelligence Laboratory，Taiyuan University of Science and Technology，Taiyuan 030024，China；3.Human Centred Robotics Research Laboratory，University of Essex，Colchester Essex C04 3SQ，UK）

Based on the inspiration to the potential interior operational principle of aggregation from biology，by using artificial potential functions namely APF and Newton-Raphson iteration update rule techniques，by means of the range limit perceived swarm dynamic model with collision-free function，thus realized the automatic distributed sensor node formation deployment problem in wireless sensor networks namely WSN in dynamic unknown environment and the sensor node formation coverage search within the implementation region，further enriched existing coverage search control algorithm.While the requirement of both the network coverage and connectivity is satisfied with the fewest possible sensor working nodes.The algorithm has plain principle，energy saving，and practical.The simulation results have validated its effectiveness.

artificial potential field（APF）；wireless sensor network（WSN）；range limit perceived group；formation；deployment；coverage search

TP393

A

1672-3813（2013）03-0037-08

2012-12-04

國家自然科學(xué)基金（61165016，60975074）；教育部“春暉計(jì)劃”合作科研項(xiàng)目（Z2009-1-81003）；青海大學(xué)高層次人才項(xiàng)目（2012-QGC-10）；山西省自然科學(xué)基金項(xiàng)目（2013011019-4）；太原科技大學(xué)同洲電子科技創(chuàng)新基金項(xiàng)目（TZ201304）

薛志斌（1966-），男，陜西清澗人，博士，教授，主要研究方向?yàn)閺?fù)雜系統(tǒng)建模與仿真、無線傳感器網(wǎng)絡(luò)部署、群智能等。

（責(zé)任編輯 耿金花）