移動傳感器網絡編隊覆蓋搜索控制算法

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

（1.青海大學智能系統與控制實驗室，西寧 810016；2.太原科技大學復雜系統與計算智能實驗室，太原 030024；3.埃塞克斯大學以人為本機器人研究室，埃塞克斯郡科爾切斯特C04 3SQ）

移動傳感器網絡編隊覆蓋搜索控制算法

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

（1.青海大學智能系統與控制實驗室，西寧 810016；2.太原科技大學復雜系統與計算智能實驗室，太原 030024；3.埃塞克斯大學以人為本機器人研究室，埃塞克斯郡科爾切斯特C04 3SQ）

受生物群體聚集機理的啟發，運用勢場理論與牛頓——拉夫遜迭代技術，借助具有碰撞規避功能的有限感知群體動力學模型，實現了動態未知環境下無線傳感器網絡分布式節點的編隊部署及其在執行區域內的編隊覆蓋搜索，豐富了已有的覆蓋搜索控制算法。以盡可能少的工作節點達到了網絡的連通性覆蓋要求，原理簡單，節能性好，實用，仿真結果驗證了該算法的有效性。

人工勢場；無線傳感器網絡；有限感知群體；編隊；節點部署；覆蓋搜索

0 引言

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

無線傳感器網絡是由部署在監測區域內的、大量的、可協作地感知對象信息的微型傳感器節點組成的集數據采集、數據處理、數據傳輸及信息傳遞功能于一體的復雜系統，已成為近期國內外網絡研究的熱點［5-8］。

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

為了解決這一覆蓋連通性問題，通過引入群智能理論，以群集行為中的涌現機理為基礎，借助筆者在前期工作中提出的有限感知群體動力學模型［20］，用于設計無線傳感器網絡的優化覆蓋策略，實現了WSN的編隊最優覆蓋搜索算法。最后，一系列仿真實驗驗證了該算法的有效性，在保證監測區域內整個網絡的連通性覆蓋性能的同時，兼顧了網絡覆蓋質量和網絡資源的優化。算法簡單、運行速度快，能有效收斂于最優解，降低了網絡能耗，為設計更加實用的覆蓋控制算法提供了依據。

1 相關工作

1.1 WSN覆蓋優化

WSN覆蓋優化問題的研究現狀是結合不同應用環境的需求，設計、應用切實可行的、合理的覆蓋控制策略，使各種資源得到優化分配，是當前無線傳感器網絡領域的一個研究熱點［21］。此類覆蓋優化問題依據節點的配置方式可以分為確定性覆蓋和隨機性覆蓋兩類子問題；同時，依據WSN的應用屬性可將此類覆蓋優化問題劃分為節能覆蓋、柵欄覆蓋、連通性覆蓋和目標定位覆蓋等子問題［17］。

鑒于此，本文的設計目標是實現WSN節點的隨機連通性編隊覆蓋搜索控制。

1.2 虛擬勢場法

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

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

路徑規劃是機器人研究的一個重要內容。常規的路徑規劃是指點到點的最優路徑規劃，其目標是尋找一條從起始點到目標點的無碰撞最優（最短或代價最小）路徑。而覆蓋任務中的路徑規劃要求路徑能保證機器人遍歷整個目標區域，其目的有兩個方面：保證遍歷每一點達到完全覆蓋和盡量避免重復路徑提高覆蓋效率。多機器人覆蓋是指多個機器人協作、快速高效地遍歷一個含障區域內的全部自由空間［26］。正是由于移動機器人運動路徑規劃應用研究的需要，物理學中的場的概念才被引進來描述機器人在空間中的幾何結構，引導機器人向目標行進。這些場包括常見的勢場，還有距離場以及來自于水力分析的基于流函數的規劃算法。國內對后兩種算法研究甚少［24］。

在傳感器網絡路徑覆蓋計算中，路徑軌跡點對傳感器節點具有引力，并且在感知半徑r范圍內，距離越遠引力函數值越大，反之越小。當距離為零時，路徑軌跡點對傳感器節點的引力勢函數為零，斥力勢函數為無窮大以免發生節點間的碰撞。此時路徑軌跡點與傳感器節點處于同一位置［25］。

1.3 感知模型

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

相應的引力/斥力相互作用函數關系式可描述為

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

2 覆蓋數學模型

2.1 節點部署

所謂節點部署，即通過一定的算法布置網絡節點，優化現有的網絡資源。通常，選用的網絡節點部署方法需要在完成監測任務的前提下，盡量節省能耗以延長網絡壽命［7］。

筆者的目標是就節點不規則部署的WSN覆蓋模型展開討論；并假定，在可移動節點執行的監測區域內，其初始空間位置隨機分布。通過借助運算規則重新配置節點，以最大化覆蓋范圍［21］。

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

區域覆蓋要求工作節點的傳感范圍完全覆蓋整個區域，即區域中的任意一點能夠至少被一個工作節點覆蓋。文中運用虛擬力算法理論，實時計算出各節點所受的合力，并將相應節點移動到適當的位置，促成整個監測區域內節點的均勻部署［16］。顯然，該理論與文獻［20］的建模思路是一致的，進而驗證了筆者擬定的研究方案是可行的。

2.2 節點覆蓋系統模型

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

目前提出的無線傳感器網絡覆蓋模型大都基于以下假設：每個節點能對其周圍環境進行全方向探測，其覆蓋范圍是一個以節點為圓心，以節點感知距離為半徑的圓形區域；區域內所有節點的探測半徑均相等；監測區域所有傳感器節點都在同一個平面內［21］；研究發現，當通信半徑達到探測半徑的2倍以上時，全覆蓋即保證了全連通。從而該問題可簡化為最小區域覆蓋問題，即如何使用最少的活躍節點保證對目標區域的全覆蓋［30］。

2.3 網絡的連通性保持

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

3 網絡的編隊覆蓋連通性

3.1 節點的編隊部署

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

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

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

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

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

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

計算群內個體i下一時刻空間位置的“牛頓 -拉夫遜”迭代公式為

其中，λ＞0，為設計者對群內個體設定的步幅增益值；ΔXi（k）為確定個體運動方向的單位運動步長矢量［32］。

相應的仿真結果如圖1所示。

圖1表明了渴望的幾何形式編隊結構中任意兩個WSN節點間的邊角關系，其中黑球代表個體的最終收斂位置，Vi，i=1，…，M各自代表WSN中不同的節點構成預期形式的凸多邊形時各個節點應占據的空間位置。

圖2中，多邊形各頂點之間的連線用“﹒”線表示；多邊形的頂點位置用“。”表示，表明了WSN在進行可移動節點重新配置后經由數值仿真實驗得出的收斂終態時刻各個節點應占據的空間局部極小值位置分布點。

圖1 6個傳感器節點的預期等邊三角形編隊結構Fig.1 The ideal formation configuration of six sensor nodes

圖2 收斂終態時刻6個傳感器節點的空間分布Fig.2 Congregated positions distribution of six sensor nodes

由上述仿真結果可見，WSN的節點在形成任意近似的簡單凸多邊形幾何形式編隊時保持穩定性的性能優良。

3.2 網絡節點的編隊覆蓋搜索

3.2.1 算法仿真示例

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

為檢驗該區域覆蓋算法在目標的檢測與移動搜索方面的連通性能，給出WSN編隊覆蓋搜索的仿真結果示例。圖3中，“＊”表示隨機部署的各WSN節點的初始位置，“。”表示其收斂終態位置，“﹒”表征各節點形成預期編隊形式的動態行進路徑軌跡。圖4中，“﹒”表征傳感器的節點及每個圓的圓心，“-﹒”線圓表征以r為傳感半徑的輻射圓。

上述仿真結果表明，只要適當選取合理的節點參數值即感知半徑r，就能保證使WSN的節點保持對目標區域的全連通和全覆蓋。

圖3 6個傳感器節點實時動態編隊收斂軌跡路徑Fig.3 Convergent trajectories paths of six sensor nodes

圖4 6個傳感器節點動態編隊覆蓋搜索效果演示Fig.4 Formation coverage search capabilities of six sensor nodes

3.2.2 仿真分析

以上仿真結果表明在執行區域內WSN中的各節點在交互協作、協調運動覆蓋搜索過程中均能以有效的動態編隊行進形式達到全連通、全覆蓋，達到了預期效果。移動傳感器網絡的編隊覆蓋搜索屬于路徑規劃算法的研究范疇，而路徑規劃算法是多個體系統覆蓋研究的核心內容，其研究目的均是為了方便進行路徑規劃，以期達到較好的覆蓋效果。同時，可以把覆蓋看成是一類WSN對目標環境進行無遺漏的完全搜索過程。

4 結語

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

［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］任彥，王博，張思東.動態無線傳感器網絡基礎設施建模方法及分析［J］.鐵道學報，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］田瑩，張淑芳，王瑩.無線傳感器網絡分布式概率覆蓋保持協議［J］.通信學報，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］趙國炳，陳國定，張奇偉.一種無線傳感器網絡覆蓋優化方法［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］孫利明，李建中，陳渝.無線傳感器網絡［M］.北京：清華大學出版社，2005：3-26.

［6］李曉維，徐勇軍，任豐原.無線傳感器網絡技術［M］.北京：北京理工大學出版社，2007：10-32.

［7］曹峰，劉麗萍，王智.能量有效的無線傳感器網絡部署［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］于海斌，曾鵬，王忠鋒，等.分布式無線傳感器網絡通信協議研究［J］.通信學報，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］李建峰，程詠梅.無線傳感器網絡的研究與發展［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］林祝亮，馮遠靜，俞立.無線傳感網絡覆蓋的粒子進化優化策略研究［J］.傳感技術學報，2009，22（6）：873-877.

Lin Zhuliang，Feng 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］王燕莉，安世全.無線傳感器網絡的覆蓋問題研究［J］.傳感技術學報，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］陶丹，孫巖，陳后金.視頻傳感器網絡中最壞情況覆蓋檢測與修補算法［J］.電子學報，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］馬華東，陶丹.多媒體傳感器網絡及其研究發展［J］.軟件學報，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］劉麗萍，李桂丹，王智，等.無線傳感器網絡多重覆蓋算法［J］.天津大學學報，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］任彥，張思東，張宏科.無線傳感器網絡中覆蓋控制理論與算法［J］.軟件學報，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］陶丹，馬華東，劉亮.基于虛擬勢場的有向傳感器網絡覆蓋增強算法［J］.軟件學報，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］郭怡婷，王俊年.無線傳感器網絡中基于微粒群算法的優化覆蓋機制［J］.計算機與現代化，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］薛志斌，曾建潮.有限感知群體的動力學仿真建模與分析［J］.系統仿真學報，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］朱寅寅.無線傳感器網絡覆蓋優化方法研究［D］.南京：南京理工大學，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］陶丹，馬華東，劉亮.視頻傳感器網絡中路徑覆蓋增強算法研究［J］.電子學報，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］.中國工程科學，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］.計算機研究與發展，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］崔益安.多機器人協同覆蓋技術研究［D］.長沙：中南大學，2008：3-71.

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

［27］曾建潮，薛志斌.智能群體的微分動力模型描述與仿真［J］.系統仿真技術及其應用，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］林祝亮，馮遠靜.基于粒子群算法的無線傳感網絡覆蓋優化策略［J］.計算機仿真，2009，26（4）：190-193.

Lin Zhuliang，Feng 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

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

薛志斌（1966-），男，陜西清澗人，博士，教授，主要研究方向為復雜系統建模與仿真、無線傳感器網絡部署、群智能等。

（責任編輯 耿金花）