一種基于社團結構的CPS節點協同感知方法

周有為，楊 強

（國防科學技術大學 信息系統工程重點實驗室，湖南 長沙 410073）

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

目前在事件監測中表現出較為穩定性能的方法有兩種，Jiang[2]等提出了一種使用R樹結構來監測感知網絡中的事件。Fan[3]等提出了一種名為ToD的方法，這種方法使用動態轉發技術監測事件是否發生。Jiang給出的R樹方法需要感知節點知道事件區域的形狀，Fan提出的動態轉發方法需要事先知道事件位置，同時事件要有已知區域上限[4]。

本文利用復雜網絡中的社團結構劃分劃分算法和觀點動力學中的多數投票者模型，給出一種新的思路來求解感知網絡中節點對事件狀態的判斷。

1 CPS協同感知問題

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

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

2 基于社團結構的協同感知策略

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

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

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

①將每個節點獨立的看作一個社團，這樣在初始條件下網絡中一共有n個社團。。

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

③重復第②步，不斷合并社團，直到整個網絡都合并成為一個社團。這個過程最多執行n-1次。

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

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

當網絡完成第一次社團劃分后，我們可以將網絡的中心節點再次抽象成一個復雜網絡，再次進行社團劃分，選取第二級的中心節點，這個過程可以迭代下去，定義迭代重數k，根據網絡規模的實際大小確定迭代的次數，從而實現對網絡的分層控制。

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

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

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

需要強調的是，CPS的感知網絡中，單個節點感知的信息是確定的，節點自身對感知信息的判斷是不會發生改變的。我們只是借用觀點動力學的模型來模擬整個節點網絡感知狀態的演化，整個演化的計算過程由中心節點完成，最后確定整個局域網絡對事件M的感知判斷。

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

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

3 結束語

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

[1]李建中，高宏，于博.信息物理融合系統（CPS）的概念、特點、挑戰和研究進展[C]//中國計算機學會.2009中國計算機科學技術發展報告，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]崔筱寧.基于傳感器網絡的擴散性事件監測技術研究[D].合肥:中國科學技術大學，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]解鄒，汪小帆.復雜網絡中的社團結構分析算法研究綜述[J].復雜系統與復雜性科學，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]王龍，伏鋒，陳小杰，等.復雜網絡上的群體決策[J].智能系統學報，2008，3（2）：95-108.WANG Long，FU 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.