張志飛 凌志浩，2 高 沖

(華東理工大學(xué)化工過程先進(jìn)控制與優(yōu)化技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室1，上海 200237;華東理工大學(xué)自動(dòng)化系2，上海 200237)

0 引言

近年來，隨著 WiFi Direct的興起，其軟接入點(diǎn)(access point，AP)功能為終端協(xié)同網(wǎng)絡(luò)提供了參考的模型。研究協(xié)同交互過程的中心節(jié)點(diǎn)自舉對(duì)組建WiFi的軟AP協(xié)同網(wǎng)絡(luò)具有重要意義。

作為終端協(xié)同的重要前提，服務(wù)及鄰居發(fā)現(xiàn)指的是對(duì)周邊服務(wù)及設(shè)備進(jìn)行搜索和發(fā)現(xiàn)。Ad-hoc網(wǎng)絡(luò)下的服務(wù)發(fā)現(xiàn)協(xié)議得到了廣泛的研究，例如基于應(yīng)用層的 PDP［1］、GSD［2］、SSD［3］和基于網(wǎng)絡(luò)層的 DSDP［4］、AODV-SD［5］、M-ZRP［6］等;鄰居發(fā)現(xiàn)的研究包括同步發(fā)現(xiàn)［7］和異步發(fā)現(xiàn)［8］的研究。本文考慮異步情況，異步情況更加貼近于實(shí)際的應(yīng)用。近年來，基于約束圖的多Agent一致性協(xié)調(diào)算法已經(jīng)得到了控制領(lǐng)域的深入研究［9－10］。但是基于多Agent的終端協(xié)同及分布式IT系統(tǒng)依然少見。本文將借助多Agent一致性算法研究帶通信約束的中心節(jié)點(diǎn)自舉過程。

1 問題及描述

終端協(xié)同指通過終端之間的相互合作，為用戶提供更加優(yōu)良的服務(wù)體驗(yàn)，其過程包括服務(wù)及設(shè)備發(fā)現(xiàn)、互通及互操作等。為了更有效地進(jìn)行組織和交互，無中心的分布式終端需要通過自舉形成軟AP，提供協(xié)同網(wǎng)絡(luò)管理、服務(wù)及設(shè)備發(fā)現(xiàn)功能。軟AP可以將分布式終端互發(fā)現(xiàn)轉(zhuǎn)變?yōu)閱蜗虬l(fā)現(xiàn)，其他終端只需要搜索該中心節(jié)點(diǎn)，即可找到協(xié)同網(wǎng)絡(luò)中的所有節(jié)點(diǎn)，并能通過中心節(jié)點(diǎn)自動(dòng)獲取IP地址，申請(qǐng)加入該協(xié)同網(wǎng)絡(luò)。因此，中心節(jié)點(diǎn)自舉過程實(shí)現(xiàn)了從分布式Ad-hoc網(wǎng)絡(luò)到具有軟AP的層次網(wǎng)絡(luò)的轉(zhuǎn)變。

中心節(jié)點(diǎn)自舉過程指對(duì)等網(wǎng)絡(luò)中的各終端通過交互，在各自終端設(shè)備上執(zhí)行中心節(jié)點(diǎn)自舉算法，最終選舉產(chǎn)生唯一的終端作為中心節(jié)點(diǎn)。

在自舉過程中，面臨著以下兩個(gè)主要的問題:①各終端的時(shí)鐘不一定嚴(yán)格同步，如何設(shè)計(jì)中心自舉算法，以避免時(shí)鐘異步對(duì)自舉過程造成的影響;②在一定范圍內(nèi)不一定能夠完全發(fā)現(xiàn)其他所有節(jié)點(diǎn)，如何在具有通信約束的網(wǎng)絡(luò)中設(shè)計(jì)中心節(jié)點(diǎn)自舉算法，以保證最終選舉結(jié)果的一致性。

1.1 異步自舉過程建模

異步自舉過程指在初始時(shí)刻不同的情況下，通過自舉產(chǎn)生唯一中心節(jié)點(diǎn)的過程。為了實(shí)現(xiàn)異步自舉過程的描述，定義了以下變量:Tb為信號(hào)幀的時(shí)長(zhǎng)，M為信道的個(gè)數(shù)。假設(shè)在信號(hào)幀之間存在Tb時(shí)長(zhǎng)的空閑時(shí)間，那么完成一個(gè)幀信號(hào)的全部時(shí)長(zhǎng)為2Tb。接收端工作于某一信道時(shí)，發(fā)送端可能工作于任何可能的信道，而只有在與接收端相同的信道上發(fā)送的信號(hào)才能被接收。如果發(fā)送端有M個(gè)信道，則需要長(zhǎng)度為2TbM的發(fā)送時(shí)間?？紤]到時(shí)鐘的非同步性，需要增加2Tb的余量，所以發(fā)送端需要保證在2Tb(M+1)時(shí)長(zhǎng)內(nèi)在可用信道上連續(xù)發(fā)送信號(hào)幀。接收端為了確保與發(fā)送端可用信道有交集，需要在M個(gè)信道上進(jìn)行輪詢，這就使得發(fā)送端必須維持2Tb(M+1)M時(shí)長(zhǎng)才能保證被接收端搜索到，T1=2Tb(M+1)M被稱為搜索時(shí)長(zhǎng)。

搜索時(shí)長(zhǎng)示意圖如圖1所示。

圖1 搜索時(shí)長(zhǎng)示意圖Fig.1 Diagram of searching duration

為了更好地進(jìn)行描述，可根據(jù)圖1定義兩種工作模式:搜索模式(scanning mode，SM)和自舉模式(contending mode，CM)，并實(shí)現(xiàn)兩者之間的切換。

①在搜索模式中，接收來自其他節(jié)點(diǎn)自舉的信號(hào)。如果接收到來自其他節(jié)點(diǎn)的自舉消息，則不再進(jìn)行自舉;如果執(zhí)行T1時(shí)長(zhǎng)后沒有收到自舉消息，則將自己推薦為中心節(jié)點(diǎn)，進(jìn)入自舉模式。

②在自舉模式中，從某一信道連續(xù)發(fā)出自舉消息，供其他節(jié)點(diǎn)搜索，執(zhí)行的時(shí)長(zhǎng)為xT1。其中，x為與參數(shù)有關(guān)的變量，體現(xiàn)終端之間的異構(gòu)性。以剩余的能量為例，如果剩余能量越高，則x越大，相應(yīng)的自舉時(shí)間越長(zhǎng)，也就越有可能成為中心節(jié)點(diǎn)。為了保證終端之間的異構(gòu)性，也可選擇ID號(hào)作為參數(shù)，因?yàn)镮D號(hào)具有唯一性，ID號(hào)越大，能夠獲得的自舉機(jī)會(huì)越多。

異步自舉過程需要實(shí)現(xiàn)的目標(biāo)是在節(jié)點(diǎn)時(shí)鐘不同步的情況下，通過搜索模式和自舉模式之間的切換，自舉產(chǎn)生唯一的中心節(jié)點(diǎn)。

1.2 通信約束建模

通信約束表現(xiàn)為終端之間的直接互通所受到的限制，可以利用圖論對(duì)其進(jìn)行建模。以G=(V，E)表示網(wǎng)絡(luò)拓?fù)洌渲蠽={1，2，…，n}為節(jié)點(diǎn)集合，E?V×V為邊的集合。節(jié)點(diǎn)的鄰域?yàn)镹i={vj∈V(i，j)∈E}。節(jié)點(diǎn)只能向鄰域內(nèi)的節(jié)點(diǎn)進(jìn)行信息的交互，而并不能與全網(wǎng)內(nèi)的所有節(jié)點(diǎn)都進(jìn)行信息交互。由于在同一條邊上的兩個(gè)節(jié)點(diǎn)既是CM中自舉消息的發(fā)送端，也是SM 中自舉消息的接收端，所以邊(i，j)、(j，i)∈E，(i，j)=(j，i)的圖為無向圖。

1.3 一致性算法

圖G=(V，E)中的一致性是通過局部的通信達(dá)成的。一致性達(dá)成指漸進(jìn)收斂于一維空間的某一點(diǎn)x=αI，即 x1=x2= … =xn= α，其中 I=(1，…，1)T，α∈R為群組決策的結(jié)果。令A(yù)=［aij］為G的鄰接矩陣，如果(i，j)∈E，則 aij=1;否則，aij=0。對(duì)于無向圖，aij=aji。鄰域 Ni={j∈V|(i，j)∈E}可以表示為 Ni={j∈V|aij≠0}，所有的邊組成的集合可以定義為E={(i，j)∈V×V|aij≠0}。對(duì)于離散模型，分布式一致性算法可以描述為:

如果初始時(shí)刻各節(jié)點(diǎn)的狀態(tài)為x(0)=(x1，…，xn)T，則各節(jié)點(diǎn)最終都收斂于空間中的某一點(diǎn):

定義拉式矩陣L=D－A，其中D=diag(d1，…，dn)為 G 的度矩陣。D 中對(duì)角元素為 di=∑j≠iaij，其他非對(duì)角元素為0，則可以將式(1)改寫為:

在最終達(dá)成一致時(shí)，由于x=αI，而LI=0，所以:

2 自舉算法理論證明

2.1 異步自舉算法

圖2 雙節(jié)點(diǎn)異步自舉過程Fig.2 Asynchronous bootstrap between two nodes

定理1 兩個(gè)節(jié)點(diǎn)利用如圖2所示的異步自舉過程，能夠產(chǎn)生而且只能產(chǎn)生唯一的中心節(jié)點(diǎn)。

證明 由于A和B的地位對(duì)等，不失一般性，假設(shè)tA0=0，tB0≥0。當(dāng) ΔxT1＞0 時(shí)，如果 0≤tB0＜ T1，由于節(jié)點(diǎn)B的自舉區(qū)間全部處于節(jié)點(diǎn)A的自舉區(qū)間，節(jié)點(diǎn)A處于自舉模式而節(jié)點(diǎn)B處于搜索模式的時(shí)長(zhǎng)為T1。在獲知節(jié)點(diǎn)A自舉后，節(jié)點(diǎn)B將不再自舉，從而使節(jié)點(diǎn)A成為中心節(jié)點(diǎn)。如果T1≤tB0，則節(jié)點(diǎn)B從tB0開始的搜索區(qū)間即可搜索到節(jié)點(diǎn)A發(fā)出的自舉消息，并不再自舉，從而A成為中心節(jié)點(diǎn)。當(dāng)ΔxT1＜0即ΔxT1≤－T1時(shí)，如果0≤tB0＜T1，且 T1≤t≤T1+tB0內(nèi)節(jié)點(diǎn) B 能夠搜索到節(jié)點(diǎn)A的自舉消息，則A成為中心節(jié)點(diǎn)。如果節(jié)點(diǎn)A在自舉失敗后，則能夠有大于T1長(zhǎng)度的區(qū)間搜索來自節(jié)點(diǎn)B的自舉消息，從而將節(jié)點(diǎn)B選舉為中心節(jié)點(diǎn)。如果T1≤tB0，則節(jié)點(diǎn)B從初始時(shí)刻起就有等于T1長(zhǎng)度的區(qū)間搜索來自節(jié)點(diǎn)A的自舉消息，從而將節(jié)點(diǎn)A選舉為中心節(jié)點(diǎn)。由于獲得了搜索到自舉節(jié)點(diǎn)的信號(hào)后節(jié)點(diǎn)就不進(jìn)行自舉，這樣就保證了最終自舉成功的中心節(jié)點(diǎn)的唯一性，證明完畢。

推論1 當(dāng) ΔxT1≤ －T1且 tB0≥T1時(shí)，xT1較小的節(jié)點(diǎn)才被選為中心節(jié)點(diǎn)。

證明 根據(jù)上述分析可知，其他情況下，xT1較大的節(jié)點(diǎn)均可能被自舉為中心節(jié)點(diǎn)。

這也就說明，xT1較大的節(jié)點(diǎn)開始自舉的時(shí)刻晚于xT1較小的節(jié)點(diǎn)，且初始時(shí)刻的差值大于T1時(shí)，xT1較小的節(jié)點(diǎn)才可通過優(yōu)先自舉的方法使得自己必然自舉成功，成為中心節(jié)點(diǎn)。

2.2 通信約束一致性自舉算法

在帶有通信約束的情況下，不能像完全圖那樣通過一次信息交互就能獲得所有節(jié)點(diǎn)的狀態(tài)，需要通過與鄰域內(nèi)節(jié)點(diǎn)多次交互才能達(dá)成一致的自舉結(jié)果。在每一次鄰域內(nèi)的交互過程中，與完全圖中的自舉算法一樣，將自身狀態(tài)值替換為鄰域內(nèi)的最大值。如果自身狀態(tài)值本身就是最大值，則繼續(xù)在該鄰居內(nèi)自舉為中心節(jié)點(diǎn)。利用一致性算法描述自舉過程為:

為了獲得一致性自舉算法的收斂的性質(zhì)，需要定義道路和連通圖。

定義從vi到vj的一條道路為:

如果對(duì)于任意的 vi，vj∈V，都存在 W(vi，vj)，則稱該圖為連通圖。在連通圖中，定義實(shí)現(xiàn)兩點(diǎn)之間最短道路的跳數(shù)d(i，j)=m為兩點(diǎn)之間最短路徑(或距離)。連通圖中最長(zhǎng)距離定義為連通圖的半徑r=max{d(i，j)}。

連通圖具有以下一致性收斂判斷法則。

定理2 當(dāng)且僅當(dāng)無向圖為連通圖時(shí)，利用式(5)和式(6)所描述的一致性算法最終才能實(shí)現(xiàn)一致性收斂。

證明 首先證明充分性。由于通信圖為連通圖，不失一般性，假設(shè)vi，vj∈V，其中 vi為狀態(tài)最大的節(jié)點(diǎn)，即 xi=max(x1，x2，…，xn)，則對(duì)于任意的其它節(jié)點(diǎn)vj∈V，根據(jù)連通圖的定義可以找到該節(jié)點(diǎn)與vi之間的道路(7)。由于xi為最大值，通過一次迭代，便能影響其鄰域內(nèi)的所有節(jié)點(diǎn)狀態(tài)，使其狀態(tài)值變?yōu)閤i。因此，節(jié)點(diǎn) vi的狀態(tài)可沿著道路 W(vi，vj)影響節(jié)點(diǎn) v1，v2，…，vm－1，vm，vj的狀態(tài)，最終實(shí)現(xiàn)道路上所有節(jié)點(diǎn)獲得一致的狀態(tài)xi=x1=…=xm=xj。由于vi為圖中的任意節(jié)點(diǎn)，所以可推斷最終能夠使得圖中所有的節(jié)點(diǎn)獲得一致的狀態(tài)x1=x2=…=xn，即通過實(shí)現(xiàn)一致性自舉算法，可獲得收斂的自舉結(jié)果。再證明必要性。假設(shè)可一致性收斂，但不是連通圖，則存在vi，vj∈V，不能找到這兩節(jié)點(diǎn)之間的道路(7)。在此情形下，狀態(tài)值最大的節(jié)點(diǎn)vi的狀態(tài)就不能有效到達(dá)節(jié)點(diǎn)vj，最終vj的狀態(tài)xj將小于xi，這與一致性收斂的假設(shè)相矛盾，所以該圖必為連通圖，證明完畢。

推論2 假設(shè)在某連通圖半徑為r，節(jié)點(diǎn)個(gè)數(shù)為n，實(shí)現(xiàn)一致性自舉的最大迭代次數(shù)為k，則三者滿足關(guān)系 k≤r≤n。

證明 由于r為圖的半徑，如果令任意兩點(diǎn)間距離為d(i，j)=m，則由圖的半徑的定義可知，m≤r。最大迭代次數(shù)為從狀態(tài)值最大的節(jié)點(diǎn)到距離其最遠(yuǎn)節(jié)點(diǎn)的跳數(shù)，即道路長(zhǎng)為 k，k∈{m=d(i，j)}，所以 k≤r。同時(shí)，由于圖的半徑不大于節(jié)點(diǎn)數(shù)，即r≤n，得到k≤r≤n，得證。

3 算法仿真及結(jié)果分析

3.1 異步自舉仿真

假設(shè)M=3，則完成一次搜索需要的時(shí)長(zhǎng)2Tb(M+1)M=2Tb×12，因此可用12個(gè)離散的序列來模擬一次搜索中的發(fā)送和接收過程。對(duì)2.1節(jié)給出的異步自舉算法進(jìn)行數(shù)值模擬，驗(yàn)證算法的有效性。當(dāng)0＜tBO＜ T1、ΔxT1＞0，0 ＜ tBO＜ T1、ΔxT1＞0，tB0≥T1、ΔxT1＜0，tB0≥T1、ΔxT1＜0 時(shí)，對(duì)應(yīng)的仿真結(jié)果分別如圖3～圖6所示。

圖3 自舉仿真結(jié)果(1)Fig.3 Simulation results(1)

圖4 自舉仿真結(jié)果(2)Fig.4 Simulation results(2)

圖5 自舉仿真結(jié)果(3)Fig.5 Simulation results(3)

圖6 自舉仿真結(jié)果(4)Fig.6 Simulation results(4)

從仿真結(jié)果可以看出，對(duì)應(yīng)于定理1中所述的各種異步情況，都能選出唯一的中心節(jié)點(diǎn)。從圖5和圖6可以看出，當(dāng)tB0≥T1時(shí)，必然可以將節(jié)點(diǎn)B自舉為中心節(jié)點(diǎn)，而與ΔxT1無關(guān)。因此即便是自舉愿望不那么強(qiáng)烈，即x較小的節(jié)點(diǎn)也通過這種方式成功自舉為中心節(jié)點(diǎn)，這也就驗(yàn)證了推論1。另外，值得注意的是，推論1為充分條件，并非必要條件。因?yàn)閺膱D4可以看出，當(dāng)0＜tB0＜T1時(shí)，x較小的節(jié)點(diǎn)也有機(jī)會(huì)成為中心節(jié)點(diǎn)，這取決于圖1中所示的信道情況及tB0。如果在一次搜索中的第9個(gè)幀可以發(fā)現(xiàn)自舉節(jié)點(diǎn)，那么當(dāng)tB0＞9時(shí)，也可以實(shí)現(xiàn)節(jié)點(diǎn)A自舉為中心節(jié)點(diǎn)。

3.2 通信約束條件下一致性自舉仿真

假設(shè)n=10，帶約束的通信圖如圖7所示。從圖7可以看出，圖的半徑為 r=max{d(i，j)，i，j=1，2，…，10}=d(1，10)=6。

圖7 帶約束的通信圖Fig.7 Communication with constraints

為了驗(yàn)證定理2及推論2，通過設(shè)置圖7中各節(jié)點(diǎn)的初始狀態(tài)值，并運(yùn)行式(5)和式(6)所描述的一致性算法，通過多次迭代，實(shí)現(xiàn)全局收斂。仿真結(jié)果如圖8所示。從圖8(a)可以看出，當(dāng)初始時(shí)刻節(jié)點(diǎn)6具有最大值時(shí)，通過3步即可實(shí)現(xiàn)全局收斂，這是因?yàn)閺墓?jié)點(diǎn)6到距離其最遠(yuǎn)的節(jié)點(diǎn)1和節(jié)點(diǎn)10的跳數(shù)為3。從圖8(b)可以看出，當(dāng)初始時(shí)刻節(jié)點(diǎn)1具有最大值時(shí)，由于到距離其最遠(yuǎn)的節(jié)點(diǎn)10的跳數(shù)為6，所以需要通過6步迭代才能實(shí)現(xiàn)最終收斂。從仿真結(jié)果可以看出，收斂時(shí)間取決于狀態(tài)值最大的節(jié)點(diǎn)在圖中位置的分布，并且收斂上界滿足k≤r≤n。

圖8 帶通信約束的一致性自舉算法仿真結(jié)果Fig.8 Simulation results of consistency bootstrap algorithm with communication constraints

4 結(jié)束語

本文對(duì)泛在網(wǎng)絡(luò)協(xié)同過程的中心節(jié)點(diǎn)自舉算法進(jìn)行了研究。針對(duì)無中心網(wǎng)絡(luò)自舉產(chǎn)生中心節(jié)點(diǎn)過程中所面臨的時(shí)鐘不同步和通信約束問題，提出了異步自舉算法和帶通信約束的一致性自舉算法，并證明了算法的有效性和收斂性。在異步自舉算法中，自舉愿望較小的節(jié)點(diǎn)通過較早的自舉成為中心節(jié)點(diǎn)，保證了各節(jié)點(diǎn)都具有成為中心節(jié)點(diǎn)的可能性。本文還給出了一致性自舉算法中收斂時(shí)間的上界，不僅與網(wǎng)絡(luò)規(guī)模有關(guān)，還與潛在中心節(jié)點(diǎn)在網(wǎng)絡(luò)中所處的位置有關(guān)。不同的位置決定其到達(dá)距離最遠(yuǎn)的點(diǎn)的距離不同，收斂所需時(shí)間也不同。下一步工作將以本文研究結(jié)果為基礎(chǔ)，對(duì)結(jié)合通信約束的異步自舉算法進(jìn)行深入研究。

［1］Song W C，Rehman S U，Lee K J，et al.Active PDP discovery for the policy based MANET management［J］.IEICE Transactions on Communication，2009，E92B(3):1027 －1030.

［2］Gao Z，Wang L，Yang M，et al.FNMGSDP:an optimized groupbased service discovery protocol for MANETs［J］.Wireless Personal Communications，2011，57(2):137 －162.

［3］Skjegstad M，Johnsen F T，Nordmoen J.An emulated test framework for service discovery and MANET research based on ns-3［C］//New Technologies，Mobility and Security(NTMS)，the 5thInternational Conference，2012:1 －5.

［4］Hwang C，Talipov E，Cha H.Distributed geographic service discovery for mobile sensor networks［J］.Computer Networks，2011，55(5):1069 －1082.

［5］Zhou X，Ge Y，Chen X，et al.SMF:A novel lightweight reliable service discovery approach in MANET［C］//Wireless Communications，Networking and Mobile Computing(WiCOM)，the 7thInternational Conference，2011:1 －5.

［6］Christopher N V，George C P.A routing layer based approach for energy efficient service discovery in mobile ad hoc networks［J］.Wireless Communications and Mobile Computing，2009，9(5):655 －672.

［7］Vasudevan S，Towsley D F，Goeckel D.Neighbor discovery in wireless networks and thecoupon collector’sproblem［C］//Mobile Computing and Networking(MOBICOM)，the 15thACM International Conference，2009:181 －192.

［8］Arachchige C J L，Venkatesan S，Mittal N.An asynchronous neighbor discovery algorithm for cognitive radio networks［C］//New Frontiers in Dynamic Spectrum Access Networks(DySPAN)，the 3rdIEEE Symposium，2008:704 －708.

［9］Martinez S，Cortes J，Bullo F.Motion coordination with distribution information［J］.IEEE Control Systems Magazine，2007，27(4):75 －88.

［10］Olfati-saber R，F(xiàn)ax J A，Murray R M.Consensus and cooperation in networked multi-agent systems［C］//Proceedings of the IEEE，2007，95(1):215－233.