周有為，楊 強(qiáng)

（國(guó)防科學(xué)技術(shù)大學(xué) 信息系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室，湖南 長(zhǎng)沙 410073）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

在圖1中，所有節(jié)點(diǎn)的觀(guān)點(diǎn)值（即對(duì)事件M的判斷值）如圖1（a）所示，對(duì)于中間的節(jié)點(diǎn)i，共有3個(gè)鄰居節(jié)點(diǎn)，兩個(gè)鄰居節(jié)點(diǎn)的觀(guān)點(diǎn)值為1，另一個(gè)的值為0。因此，在下一個(gè)時(shí)刻，中間的節(jié)點(diǎn)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

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

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

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

3 結(jié)束語(yǔ)

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

[1]李建中，高宏，于博.信息物理融合系統(tǒng)（CPS）的概念、特點(diǎn)、挑戰(zhàn)和研究進(jìn)展[C]//中國(guó)計(jì)算機(jī)學(xué)會(huì).2009中國(guó)計(jì)算機(jī)科學(xué)技術(shù)發(fā)展報(bào)告，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ò)的擴(kuò)散性事件監(jiān)測(cè)技術(shù)研究[D].合肥:中國(guó)科學(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ò)中的社團(tuán)結(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é)報(bào)，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.