無線傳感執行網絡的協調機制研究
2009-01-01 00:00:00李洪峻李迅馬宏緒
計算機應用研究 2009年1期
（國防科學技術大學 自動控制系， 長沙 410073）
摘 要：主要研究了無線傳感執行網絡中執行節點之間的協調，提出了基于單執行節點任務的分布式協調機制。在多執行節點協調算法中，建立了多執行節點協調的數學模型，引入基于進化算法的多目標優化，提高了系統的最優性能。
關鍵詞：無線傳感執行網絡；協調；多目標優化；進化算法
中圖分類號：TP393 文獻標志碼：A
文章編號：10013695(2009)01025003
Study on coordination of wireless sensor and actor networks
LI Hongjun，LI Xun，MA Hongxu
(Dept. of Automatic Control， National University of Defense Technology， Changsha 410073， China)
Abstract:This paper focused on studying the coordination between the actors. First presented a distributed coordination based on single actor.Then formulated the multiactors coordination as a multiobjective optimization.Presented a solution of the multiobjective optimization based on evolutionary algorithm.
Key words:wireless sensor and actor networks; coordination; multiobjective optimization; evolutionary algorithm
0 引言
無線傳感執行網絡是由部署在監測區域內大量低成本、低功耗、具備感知、數據處理、存儲和無線通信能力的傳感器節點，以及少量具備處理和通信能力，并能主動對外部環境實施操作，且能量資源豐富（更長的電池壽命或者恒定電源）的執行節點通過自組織方式形成的網絡。其目的是由傳感節點協作采集、處理和傳輸網絡覆蓋區域中被感知對象的信息，執行節點根據傳感節點感知信息并對外部環境實施相應的反應。
圖1是無線傳感執行網絡體系結構示意圖。典型的無線傳感執行網絡通常包括傳感節點(sensor nodes)、執行節點(actor nodes) 以及任務管理節點。大量傳感節點及少量執行節點通過隨機部署或確定部署的方式布撒在監測區域內，并通過自組織方式形成多跳無線通信網絡。傳感節點負責從環境中收集數據，而執行節點根據從傳感節點接收到的數據執行相應的操作。匯聚節點一般遠離被監測環境，負責監控整個網絡，并通過Internet或衛星網絡與任務管理節點進行通信，必要時與傳感或執行節點進行通信。
在WSANs中，感知環境信息和對環境進行操作分別由傳感節點和執行節點來實現。對于無線傳感執行網絡的研究，國內剛剛起步。目前，圍繞應用需求以及無線傳感執行網絡的特點，研究熱點主要分為三方面，即管理、協調和通信。
1）管理平臺 能量管理平臺（power management）主要管理節點如何高效地使用有限能量；移動管理平臺（mobility management）檢測并注冊節點的移動，維護網絡的連通性；故障管理平臺（fault management）探測和解決節點故障問題。
2）協調平臺 依據通信平臺和管理平臺接收到的數據，決定節點如何操作。協調平臺的存在對執行節點來說，比對傳感節點更重要。因為在執行決策中，執行節點需要相互協調，以實現任務的分配。
3）通信平臺 該平臺實現節點之間信息及連接關系的交換和共享，是傳感節點和執行節點結構中最重要的一個平臺。通信平臺包括物理層、數據鏈路層、網絡層、傳輸層和應用層。WSANs既有傳感節點與執行節點通信，又有執行節點與執行節點通信。通信所需要實現的高效操作均通過傳感節點和執行節點的協調來實現，而執行數據收集和協調的匯聚節點并不是必需的。
在WSNs中，通信問題主要集中于傳感節點和sink節點之間。而在WSANs中，除了傳感節點與執行節點通信外，還存在執行節點之間的通信，以實現應用的目標。因此，為了提供高效的檢測和反應能力，在傳感節點和執行節點中的局部協調機制是必要的，如傳感節點與傳感節點協調、傳感節點與執行節點協調、執行節點與執行節點協調。傳感節點與傳感節點協調、傳感節點與執行節點協調在WSNs中已有所研究，本文主要研究執行節點與執行節點之間的協調。
1 執行節點與執行節點之間的協調
執行節點在不同的應用環境中，需要與其他節點進行通信協調，如接收到傳感數據的執行節點的作用范圍不足覆蓋事件區域，或沒有足夠能力作出響應時。在執行節點相互通信過程中，協調和任務分配是一個核心問題，本文從以下兩個方面來分析。
11 單執行節點任務(singleactor task，SAT)中分布式協調算法
SAT是指每項任務只需一個執行節點就能完成。在SAT中，如果只有一個執行節點接收到事件信息，并能夠執行所需的操作時，它無須與其他執行節點或決策中心進行通信，以避免超過延遲界限。但如果有多個執行節點從傳感節點接收到事件信息，執行節點就需要相互協調，為該事件選出一個最佳執行節點。
對于SAT，主要問題在于如何選擇單一執行節點。協調算法分為集中式和分布式兩種。集中式是指這種決策過程以集中的方式實現的。它使動作決策以一種有組織的方式進行。集中式的缺點在于如果決策中心遠離事件區，將導致通信延遲時間長，并且當執行節點移動時決策中心很難及時更新網絡中執行節點的位置。因此如何選擇決策中心的執行節點是集中式算法中一個研究難題。分布式算法是指決策過程以分布的方式實現的。它允許相鄰執行節點進行局部協調，以提供及時的操作和獨立于網絡規模的協調。本文主要設計分布式協調算法。
在分布式協調算法中，沒有專門充當決策中心的執行節點，主要是在接收到事件報告的執行節點之間進行協調，以確定執行事件響應的操作。因此通過初始階段的傳感節點、執行節點的位置信息廣播，每個傳感節點記錄自己相鄰的傳感節點ID號和位置信息，以及所有執行節點的ID號和位置信息，而執行節點只需記錄其他執行節點的ID號和位置信息。根據所接收到的執行節點的位置信息，傳感節點選擇信號最強的執行節點作為自己的根節點——事件消息報告的目的地。執行節點之間的邊界是通過動態構造Voronoi圖來劃分的。
為了避免出現多個執行節點同時對該事件作出響應，造成不必要的資源浪費，引入主決策節點的概念。主決策節點的確定與效能函數有密切的關系。假設執行節點具有相同的能力，在同等或相近的條件下，距離事件中心越近，執行節點的效能值（即完成對事件響應的時間）就越大。因此，將包含事件中心的Voronoi區域所屬的執行節點作為該事件的主決策節點。任何需對事件執行操作的執行節點，都必須得到主決策節點的同意。另外，主決策節點收集傳感節點事件報告的計時器的時延，應大于其他執行節點收集事件報告的計時器的時延，以保證在事件的主決策節點計時器超時之前，其他執行節點均能將事件的數據報告給主決策節點。
主決策節點接收到事件的信息熵超過決策閾值時，需要考慮選擇什么樣的執行節點，以使響應事件的任務順利完成。因此主決策節點需要先收集周邊執行節點當前執行對事件響應任務的效能，然后再選擇合適的節點去執行對事件響應的任務。在這里使用基于市場的拍賣規則，用來收集周邊執行節點當前執行本事件任務的效能。
拍賣規則定義：主決策節點作為事件的賣家，發送一個開始消息，將事件的ID號、位置等信息廣播給周邊的執行節點，并啟動一個計時器，以避免拍賣時間過久，使得應用的實時需求無法滿足。周邊的執行節點作為事件的買家，在監聽到開始消息后，提交能夠開始完成任務后所能剩余的能量。在計時器超時后，主決策節點依據周邊節點提交的和自己的執行事件任務的信息，選出一個效能最大的執行節點來執行。
執行節點在接收到開始信息請求時，需要計算自己執行事件的效能。執行節點可利用自身完成任務時的最終時間、位置和所擁有的能量，直接計算執行當前事件所需的效能。主決策節點作出決策后，如果執行節點并非自己，則將執行響應的命令發送給執行節點。
12 多執行節點任務(multiactor task，MAT)協調算法
MAT是指事件任務需要多個執行節點才能完成。在MAT中，無論接收到感知數據的執行節點個數有多少，執行節點都需要相互協調，以確定完成整項任務所需要的節點個數。對于MAT來說，主要問題在于除了需要決定執行操作的最佳執行節點個數，還需要從可執行該項任務的執行節點中選擇出最適合的節點、考慮實時性(時間)等指標。
考慮到MAT協調是一個復雜的問題，本文把它建模為一個多目標組合優化問題。多目標優化問題的多個優化目標之間往往是互相沖突的，求解時需要在不同的目標之間進行妥協。一般而言，一個目標性能的提高通常會導致其他目標性能的下降。因此，多目標優化問題的解通常不是一個，而是一組，這些解的特點是：無法在改進任何目標函數的同時不削弱至少一個其他目標函數，即綜合考慮所有的目標，不存在比它們更優的解。這些解就是Pareto最優解，其概念最早由法國經濟學家V.Pareto提出。本文把精力放在尋找近似最優解或者滿意解上。進化算法基于種群的計算特性和隱并行性使得算法能夠在一次執行過程中，基于Pareto優劣性同時處理多個優化目標，并且生成一組解，這些解體現了在多個目標之間不同的折中程度，能夠為決策者提供更多、更全面的信息。進化算法作為多目標優化問題的求解方法是尋求這種滿意解的最佳工具之一。進化多目標優化（evolutionary multiobjective optimization，EMO）已經成為近年來多目標優化研究的一個熱門領域，提出了大量豐富的研究成果。本文通過研究基于多目標優化的適應值計算、多樣性保持以及精英策略等關鍵問題來解決MAT協調問題。
假設SA為執行器節點集合，執行器節點個數為NA=|SA|。每個執行器節點的作用范圍由自身能力決定，相鄰的執行器節點的作用范圍可能出現交叉重疊，如圖2所示。
設AA，nov和AA，ov為非重疊區域和重疊區域。設SA，mA，ov為可以在第m個重疊區域執行任務的執行節點的集合。設PA為執行器節點A能用來執行任務的總能量，把執行節點A的能量分為l個等級，PmA為執行節點A的第m等級的能量，即PmA=mPA/l。無線傳感執行網絡中執行器節點之間的協調問題可以看做多目標尋優問題，定義如下：
a)Xm為二值矩陣，矩陣的元素xma，p等于1當且僅當執行器節點a利用第p等級的能量執行區域Ama，ov的任務；
b)Tma，p為執行器節點單獨在第m個重疊區域使用第p等級的能量完成任務的總時間；
c)ha=1，當且僅當執行器節點a被選中去執行任務Th；
d)任務Th需要完成的總工作時間為T；
e)事件event發生地點與actor的距離為d(event，ACTORa)，actor移動速度為va。
多目標優化問題Pmin:tasktimemin:reqestenergy用數學描述如下：
給定無線傳感執行網絡參數：NA，l，Tma，p，T，γ；
求解Xm=[xma，p]，ha(1)
使得minimize F(p)=Ereqavg，NAa=1Tma，p (2)
約束條件如下：
對于a，Eresa=EAva-Ereqz≥0(3)
對于a，Eresa=Mcm=1lp=1xma，pPma，p/[NAa=1lp=1xma，p/Tma，p](4)
對于 a、p，Tma，p=d(event，ACTORa)/va+T/NAa=1ha(5)
對于a，m，lp=1xma，p≤1;NAa=1lp=1xma，p≥1(6)
對于a，ha≤lp=1Mcm=1xma，p(7)
對于a，p，m，ha≥xma，p(8)
式（2）給出了目標函數，要求無線傳感執行網絡完成任務時取得能量消耗最小、工作時間最少的性能指標；式(3)保證節點具有正的能量；式（4）描述了執行器節點完成任務所需要的能量；式（5）定義了執行節點完成任務所耗費的時間；式（6）描述了每個執行節點僅使用其自身一部分能量，并且至少有一個執行節點去執行任務；式（7）（8）描述了變量ha與xma，p的關系。
進化多目標優化算法主要設計適應值計算、多樣性保持以及精英策略三個重要問題。下面主要研究這三個關鍵問題。
1）適應值計算 進化算法用于解決單目標優化問題時，適應值計算方法相對簡單。個體的適應值可以與目標函數值等價，或者基于優化目標函數值進行一定的變換得到。但是當進化算法解決多目標優化問題時，情況要復雜得多，需要考慮如何將多維的目標函數向量轉換為標量的適應值。本文采用基于Pareto最優性的賦值策略。
基于Pareto最優性的賦值方法是目前的MOEA中應用最廣的方法，也是Pareto最優概念與進化算法的真正結合。這種賦值方法是以Pareto優劣性這種偏序關系為基礎的，個體的適應值可以通過在種群中支配的個體數目、被支配的個體數目或個體位于的非劣層數來體現。
2）多樣性保持 多目標進化算法找出的是問題的近似Pareto最優解集和近似Pareto最優層，為了給決策者提供更多的信息，希望找到盡可能多的不同Pareto最優解，而且對應的Pareto 最優層能夠體現在多個目標上不同的妥協程度。在EMO研究中，多樣性保持主要體現在兩方面：a)對個體進行適應值計算時，對于相同Pareto優劣性的個體，利用個體的密度信息對基于Pareto優劣性的初始適應值進行修正，使得個體被選中的概率隨其密度的增大而減少；b)當利用有限規模的外部種群存儲進化過程中找到的非劣解時，為了維持外部種群的規模，對Pareto相當的個體，根據密度信息刪除鄰域密度大的個體，以維持外部種群的規模。
實現多樣性保持的關鍵是在當前的非劣個體集合中對個體的密度信息進行評價。本文采用核函數法(kernel method)。核函數法根據核函數K定義個體的鄰域，核函數通常以個體到其他個體的距離為變量。對于每個個體，首先計算個體到種群中所有其他個體i的距離di后得到K(di)，所有K(di)的總和即為該個體的密度評估值。
3）精英策略 進化過程中，隨機因素的存在，會導致有些Pareto最優解在進化過程中被丟失。為了避免這一問題，現代MOEA設計中均引入了精英策略的思想，這也成為第二代MOEA的顯著標志。精英策略的基本思想是保留當前高性能的解。精英策略的引入，提高了MOEA的收斂效率，改善了近似Pareto最優解集的質量，成為目前MOEA設計中不可缺少的一部分。
對于多目標優化問題，由于Pareto最優解集的存在，精英策略的實現比較復雜。實現精英策略的方法是構建一個外部種群，許多算法中也稱之為精英池（archive），存儲進化過程中找到的非劣解。外部種群參與到進化過程中時，算法的性能得到很大的提高，加快收斂速度和提高算法的魯棒性。在采用外部種群的MOEA中，需要解決的一個重要問題是如何隨著進化過程的進行更新外部種群。
一般來說，個體進入外部種群的條件是：該個體是當前進化種群中的非劣解并且在外部種群中不存在比該個體更優的解。但是，到了進化的晚期，非劣個體的數目可能會很多，因此需要采用一定的策略來控制外部種群的規模。為了在控制外部種群規模的同時盡可能地保持近似Pareto層的多樣性，多數MOEA均結合了Pareto支配關系和密度評估方法來進行外部種群的更新。對于相同Pareto優劣性的個體，優先選擇周圍個體比較稀疏的個體進入外部種群，而刪除鄰域密度比較大的個體，這種操作在MOEA中一般也稱為剪枝（truncate），剪枝算子的具體實現根據采用的密度評估方法不同而不同。
2 性能評估
1）平均移動距離 在不同的應用中，隨著并發事件數的增加，執行節點的移動距離有所增加。在分布式算法中，采用先滿足決策閾值的事件先選擇事件執行的原則，雖然不能保證執行節點的移動距離是最優的，但可以保證是次優的，不是最壞的。
2）系統的開銷 它主要由初始化、傳感節點事件探測和事件報告、反應節點協調及反應節點位置更新的開銷構成。首先分析算法中一個事件所對應的反應節點協調的開銷：假定傳感反應網絡中的反應節點個數為N，接收到傳感節點事件報告的反應節點的個數為M。在分布式算法中，因主決策節點采取的策略不同，反應節點協調的開銷差別較大。采用拍賣策略，在最壞的情況下，主決策節點將會接收到（M-1）個來自其他反應節點的數據報告，同時還要發送加入任務的消息；其他位于通信范圍內的反應節點將提交自己執行事件的效能，反應節點有（N-1）個；最后主決策節點發送執行命令給執行節點；因此總共有（N＋M）個。在最好的情況下，競拍策略也只減少其他反應節點的數據報告和發送命令消息，因此需N個。采用設定起拍價的拍賣策略，可以有效地減少其他反應節點提交執行事件的效能。在最好的情況下，只需一個加入執行任務的消息，抑制其他反應節點報告事件信息，因為在自己執行效能高于其他節點時，其他反應節點無須提交執行的效能。在最差的情況下，等同于一般的拍賣策略，也是（N＋M）個。
對于多執行器節點協調系統，通過已有的多目標優化的研究成果可以得到最優的MAT協調效果。
3 結束語
無線傳感執行網絡是涉及多學科的新型網絡，具有極為廣闊的應用前景，對國防和國民經濟的發展具有十分重要的意義。本文就無線傳感執行網絡的協作機制進行了研究和探討。研究了無線傳感執行網絡中執行節點之間的協調機制，提出了基于單執行節點任務的分布式協調機制；以基于進化算法的多目標優化為基礎，建立了多執行器節點協調的數學模型，提出了多執行節點協調算法，提高系統的最優性能。
參考文獻：
［1］
AKYILDIZ I F，KASIMOGLU I H.Wireless sensor and actor networks:research challenges[J].Ad hoc Networks，2004，2(4):351367.
［2］HAENGGI M.Mobile sensoractuator networks: opportunities and challenges[C]//Proc of the 7th IEEE Int’l Workshop.Frankfort:IEEE Press，2002：283290.
［3］AKYILDIZ I F，SU W，CAYIRCI Y S E.Wireless sensor networks:a survey[J].Computer Networks，2002，38(4):393422.
［4］MELODIA T，POMPILI D，VEHBIC G.A distributed coordination framework for wireless sensor and actor networks[C]//Proc of ACM Mobile Ad hoc Networking and Computing.New York:ACM Press，2005:99110.
［5］孫利民，李建中.無線傳感器網絡[M].北京：清華大學出版社，2005.
［6］CALLAWAYE H.Wireless sensor networks:architectures and protocols[M].[S.l.]:CRC Press，2003.
［7］MELODIA T，POMPILI D，AKYILDIZ I F.A communication architecture for mobile wireless sensor and actor networks[C]//Proc of IEEE SECON.[S.l.]:IEEE Press，2006.
[8]崔遜學.一種求解高維優化問題的多目標遺傳算法及其收斂性分析[J].計算機研究與發展，2003，40(7):901906.
[9]AGUIRRE A H，RIONDA S B，COELLO C A C.Handling constraints using multiobjective optimization concepts[J].International Journal for Numerical Methods in Engineering，2004，59(15):19892017.
[10]DRAGAN C，IAN C P.Preferences and their application in evolutionary multiobjective optimization[J].IEEE Trans on Evolutionary Computation，2002，6(1):4257.
［11］ FONSECA C M，FLEMING P J.An overview of evolutionary algorithms in multiobjective optimization[J].Evolutionary Computation，1995，3(1):1116.
