周有為，楊 強

（國防科學(xué)技術(shù)大學(xué) 信息系統(tǒng)工程重點實驗室，湖南 長沙 410073）

CPS綜合了傳感系統(tǒng)、通信系統(tǒng)、計算系統(tǒng)和控制系統(tǒng)，目的在于更廣泛的互聯(lián)互通、更透徹的認知物理世界、更有效的控制物理世界，使信息世界與物理世界緊密融合，實現(xiàn)對物理世界安全、可靠、高效、實時、協(xié)同的感知和控制[1]。傳感系統(tǒng)實現(xiàn)對物理世界的直接感知，通過通信系統(tǒng)將感知的信息傳遞給CPS計算系統(tǒng)和控制系統(tǒng)，實現(xiàn)對物理世界的控制和決策。感知是CPS的基礎(chǔ)，感知的正確性和有效性是CPS實現(xiàn)正確控制的前提。大多數(shù)情況下，CPS中的節(jié)點數(shù)目量級較大，單個節(jié)點的感知能力有限，感知的數(shù)據(jù)存在不確定性，因此需要CPS節(jié)點之間協(xié)同感知。CPS中節(jié)點之間可能是完全對等的，也可能存在中心節(jié)點來協(xié)同網(wǎng)絡(luò)中的節(jié)點。中心節(jié)點的計算能力較強，負責(zé)控制，管理，協(xié)同一定區(qū)域內(nèi)的節(jié)點。CPS中協(xié)同感知是指節(jié)點不僅要知道自己的狀態(tài)，還要了解一定鄰域范圍內(nèi)其余節(jié)點的狀態(tài)，多節(jié)點協(xié)同，共同完成一項任務(wù)，這樣可以有效提升CPS感知的正確性和可靠性。

目前在事件監(jiān)測中表現(xiàn)出較為穩(wěn)定性能的方法有兩種，Jiang[2]等提出了一種使用R樹結(jié)構(gòu)來監(jiān)測感知網(wǎng)絡(luò)中的事件。Fan[3]等提出了一種名為ToD的方法，這種方法使用動態(tài)轉(zhuǎn)發(fā)技術(shù)監(jiān)測事件是否發(fā)生。Jiang給出的R樹方法需要感知節(jié)點知道事件區(qū)域的形狀，F(xiàn)an提出的動態(tài)轉(zhuǎn)發(fā)方法需要事先知道事件位置，同時事件要有已知區(qū)域上限[4]。

本文利用復(fù)雜網(wǎng)絡(luò)中的社團結(jié)構(gòu)劃分劃分算法和觀點動力學(xué)中的多數(shù)投票者模型，給出一種新的思路來求解感知網(wǎng)絡(luò)中節(jié)點對事件狀態(tài)的判斷。

1 CPS協(xié)同感知問題

我們主要考慮存在中心節(jié)點的CPS感知網(wǎng)絡(luò)，中心節(jié)點自身的通信能力、計算能力比網(wǎng)絡(luò)中其他節(jié)點強。首先不考慮中心節(jié)點自身的能耗，主要研究在節(jié)點網(wǎng)絡(luò)拓撲（即節(jié)點的部署位置）確定的情況下選取哪些節(jié)點作為中心節(jié)點，中心節(jié)點如何協(xié)同區(qū)域的其他節(jié)點，使所有節(jié)點形成對事件M的一致判斷。

在一個區(qū)域S部署了N個節(jié)點，這N個節(jié)點是密集部署的，N個節(jié)點協(xié)同感知一個事件M，節(jié)點感知的物理信息為F，每個節(jié)點有一個敏感區(qū)間[ai，bi]（i=1，2，…，N），當(dāng)節(jié)點 i感知的信息fi∈[ai，bi]時，節(jié)點i判定事件 M發(fā)生，節(jié)點i對事件 M的感知狀態(tài)值更新為1（我們假定節(jié)點對事件E的感知狀態(tài)默認值為0）。單個節(jié)點感知信息的可靠度和準確性有限，如何選取中心節(jié)點，中心節(jié)點如何協(xié)同區(qū)域中的其他節(jié)點，最后形成所有節(jié)點對事件M感知狀態(tài)的判斷是我們求解的問題。

2 基于社團結(jié)構(gòu)的協(xié)同感知策略

CPS中單個節(jié)點的感知能力，計算能力和通信能力都是有限的，每個節(jié)點只能和其鄰域的節(jié)點進行通信，N個節(jié)點可以抽象為一個網(wǎng)絡(luò)G（V，E），V表示網(wǎng)絡(luò)的節(jié)點，E表示網(wǎng)絡(luò)中的邊。在我們描述的問題中，V代表節(jié)點，E代表能夠相互通信的節(jié)點之間的鏈路，我們可以用復(fù)雜網(wǎng)絡(luò)以及觀點動力學(xué)中的相關(guān)理論來研究CPS中節(jié)點的協(xié)同感知問題。算法的過程如下：

1）CPS節(jié)點網(wǎng)絡(luò)社團劃分 首先選取中心節(jié)點位置。在CPS節(jié)點感知網(wǎng)絡(luò)中，節(jié)點的數(shù)量級較大，可以將CPS節(jié)點網(wǎng)絡(luò)抽象為一個復(fù)雜網(wǎng)絡(luò)，網(wǎng)絡(luò)的頂點表示節(jié)點的位置，網(wǎng)絡(luò)中的邊連接能夠直接通信的節(jié)點。利用復(fù)雜網(wǎng)絡(luò)的社團結(jié)構(gòu)分析算法對CPS節(jié)點網(wǎng)絡(luò)進行社團劃分，CPS感知網(wǎng)絡(luò)的節(jié)點數(shù)量級通常很高，因此需要選取適當(dāng)?shù)纳鐖F劃分算法。Newman提出的凝聚算法[5]分析的節(jié)點數(shù)量可以達到百萬個，對于CPS感知網(wǎng)絡(luò)來說，這種算法較為適用。

凝聚算法通過模塊性來衡量網(wǎng)絡(luò)質(zhì)量的劃分[6]。若一種社團劃分的算法將網(wǎng)絡(luò)劃分為k個社團。定義一個k階方陣E=（eij），其中元素eij表示網(wǎng)絡(luò)中連接兩個不同社團的節(jié)點的邊在所有邊中所占的比例，這兩個節(jié)點分別位于第i個社團和第j個社團[7]矩陣E中主對角線上各元素之和為每行各元素之和為模塊性的定義為：

①將每個節(jié)點獨立的看作一個社團，這樣在初始條件下網(wǎng)絡(luò)中一共有n個社團。。

②依次合并有邊相連的社團對，按照式（2）計算合并后的Q值增量，每次合并沿著使Q增大或者減小的方向進行。

③重復(fù)第②步，不斷合并社團，直到整個網(wǎng)絡(luò)都合并成為一個社團。這個過程最多執(zhí)行n-1次。

以上步驟完成后能夠得到一個社團結(jié)構(gòu)分解的樹狀圖。在不同位置斷開就可以得到不同的社團結(jié)構(gòu)。在這些社團結(jié)構(gòu)中，選取局部最大的Q值，就可以得到最好的社團結(jié)構(gòu)[7]。

當(dāng)網(wǎng)絡(luò)的社團劃分結(jié)束后，分別考慮每個社團內(nèi)部的網(wǎng)絡(luò)結(jié)構(gòu)，建立每個社團網(wǎng)絡(luò)節(jié)點間的距離矩陣Dij。Dij中的元素dij表示節(jié)點i和節(jié)點j的最短路徑。距離矩陣每i行的和n為 表示節(jié)點i與社團內(nèi)部其余所有節(jié)點最短路徑的距｝離總和，其中n為網(wǎng)絡(luò)節(jié)點的數(shù)目。求解（i=1，2，…，n），選取距離總和最小的節(jié)點作為社團的中心節(jié)點，中心節(jié)點負責(zé)協(xié)同社團內(nèi)部的節(jié)點。

當(dāng)網(wǎng)絡(luò)完成第一次社團劃分后，我們可以將網(wǎng)絡(luò)的中心節(jié)點再次抽象成一個復(fù)雜網(wǎng)絡(luò)，再次進行社團劃分，選取第二級的中心節(jié)點，這個過程可以迭代下去，定義迭代重數(shù)k，根據(jù)網(wǎng)絡(luò)規(guī)模的實際大小確定迭代的次數(shù)，從而實現(xiàn)對網(wǎng)絡(luò)的分層控制。

2）社團內(nèi)部的節(jié)點協(xié)同 每個中心節(jié)點負責(zé)處理社團內(nèi)部節(jié)點的感知信息，社團內(nèi)部的協(xié)同可以采用常用的觀點動力學(xué)模型，例如投票者模型，多數(shù)決定模型等。根據(jù)應(yīng)用的不同選取適當(dāng)?shù)哪Ｐ停鐖F內(nèi)部節(jié)點的感知信息匯集到中心節(jié)點，每個中心節(jié)點處理該社團內(nèi)的感知信息，然后網(wǎng)絡(luò)中所有中心節(jié)點再次進行協(xié)同，中心節(jié)點的協(xié)同也可以采用觀點動力學(xué)中的模型，最后實現(xiàn)CPS感知網(wǎng)絡(luò)的協(xié)同。社團內(nèi)部節(jié)點的協(xié)同過程為：CPS系統(tǒng)中的節(jié)點感知一種特定的物理信息F，定義區(qū)間[a，b]為節(jié)點對F的敏感區(qū)間。當(dāng)節(jié)點感知的信息f∈[a，b]時，感知節(jié)點判斷事件E被觸發(fā)，節(jié)點對應(yīng)的值更新為1，否則節(jié)點的值保持為0，由于單個節(jié)點的感知存在不確定和不可靠性，因此需要社團內(nèi)的節(jié)點協(xié)同。社團內(nèi)的每個節(jié)點對于事件M存在感知狀態(tài)（0或1），節(jié)點對事件M的感知狀態(tài)是一個二值判斷，我們采用多數(shù)投票模型實現(xiàn)社團內(nèi)部節(jié)點的協(xié)同，多數(shù)決定模型描述個體決策時主要利用鄰居節(jié)點的信息，觀點更新時選取數(shù)目占優(yōu)的觀點值。節(jié)點下一時刻選取某觀點的概率正比于周圍鄰居所持此觀點的總數(shù)目[8]。最終整個局域網(wǎng)絡(luò)達到同步，即觀點的統(tǒng)一。

在圖1中，所有節(jié)點的觀點值（即對事件M的判斷值）如圖1（a）所示，對于中間的節(jié)點i，共有3個鄰居節(jié)點，兩個鄰居節(jié)點的觀點值為1，另一個的值為0。因此，在下一個時刻，中間的節(jié)點i以2/3的概率選擇狀態(tài) 1（如圖1（b）所示），1/3的概率選擇狀態(tài)0（即保持現(xiàn)有狀態(tài)）。

圖1 多數(shù)決定模型演化示意圖Fig.1 Sketch map of majority rule model

需要強調(diào)的是，CPS的感知網(wǎng)絡(luò)中，單個節(jié)點感知的信息是確定的，節(jié)點自身對感知信息的判斷是不會發(fā)生改變的。我們只是借用觀點動力學(xué)的模型來模擬整個節(jié)點網(wǎng)絡(luò)感知狀態(tài)的演化，整個演化的計算過程由中心節(jié)點完成，最后確定整個局域網(wǎng)絡(luò)對事件M的感知判斷。

3）社團間進行協(xié)同 對網(wǎng)絡(luò)進行一次社團劃分之后，每個社團內(nèi)部確定一個中心節(jié)點，中心節(jié)點代表社團內(nèi)部運用觀點動力學(xué)模型演化后對事件M的判斷值，每個社團中心節(jié)點之間可以再次抽象為一個復(fù)雜網(wǎng)絡(luò)，可以再次對這個網(wǎng)絡(luò)進行社團分析，用觀點動力學(xué)的模型進行演化。這個過程可以迭代下去，根據(jù)網(wǎng)絡(luò)的規(guī)模確定迭代的次數(shù)，最終整個網(wǎng)絡(luò)達到一致，即得出所有感知節(jié)點對事件M的判斷

凝聚算法的時間復(fù)雜度為O（（m+n）n），其中m為網(wǎng)絡(luò)的邊的數(shù)目，n為網(wǎng)絡(luò)的節(jié)點數(shù)目。對于多數(shù)決定模型，Krapivsky等[9]研究了方格上的二值觀點傳播，整個網(wǎng)絡(luò)觀點達到一致的收斂時間量級為In n，n為網(wǎng)絡(luò)節(jié)點的數(shù)目[8]。因此，整個網(wǎng)絡(luò)對事件M判斷的收斂速度是較快的，同時本文給出的求解方法不需要事先知道事件區(qū)域的形狀，節(jié)點網(wǎng)絡(luò)能夠形成對事件快速，可靠的判斷。

3 結(jié)束語

本文給出一種基于社團結(jié)構(gòu)的CPS感知網(wǎng)絡(luò)中心節(jié)點選取算法以及局域內(nèi)部節(jié)點的協(xié)同方法。CPS感知網(wǎng)絡(luò)中心節(jié)點的正確選取可以優(yōu)化感知網(wǎng)絡(luò)的協(xié)同，尤其是CPS節(jié)點在大規(guī)模、高密度部署的情況下，中心節(jié)點的選取及節(jié)點之間的協(xié)同感知更加重要。本文主要討論了感知節(jié)點對感知事件的判斷是二值的情況。在有些情況下，感知節(jié)點的感知信息是連續(xù)的，這時需要采用與之相應(yīng)的觀點動力學(xué)模型模擬CPS感知網(wǎng)絡(luò)節(jié)點的演化。同時，在確定事件發(fā)生后，如何確定事件源的位置也是今后需要研究的內(nèi)容。

[1]李建中，高宏，于博.信息物理融合系統(tǒng)（CPS）的概念、特點、挑戰(zhàn)和研究進展[C]//中國計算機學(xué)會.2009中國計算機科學(xué)技術(shù)發(fā)展報告，2010:2-17.

[2]Jiang C，Dong G，Wang B.Detection and tracking of region based evolving targets in Sensor Networks[C]//Proceedings of 14th International Conference on Computer Communications and Networks，San Diego，California，USA.2005:563-568.

[3]Fan K W，Liu S，Sinha P.Scalable data aggregation for dynamic events in sensor networks[C]//Proceedings of the International Conference on Sensor Systems（SenSys），Boulder，Colorado，USA.2006:181-194.

[4]崔筱寧.基于傳感器網(wǎng)絡(luò)的擴散性事件監(jiān)測技術(shù)研究[D].合肥:中國科學(xué)技術(shù)大學(xué)，2010.

[5]Newman M E J.Fast algorithm for detecting community structure in networks[J].Phys rev E，2004，69（6）:066133.

[6]Newman M E J，Givran M.Finding and evaluating community structure in networks[J].Phys rev E，2004，69（2）:026133.

[7]解鄒，汪小帆.復(fù)雜網(wǎng)絡(luò)中的社團結(jié)構(gòu)分析算法研究綜述[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2005，2（3）：1-12.XIE Zou，WANG Xiao-fan.An overview of algorithms for analyzing community structure in complex networks[J].Complex Systems and Complexity Science，2005，2（3）：1-12.

[8]王龍，伏鋒，陳小杰，等.復(fù)雜網(wǎng)絡(luò)上的群體決策[J].智能系統(tǒng)學(xué)報，2008，3（2）：95-108.WANG Long，F(xiàn)U Feng，CHEN Xiao-jie，et al.Collective decision-making over complex networks [J]. CAAI Transactions on Intelligent Systems，2008，3（2）：95-108.

[9]Krapivsky P L，Redner S.Dynamics of majority rule in twostate interacting spin systems[J].Phys Rev Lett，2003，90（23）：238701.