無(wú)線傳感器網(wǎng)絡(luò)協(xié)同任務(wù)分配研究

摘 要： 無(wú)線傳感器網(wǎng)絡(luò)的任務(wù)協(xié)同主要是任務(wù)的描述、分解、分配、調(diào)度和執(zhí)行。任務(wù)分配是任務(wù)協(xié)同的主要內(nèi)容，任務(wù)分配的方案直接決定著網(wǎng)絡(luò)能耗，從而影響網(wǎng)絡(luò)的生命周期。著重分析了無(wú)線傳感器網(wǎng)絡(luò)協(xié)同技術(shù)以及啟發(fā)式算法解決任務(wù)分配的問(wèn)題，并給出了無(wú)線傳感器網(wǎng)絡(luò)任務(wù)分配需要進(jìn)一步研究的內(nèi)容和方向。

關(guān)鍵字： 無(wú)線傳感器網(wǎng)絡(luò)； 任務(wù)協(xié)同； 任務(wù)分配； 啟發(fā)式算法

中圖分類(lèi)號(hào)： TN711?34； TP393 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2013）23?0044?03

Research of collaborative task allocation in wireless sensor networks

WANG Jian， WANG Fu?bao， DUAN Wei?jun， HUANG Liang

（School of Electronics and Information， Northwestern Polytechnical University， Xi’an 710072， China）

Abstract：The task collaboration of wireless sensor networks （WSNs） refers to task description， decomposition， allocation， scheduling and execution. The task allocation is the main content of task collaboration. Furthermore， the scheme of task allocation directly determines the network energy consumption， and affects the network lifetime. The collaboration technology of wireless sensor networks and heuristic algorithm to solve collaborative task allocation problem are analyzed emphatically. Finally， the contents and direction for further research in future are put forward.

Keywords： wireless sensor networks； task collaboration； task allocation； heuristic algorithm

0 引 言

微機(jī)電系統(tǒng)（Microelectromechanical Systems，MEMS）、微處理器以及 Ad?hoc網(wǎng)絡(luò)協(xié)議的迅猛發(fā)展孕育出了無(wú)線傳感器網(wǎng)絡(luò)[1]，無(wú)線傳感器網(wǎng)絡(luò)是由大量廉價(jià)且資源有限的傳感器節(jié)點(diǎn)組成。由于每個(gè)傳感器節(jié)點(diǎn)資源有限以及計(jì)算和通信能力有限，單個(gè)節(jié)點(diǎn)無(wú)法解決網(wǎng)絡(luò)規(guī)模龐雜的問(wèn)題，更無(wú)法解決網(wǎng)絡(luò)全局性問(wèn)題。基于以上原因，WSNs中的傳感器節(jié)點(diǎn)要相互協(xié)同以完成任務(wù)。

WSNs協(xié)同主要包括協(xié)同資源的使用，協(xié)同任務(wù)的分配和執(zhí)行以及協(xié)同信息與信號(hào)的處理[2]。任務(wù)協(xié)同中的主要部分是任務(wù)分配，因?yàn)槿蝿?wù)分配方案直接決定著網(wǎng)絡(luò)能耗，從而決定了網(wǎng)絡(luò)的整體壽命。因此，WSNs協(xié)同任務(wù)分配具有重要的理論和現(xiàn)實(shí)意義。

1 無(wú)線傳感器網(wǎng)絡(luò)任務(wù)分配協(xié)同技術(shù)

由于WSNs具有采用射頻通信、能量有限、計(jì)算和通信能力較弱以及大規(guī)模高密度部署等特點(diǎn)，所以傳統(tǒng)分布式系統(tǒng)的協(xié)同方法并不能直接應(yīng)用于WSNs，目前WSNs協(xié)同技術(shù)是來(lái)自分布式人工智能領(lǐng)域的多智能體理論。基于多智能體的WSNs協(xié)同技術(shù)有基于協(xié)商的方法、基于動(dòng)態(tài)聯(lián)盟的方法、分布式約束滿足法和組織結(jié)構(gòu)設(shè)計(jì)方法四種。

1.1 基于協(xié)商的方法

基于協(xié)商的方法是以多智能體中的協(xié)商理論為模型，將協(xié)商模型與拍賣(mài)方法和合同網(wǎng)相結(jié)合而形成，目前用于解決WSNs協(xié)同問(wèn)題的主要是組合拍賣(mài)（Combinatorial Auction）和動(dòng)態(tài)仲裁（Dynamic Arbitration）兩種方法[2]。組合拍賣(mài)和動(dòng)態(tài)仲裁采取的都是集中式的任務(wù)分配方法，即存在一個(gè)中心節(jié)點(diǎn)，該中心節(jié)點(diǎn)要和周?chē)?jié)點(diǎn)進(jìn)行協(xié)商最終完成對(duì)任務(wù)的分配過(guò)程；組合拍賣(mài)對(duì)任務(wù)的組合由周?chē)?jié)點(diǎn)完成，而動(dòng)態(tài)仲裁任務(wù)的組合和分配都是由中心節(jié)點(diǎn)完成。相對(duì)來(lái)說(shuō)，后者更容易在網(wǎng)絡(luò)中形成能量空洞。

文獻(xiàn)[3?4]采用基于協(xié)商的方法解決任務(wù)分配，在CNP（Contract Net Protocol）中引入了推理模型和能量閾值，實(shí)現(xiàn)了高效節(jié)能的任務(wù)分配，減少了網(wǎng)絡(luò)中的能量空洞，從而延長(zhǎng)了網(wǎng)絡(luò)的壽命。

1.2 基于動(dòng)態(tài)聯(lián)盟的方法

動(dòng)態(tài)聯(lián)盟是基于事件觸發(fā)的，當(dāng)節(jié)點(diǎn)捕獲到事件時(shí)會(huì)形成一個(gè)聯(lián)盟，并且由該聯(lián)盟負(fù)責(zé)任務(wù)的處理；當(dāng)聯(lián)盟完成任務(wù)后，聯(lián)盟也將隨之而解散。其過(guò)程主要包括動(dòng)態(tài)聯(lián)盟初始化、聯(lián)盟形成和聯(lián)盟確認(rèn)三個(gè)階段。在當(dāng)前的無(wú)線傳感器網(wǎng)絡(luò)協(xié)同任務(wù)分配機(jī)制中，動(dòng)態(tài)聯(lián)盟機(jī)制占據(jù)了重要的地位；由于其是基于事件觸發(fā)的，能夠針對(duì)任務(wù)情況動(dòng)態(tài)地協(xié)同任務(wù)的分配。

針對(duì)目標(biāo)跟蹤問(wèn)題，文獻(xiàn)[1]提出了基于拍賣(mài)的動(dòng)態(tài)聯(lián)盟任務(wù)分配機(jī)制，和基于案例推理的動(dòng)態(tài)聯(lián)盟機(jī)制相比提高了目標(biāo)跟蹤的準(zhǔn)確性并且降低了能耗；文獻(xiàn)[5]基于動(dòng)態(tài)聯(lián)盟提出了EATA（Effective Adaptive Task Allocation），每個(gè)節(jié)點(diǎn)通過(guò)EATA可以自主調(diào)整自身參數(shù)和狀態(tài)，實(shí)現(xiàn)了資源利用最大化并延長(zhǎng)了網(wǎng)絡(luò)壽命。

1.3 分布式約束滿足法

分布式滿足方法采用的是一種映射的思想，其將傳感器節(jié)點(diǎn)、傳感器節(jié)點(diǎn)行為模式以及傳感器節(jié)點(diǎn)間的關(guān)系分別映射為變量、變量的取值以及變量間的約束關(guān)系，從而將WSNs中的協(xié)同問(wèn)題轉(zhuǎn)化為分布式約束滿足問(wèn)題進(jìn)行解決。分布式約束滿足法將任務(wù)分配問(wèn)題映射成DCSP問(wèn)題，采用DCSP方法解決問(wèn)題，最終形成任務(wù)分配的方案，Pragnesh J.M等人給出將傳感器網(wǎng)絡(luò)中追蹤問(wèn)題轉(zhuǎn)化為DCSP問(wèn)題的方法。

1.4 組織結(jié)構(gòu)設(shè)計(jì)方法

組織結(jié)構(gòu)設(shè)計(jì)方法是根據(jù)無(wú)線傳感器網(wǎng)絡(luò)大規(guī)模部署特點(diǎn)提出的，其包括簡(jiǎn)單分層和垂直分層。該方法將整個(gè)網(wǎng)絡(luò)劃分為不同的區(qū)域，通過(guò)指派區(qū)域管理員負(fù)責(zé)區(qū)域內(nèi)以及區(qū)域間的通信，但是該方法需要事先指定每個(gè)傳感器節(jié)點(diǎn)的角色[6]。由于組織結(jié)構(gòu)設(shè)計(jì)方法是針對(duì)無(wú)線傳感器大規(guī)模特點(diǎn)提出的，所以能夠很好地解決大規(guī)模無(wú)線傳感器網(wǎng)絡(luò)中目標(biāo)跟蹤問(wèn)題，通常用于區(qū)域監(jiān)視。

以上技術(shù)都有其應(yīng)用場(chǎng)景及優(yōu)缺點(diǎn)。對(duì)于小規(guī)模網(wǎng)絡(luò)問(wèn)題，協(xié)商方法和動(dòng)態(tài)聯(lián)盟方法比較適合，但是對(duì)于大規(guī)模網(wǎng)絡(luò)問(wèn)題則會(huì)面臨組合爆炸的難題。然而，對(duì)于大規(guī)模網(wǎng)絡(luò)問(wèn)題，組織結(jié)構(gòu)設(shè)計(jì)方法能夠很好的解決，但是，由于節(jié)點(diǎn)的通信范圍受到了限制，組織結(jié)構(gòu)設(shè)計(jì)方法會(huì)面臨邊界的問(wèn)題。由于將無(wú)線傳感器網(wǎng)絡(luò)任務(wù)分配問(wèn)題映射成DCSP問(wèn)題是個(gè)復(fù)雜、低效的過(guò)程，分布式約束滿足法在傳感器網(wǎng)絡(luò)任務(wù)分配方面還不成熟。三種協(xié)同技術(shù)的性能比較見(jiàn)表1。

2 啟發(fā)式算法解決任務(wù)分配

由于任務(wù)分配是一個(gè)NP的組合優(yōu)化問(wèn)題，目前已經(jīng)有許多啟發(fā)式算法來(lái)解決該問(wèn)題。常用啟發(fā)式算法有遺傳算法、粒子群優(yōu)化等。對(duì)于任務(wù)分配問(wèn)題，啟發(fā)式算法并不是單純利用某個(gè)啟發(fā)式算法解決問(wèn)題，其通常與協(xié)同技術(shù)相結(jié)合。

表1 三種技術(shù)比較

文獻(xiàn)[7]采用遺傳算法對(duì)聯(lián)盟中的任務(wù)進(jìn)行分配，其優(yōu)化了遺傳算法初始種群的選擇和交叉/變異運(yùn)算并且引入了Metropolis準(zhǔn)則，改善了任務(wù)分配效率的同時(shí)降低了通信開(kāi)銷(xiāo)。文獻(xiàn)[8]針對(duì)現(xiàn)有任務(wù)分配算法無(wú)法解決容錯(cuò)問(wèn)題，其引入了PB（Primary/Backup）機(jī)制，采用PSO（Particle Swarm Optimization）進(jìn)行任務(wù)分配，提高了無(wú)線傳感器網(wǎng)絡(luò)任務(wù)分配的可靠性。文獻(xiàn)[9]引入動(dòng)態(tài)聯(lián)盟模型，以任務(wù)執(zhí)行時(shí)間和能量消耗構(gòu)建適應(yīng)度函數(shù)，采用改善的粒子群優(yōu)化算法進(jìn)行任務(wù)優(yōu)化，降低了網(wǎng)絡(luò)能耗且縮短了任務(wù)的執(zhí)行時(shí)間。

WSN任務(wù)分配旨在資源和效率以及全局搜索和局部求解之間尋求平衡。為了降低網(wǎng)絡(luò)能耗，延長(zhǎng)網(wǎng)絡(luò)的壽命，啟發(fā)式算法適應(yīng)度函數(shù)選取及優(yōu)化相當(dāng)重要；由于任務(wù)分配是全局尋優(yōu)問(wèn)題，一些啟發(fā)式算法容易陷入局部最優(yōu)，所以啟發(fā)式算法引入了一些算子或者對(duì)算法本身已有的算子進(jìn)行修正。

文獻(xiàn)[10]在遺傳算法中引入了混雜的適應(yīng)度函數(shù)來(lái)進(jìn)行任務(wù)分配，延長(zhǎng)了網(wǎng)絡(luò)的整體壽命。文獻(xiàn)[11]引入動(dòng)態(tài)聯(lián)盟思想，構(gòu)造了無(wú)線傳感器網(wǎng)絡(luò)的動(dòng)態(tài)聯(lián)盟模型，提出了一種基于離散粒子群優(yōu)化的任務(wù)分配算法，引入了變異算子，在保持種群多樣性的同時(shí)提高了算法的全局搜索能力，該算法在局部求解和全局尋優(yōu)之間取得了較好的平衡并且降低了任務(wù)分配的時(shí)間和網(wǎng)絡(luò)的能耗。

遺傳算法和粒子群優(yōu)化算法均可用于無(wú)線傳感器網(wǎng)絡(luò)任務(wù)分配的問(wèn)題，一般前者可直接應(yīng)用，而當(dāng)適應(yīng)度函數(shù)是離散時(shí)，后者需重新定義速度及位置更新公式等。由于無(wú)線傳感器網(wǎng)絡(luò)本身資源有限性的特點(diǎn)，二者在構(gòu)造適應(yīng)度函數(shù)時(shí)必須考慮無(wú)線傳感器網(wǎng)絡(luò)資源；對(duì)于有實(shí)時(shí)性需求的問(wèn)題，還需考慮任務(wù)分配的執(zhí)行時(shí)間，此時(shí)建議采用粒子群優(yōu)化算法進(jìn)行任務(wù)分配。二者優(yōu)缺點(diǎn)比較見(jiàn)表2。

表2 遺傳算法和粒子群優(yōu)化算法比較

3 結(jié) 語(yǔ)

由于無(wú)線傳感器網(wǎng)絡(luò)本身所具有的節(jié)點(diǎn)資源有限性、動(dòng)態(tài)拓?fù)湫浴?shù)據(jù)傳輸不可靠性等特點(diǎn)，需要從節(jié)能性、實(shí)時(shí)性和可靠性等方面對(duì)無(wú)線傳感器網(wǎng)絡(luò)的任務(wù)分配進(jìn)行改善。現(xiàn)有研究者主要從節(jié)能性的角度對(duì)無(wú)線傳感器網(wǎng)絡(luò)任務(wù)分配和調(diào)度進(jìn)行相應(yīng)的研究，從而最大限度地延長(zhǎng)整個(gè)網(wǎng)絡(luò)的壽命。但是任務(wù)分配的實(shí)時(shí)性和可靠性以及能源高效性方面的研究比較少，因此，這一部分還需要進(jìn)一步地研究。

參考文獻(xiàn)

[1] CHEN Jian?xia， ZANG Chuan?zhi， LIANG Wei. Auction?based dynamic coalition for single target tracking in wireless sensor network [C]// Proceedings of Sixth World Congress on Intelligent Control and Automation. New York： IEEE， 2006： 94?98.

[2] 車(chē)暢，梁周悅，等.基于多智能體的無(wú)線傳感器網(wǎng)絡(luò)協(xié)同問(wèn)題研究[J].儀器儀表學(xué)報(bào)，2005，26（8）：229?232.

[3] LI Yu?kun， GAO Zhi?peng， YANG Yang. A cluster?based negotiation model for task allocation in wireless sensor network [C]// Proceedings of 2010 International Conference on Network and Service Management. Niagara Falls： CNSM， 2010： 112?117.

[4] TIAN Wang?lan， LEI Hong?yan. An energy efficient task allocation method based on reasoning model in wireless sensor networks [J]. Advanced Materials Research， 2011， 268： 440?445 .

[5] CHEN Ying， GUO Wen?zhong， CHEN Guo?long. A dynamic?alliance?based adaptive task allocation algorithm in wireless sensor networks [C]// Proceedings of 2010 9th International Conference on Grid and Cooperative Computing. Nanjing： I GCC， 2010： 356?360.

[6] 朱興國(guó).無(wú)線傳感器網(wǎng)絡(luò)任務(wù)協(xié)同技術(shù)研究[D].西安：西北工業(yè)大學(xué)，2007.

[7] TAO Hai?jun，WANG Ya?dong， GUO Mao?zu. An extended contract?net negotiation model based on task coalition and genetic algorithm [C]// 2007 International Conference on Machine Learning and Cybernetics. Hong Kong： IEEE， 2007： 879?884.

[8] CHEN Cheng?yu， GUO Wen?zhong， CHEN Guo?long. A new task allocation algorithm based on dynamic coalition in WSNs [C]// Proceedings of 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops PhD Forum （IPDPSW）. Shanghai： IEEE， 2012： 1243?1248.

[9] QIU Ying?hui， LIU Chun?lei. A collaborative task allocation mechanism for wireless sensor networks [J]. International Review on Computers and Software， 2012， 7（7）： 3821?3825.

[10] JIN Yi?chao， WEI Da?li， GLUHAK A. Latency and energy?consumption optimized task allocation in wireless sensor networks [C]// Proceedings of 2010 IEEE Wireless Communications and Networking Conference （WCNC）. Sydney， Australia： IEEE， 2010： 1?6.

[11] CHEN Guo?long， GUO Wen?zhong， CHEN Yu?zhong. Research on dynamic alliance of task allocation and its algorithm in wireless sensor networks [J]. Journal on Communications， 2009， 30（11）： 48?55.

作者簡(jiǎn)介：王 建 男，1987年出生，江蘇徐州人，碩士研究生。研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)。