趙學(xué)鋒，陳祥恩

(西北師范大學(xué) a. 計(jì)算機(jī)科學(xué)與工程學(xué)院；b. 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，蘭州 730070)

1 概述

支配集問題在無線網(wǎng)絡(luò)設(shè)計(jì)、社交網(wǎng)絡(luò)和Web 圖中有許多應(yīng)用和研究[1-2]。無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)中節(jié)點(diǎn)往往隨機(jī)散落在區(qū)域中，具有相同的通信半徑，常用單位圓盤圖(Unit Disk Graph,UDG)作為研究網(wǎng)絡(luò)的基本模型，所關(guān)注的問題如構(gòu)建虛擬骨干網(wǎng)、網(wǎng)絡(luò)分簇和拓?fù)淇刂频榷寂cUDG 的連通支配集(Connected Dominating Set,CDS)有關(guān)。在UDG 類拓?fù)浣Y(jié)構(gòu)上構(gòu)造最小連通支配集(Minimum Connected Dominating Set,MCDS)是NP 難題，而出于無線網(wǎng)絡(luò)中節(jié)點(diǎn)計(jì)算能力和能量消耗等因素的考慮，MCDS 算法應(yīng)具有分布式、局部化的特性。文獻(xiàn)[1]提出鄰居指定的局部化算法，從節(jié)點(diǎn)的多點(diǎn)中繼集合中選定幾個(gè)支配節(jié)點(diǎn)，這類算法得到的CDS 規(guī)模較大。在基于支配樹的MCDS 算法中，較常見的是2 階段構(gòu)造方式，即首先構(gòu)造極大獨(dú)立集，然后另外選擇一些連接點(diǎn)共同組成CDS[3-4]，文獻(xiàn)[4]給出了這類算法的近似比為7.6。文獻(xiàn)[5]將2 階段合為一個(gè)階段，在與上一輪選出的支配點(diǎn)相距2-跳的節(jié)點(diǎn)中選出新的支配點(diǎn)，并由與新舊支配點(diǎn)相距1-跳的節(jié)點(diǎn)連接，生成網(wǎng)絡(luò)的支配樹。文獻(xiàn)[6]在廣度優(yōu)先搜索樹上構(gòu)造分層的支配集，然后通過相鄰層的中間節(jié)點(diǎn)將不連通的支配點(diǎn)連接為一個(gè)支配樹，除了CDS 的大小外，還提出了以支配樹的平均跳數(shù)距離(Average Hop Distance,AHD)作為新的評(píng)價(jià)準(zhǔn)則，AHD 小，則網(wǎng)絡(luò)通信的平均代價(jià)小且更可靠。在構(gòu)造支配樹時(shí)，需要確定節(jié)點(diǎn)權(quán)值和支配點(diǎn)的連接方式，最簡單的權(quán)值是節(jié)點(diǎn)標(biāo)識(shí)[3]，但對(duì)CDS不是本質(zhì)的[1]，更多的研究以節(jié)點(diǎn)度數(shù)為主要指標(biāo)[5-6]，文獻(xiàn)[7]將節(jié)點(diǎn)局部轉(zhuǎn)發(fā)因子作為選擇支配點(diǎn)的優(yōu)先級(jí)。文獻(xiàn)[8]計(jì)算的CDS 規(guī)模較小，但該文設(shè)計(jì)的是集中式算法，而面對(duì)無線傳感器網(wǎng)絡(luò)和大數(shù)據(jù)的復(fù)雜網(wǎng)絡(luò)，利用局部信息求解問題成為新的要求[9]，集中式算法不能適應(yīng)這一要求。另外，對(duì)MCDS 的研究還延伸到一些新的問題，如文獻(xiàn)[10]要求網(wǎng)絡(luò)節(jié)點(diǎn)要被多個(gè)節(jié)點(diǎn)所支配，文獻(xiàn)[11]將分享度(Share Degree,SD)作為量化指標(biāo)選舉網(wǎng)絡(luò)的覆蓋集。以上述內(nèi)容為基礎(chǔ)，本文提出一種基于分享度的最小連通支配集求解算法。

2 符號(hào)與概念

設(shè)N(u)={v|v∈V,(u,v)∈E}是節(jié)點(diǎn)u∈V 的鄰接點(diǎn)集合；u 的度d(u)=|N(u)|；T 表示SD 算法構(gòu)造的支配樹；VT為T的節(jié)點(diǎn)集；u.prev 是u∈VT的父節(jié)點(diǎn)；h (u,v)表示網(wǎng)絡(luò)G 中u,v∈V 之間最短通信鏈路的跳數(shù)，最大的h (u,v)稱為網(wǎng)絡(luò)直徑；hT(u,v)是T 中節(jié)點(diǎn)u、節(jié)點(diǎn)v 之間唯一通信鏈路的跳數(shù)。特別地，當(dāng)u 為T 的根節(jié)點(diǎn)時(shí)，將h(u,v)和hT(u,v)分別記為h (v)和hT(v)；G 的AHD 的計(jì)算公式為：∑h (u,v)/n(n-1)，T 的AHD 為：∑hT((u,v)/|VT|(|VT|-1)，∑分別是對(duì)各自圖中的所有點(diǎn)對(duì)求和。

定義1(UDG)n 個(gè)點(diǎn)隨機(jī)均勻分布在區(qū)域[0,R]2上，2 點(diǎn)鄰接?其歐氏距離不超過r。當(dāng)R=1 時(shí)，UDG 存在臨界半徑rc，滿足πnrc2=lnn 且對(duì)r≥rc，UDG 幾乎是連通的。

定義2(SD)設(shè)節(jié)點(diǎn)v∈N(u)，即v 是u 的d(u)個(gè)鄰居中的一個(gè)成員，則v 對(duì)u 的分享度為1/d(u)?，F(xiàn)將N(u)中度數(shù)相同的節(jié)點(diǎn)歸為一類，設(shè)|{v|v∈N(u)∧d(v)=i}|=ki，稱ki/i 為u 關(guān)于度數(shù)i 的分享度。

稱fu(x)=k1x+k2x2+…+kn-1xn-1為u 的度分布，顯然fu(1)=d(u)。

稱gu(x)=k1x+k2x2/2+…+kn-1xn-1/(n-1)為u 的分享度分布。

設(shè)v 的分享度分布為：gv(x)=b1x+b2x2/2+…+bn-1xn-1/(n- 1)。若k1=b1,k1=b2,…,ki-1=bi-1，但ki＞bi，則稱gu(x)＞gv(x)。

若gu(x)＞gv(x)對(duì)?v∈{w|w∈N(u)∧s(w)=0}成立，則u為局部剩余SD 最大節(jié)點(diǎn)，稱u 是局部分享度占優(yōu)的。分享度的意義在于，gu(x)越大則鄰居點(diǎn)被支配的比例下降得越快。

節(jié)點(diǎn)u 的權(quán)值Q(u)=＜gu(x),u＞，Q(u)＞Q(v)?(gu(x)＞gv(x))∨(gu(x)=gv(x)∧u＜v)。

3 基于SD 的MCDS 求解算法

3.1 算法規(guī)則與流程

SD 算法的支配樹構(gòu)造表示一個(gè)迭代過程，記Ai為第i 次迭代后V 中所有狀態(tài)為4 的節(jié)點(diǎn)集合，即Ai={u|u∈V∧s(u)=4}。初始階段，A0={I}，一般情況下，Ai=SD(Ai-1)，i=1,2,…，若迭代進(jìn)行到Ak=?時(shí)結(jié)束，則k 為迭代復(fù)雜度。算法可形式化地描述為一個(gè)4 元組：＜G,SD,s,A0＞，其中，s 為節(jié)點(diǎn)狀態(tài)變遷，s(u)∈{0,1,2,3,4,5}。初始時(shí)只有根節(jié)點(diǎn)I 狀態(tài)為4，其余節(jié)點(diǎn)狀態(tài)為0。其中，1(支配點(diǎn))、2(連接點(diǎn))和5(退化點(diǎn))為穩(wěn)定狀態(tài)；s(u)=3 表明u 是支配點(diǎn)的子節(jié)點(diǎn)；若沒有轉(zhuǎn)到狀態(tài)2，迭代結(jié)束后維持3 狀態(tài)不變；s(u)=4，是3 狀態(tài)節(jié)點(diǎn)的子節(jié)點(diǎn)，是一個(gè)臨時(shí)狀態(tài)。算法的迭代運(yùn)行將當(dāng)前4 狀態(tài)節(jié)點(diǎn)的狀態(tài)轉(zhuǎn)為{1,3,5}中的一種。對(duì)節(jié)點(diǎn)w∈Ai，狀態(tài)變遷為4→1，表明w 在局部分享度占優(yōu)；狀態(tài)變遷為4→5，即w 的局部分享度為0；狀態(tài)變遷為4→3，表明在w 的鄰居N(w)∩Ai中新產(chǎn)生了1 態(tài)點(diǎn)u，則令w.prev=u，而N(w)中的0 態(tài)點(diǎn)隨后轉(zhuǎn)為新的4 態(tài)點(diǎn)，完成一次迭代。算法結(jié)束時(shí)狀態(tài)為1、2 的節(jié)點(diǎn)組成CDS。節(jié)點(diǎn)的狀態(tài)變遷如圖1 所示，邊上的數(shù)字表示接收的消息種類。

圖1 節(jié)點(diǎn)狀態(tài)變遷

基于分享度構(gòu)造支配樹的算法描述如下：

3.2 算法分析

在執(zhí)行While 的迭代過程中依次產(chǎn)生的4 狀態(tài)節(jié)點(diǎn)集合為A0,A1,…,Ak，現(xiàn)設(shè)相應(yīng)的1 狀態(tài)節(jié)點(diǎn)集合為D0,D1,…,Dk，顯然Di是Ai(1≤i≤k)的子集且A0=D0={I}，而D=D1∪D2∪…∪Dk={u|u∈V∧s(u)=1}為支配點(diǎn)集；C={u|u∈V∧s(u)=2}為連接點(diǎn)集。

定理1 SD 算法得到的是網(wǎng)絡(luò)的支配樹。

證明 迭代結(jié)束時(shí)Ak=?意味著G 中已無4 態(tài)點(diǎn)，也不存在0 態(tài)點(diǎn)，網(wǎng)絡(luò)節(jié)點(diǎn)的狀態(tài)為{1,2,3,5}，進(jìn)入穩(wěn)定狀態(tài)。設(shè)第次i 迭代完成時(shí)1、2 狀態(tài)節(jié)點(diǎn)組成了一個(gè)樹，設(shè)u∈Di+1，由步驟9、步驟10，u 將選擇Di與Di+1之間的一個(gè)3 態(tài)節(jié)點(diǎn)v 為唯一的父節(jié)點(diǎn)，并使s(v)=2，由于網(wǎng)絡(luò)中的每個(gè)3 態(tài)點(diǎn)都是1 態(tài)點(diǎn)的子節(jié)點(diǎn)，因此存在唯一的w∈Di，使w 為v 的父節(jié)點(diǎn)，因此，u 通過v 與w 連接，形成一個(gè)隨迭代次數(shù)增長的樹。若以根節(jié)點(diǎn)I 為0 層，則算法結(jié)束時(shí)形成一個(gè)偶層為1 態(tài)點(diǎn)，奇層由2 態(tài)點(diǎn)組成的交錯(cuò)支配樹T。T 的節(jié)點(diǎn)集VT=D∪C 為G 中MCDS 的近似解，T 的邊集ET={(u,v)|u,v∈VT∧(u=v.prev)}。

引理1 設(shè)G 是n 個(gè)節(jié)點(diǎn)的UDG，r2=arc2，參數(shù)a＞1 調(diào)節(jié)網(wǎng)絡(luò)連通性和節(jié)點(diǎn)密度。記△為G 中節(jié)點(diǎn)的最大度數(shù)，則對(duì)常數(shù)δ≥6，以1-(1/n3a)的概率，使△≤δalnn。

證明 用D(u,r)表示以u(píng)∈V 為中心r 為半徑的圓盤，則N(u)中的節(jié)點(diǎn)都分布在D(u,r)中，按照UDG 模型，G 中節(jié)點(diǎn)分布在區(qū)域[0,R]2中，當(dāng)u 接近區(qū)域邊界時(shí)，D(u,r)不會(huì)完全包含在[0,R]2中，相交部分的面積為Area{D(u,r)∩[0,R]2}＜Area{D(u,r)}=πr2。為方便分析，令D(u,r0)是另一個(gè)圓盤，滿足：r0＞r 且Area{D(u,r0)∩[0,R]2}=πr2，設(shè)D(u,r0)∩[0,R]2中的節(jié)點(diǎn)數(shù)為μ，其期望值為E[μ]=(n-1)×πr2/R2=(n-1)×alnn/n=alnn-O(1)，于是：

其中，第3 個(gè)≤依據(jù)的是文獻(xiàn)[12]的定理4.4。

網(wǎng)絡(luò)中節(jié)點(diǎn)的期望度數(shù)為alnn，引理1 說明G 中節(jié)點(diǎn)度數(shù)超出alnn 較大倍數(shù)幾乎是不可能的，因此，在下面的分析中將G 中節(jié)點(diǎn)度數(shù)看作alnn。

定理2 SD 算法的時(shí)間復(fù)雜度為O(nlnn)。

證明 控制算法運(yùn)行時(shí)間關(guān)鍵步驟是支配點(diǎn)的選舉。?u∈D，需要收集鄰居點(diǎn)v∈A∩N(u)的Q(v)=＜gv(x),v＞，并與自己的權(quán)值Q(u)=＜gu(x),v＞比較，因此，在u 上選舉的時(shí)間代價(jià)最多為O((lnn)2)，從而算法的執(zhí)行時(shí)間為O(|D|(lnn)2)。由于V 隨機(jī)分布在[0,R]2中，G 的支配集大小由[0,R]2中所能填充的半徑為r/2 的圓盤數(shù)量決定，即|D|≤1/(π(r/2)2)≤4n/lnn，因此|D|(lnn)2≤4nlnn，即結(jié)論成立。

引理2 ?u∈Di,?v∈Di-1,1≤i≤k，成立h(u)≥h(v)+1。

引理3 ?u,v∈Di,1≤i≤k，成立hT(u)=hT(v)。

定理3 ?u∈Di,1≤i≤k，成立hT(u)≤2h(u)。

證明 依歸納法證明。當(dāng)i=1 時(shí)，hT(u)=h(u)=2，符合；假設(shè)結(jié)論對(duì)i(≥2)成立，考慮i+1 的情況。?u∈Di+1，如果u.prev∈Ai-Di，則u.prev 的狀態(tài)變遷為0→4→3，則?v∈Di為u.prev 的更新后唯一的父節(jié)點(diǎn)，這時(shí)hT(u)=hT(v)+2，按照歸納假設(shè)，hT(v)≤2h(v)，所以，hT(u)≤2h(v)+2=2(h(v)+1)=2h(u)；如果u.prev 的狀態(tài)變遷為0→3，此時(shí)，hT(u)=hT(v)+2≤2h(v)+2=2h(u)-2＜2h(u)。這表明T 中從根節(jié)點(diǎn)I 開始的每條路徑長度不超過網(wǎng)絡(luò)直徑的2 倍。

4 實(shí)驗(yàn)結(jié)果與分析

本文算法用Java 語言實(shí)現(xiàn)。為驗(yàn)證其有效性，在UDG上進(jìn)行了實(shí)驗(yàn)，并與文獻(xiàn)[6]的CDS-BD-C2 算法進(jìn)行比較，以文獻(xiàn)[8]集中式算法——BCOP 算法作為MCDS 測試基準(zhǔn)。每個(gè)實(shí)驗(yàn)數(shù)據(jù)都是在隨機(jī)產(chǎn)生的100 個(gè)連通網(wǎng)絡(luò)拓?fù)鋱D上運(yùn)行結(jié)果的均值。2 組實(shí)驗(yàn)數(shù)據(jù)如下：

(1)節(jié)點(diǎn)數(shù)n 從300 開始以增量100 變化至900，區(qū)域邊長R=500 m，通信半徑r=50 m，CDS 中的點(diǎn)數(shù)隨網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的變化如圖2 所示，平均跳數(shù)距離隨節(jié)點(diǎn)數(shù)的變化如圖3 所示。隨著節(jié)點(diǎn)數(shù)的變化，本文算法的計(jì)算結(jié)果總是保持較優(yōu)。

圖2 CDS 中的點(diǎn)數(shù)隨網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的變化

(2)節(jié)點(diǎn)數(shù)n=1000，R=100 m，半徑r 以5 為步長從10 m 增加至40 m，隨著r 的增大，網(wǎng)絡(luò)密度逐漸增加。CDS中的點(diǎn)數(shù)隨網(wǎng)絡(luò)通信半徑的變化如圖4 所示，平均跳數(shù)距離(Average Hop Distance,AHD)隨網(wǎng)絡(luò)通信半徑的變化如圖5 所示，在較為稀疏的網(wǎng)絡(luò)中，本文算法有明顯的優(yōu)勢(shì)。

圖4 CDS 中的點(diǎn)數(shù)隨網(wǎng)絡(luò)通信半徑的變化

圖5 平均跳數(shù)距離隨網(wǎng)絡(luò)通信半徑的變化

上述實(shí)驗(yàn)結(jié)果中的G-AHD 表示圖G 的AHD，是任何支配樹的AHD 下界，在此作為算法比較的參照。綜合2 組實(shí)驗(yàn)的數(shù)據(jù)進(jìn)行對(duì)比分析可見，在不同的網(wǎng)絡(luò)參數(shù)下，無論是CDS 的大小還是支配樹的平均跳數(shù)距離，這2 個(gè)性能指標(biāo)上本文算法都對(duì)CDS-BD-C2 算法有所改進(jìn)，構(gòu)造的支配樹的平均跳數(shù)距離平均減少12%，得到的CDS 更接近BCOP 算法。

5 結(jié)束語

本文提出一種基于分享度求解最小連通支配集的SD 算法。從根節(jié)點(diǎn)開始迭代交替選擇支配點(diǎn)和連接點(diǎn)，支配點(diǎn)的選取主要依賴于1-跳鄰居中0 狀態(tài)節(jié)點(diǎn)分享度的比較。連接點(diǎn)將本次生成的支配點(diǎn)和上次產(chǎn)生距根節(jié)點(diǎn)近的支配點(diǎn)連通起來，使得所有選擇出的具有局部分享度占優(yōu)的節(jié)點(diǎn)恰好是連通的。算法具有分布式特點(diǎn)，由1 個(gè)階段完成構(gòu)造，避免了2 次構(gòu)造的通信開銷。在UDG 模型上分析了時(shí)間復(fù)雜度和支配樹的特性。實(shí)驗(yàn)結(jié)果表明，和現(xiàn)有構(gòu)造支配樹的分布式相比，該算法得到的CDS 點(diǎn)數(shù)較少，支配樹的平均跳數(shù)也比近期具有代表性的CDS-BD-C2 算法計(jì)算得到的值小，便于實(shí)際應(yīng)用。研究新的節(jié)點(diǎn)權(quán)值和連接方式，以網(wǎng)絡(luò)局部信息改進(jìn)MCDS 算法的性能是今后的研究重點(diǎn)。

[1]Wu Jie,Lou Wei,Dai Fei. Extended Multipoint Relays to Determine Connected Dominating Sets in MANETs[J]. IEEE Transactions on Computers,2006,55(3): 334-347.

[2]Cooper C,Klasing R,Zito M. Lower Bounds and Algorithms for Dominating Sets in Web Graphs[J]. Internet Mathematics,2005,2(2): 275-300.

[3]Wan Pengjun,Alzoubi K M,Frieder O. Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks[J]. Mobile Networks and Applications,2004,9(2):141-149.

[4]Wu Weili,Du Hongwei,Jia Xiaohua,et al. Minimum Connected Dominating Sets and Maximal Independent Sets in Unit Disk Graphs[J]. Theoretical Computer Science,2006,352(1-3): 1-7.

[5]Funke S,Kesselman A,Meyer U. A Simple Improved Distributed Algorithm for Minimum CDS in Unit Disk Graphs[J].ACM Transactions on Sensor Networks,2006,2(3): 444-453.

[6]Kim D,Wu Yiwei,Li Yingshu,et al. Constructing Minimum Connected Dominating Sets with Bounded Diameters in Wireless Networks[J]. IEEE Transactions on Parallel and Distributed System,2009,20(2): 147-157.

[7]解文斌,李 佳,鮮 明,等. 基于拓?fù)涮匦缘姆植际教摂M骨干網(wǎng)算法[J]. 軟件學(xué)報(bào),2010,21(6): 1416-1425.

[8]Butenko S,Cheng Xiuzhen,Oliveira C,et al. A New Heuristics for the Minimum Connected Dominating Set Problem on Ad Hoc Wireless Networks[C]//Proc. of Recent Developments in Cooperative Control and Optimization. New York,USA:Kluwer Academic Publisher,2004.

[9]Borgs C,Brautbar M,Chayes J,et al. The Power of Local Information in Social Networks[C]//Proc. of the 8th International Conference on Internet and Network Economics.Berlin,Germany: Springer,2012.

[10] Wang Feng,Du Hongwei,Camacho E,et al. On Positive Influence Dominating Sets in Social Networks[J]. Theoretical Computer Science,2011,412(3): 265-269.

[11] Li Shaohua,Wang Jianxin,Chen Jianer,et al. An Algorithm for Minimum Vertex Cover Based on Max-I Share Degree[J].Journal of Computers,2011,6(8): 1781-1788.

[12] Mitzenmacher M,Upfal E. Probability and Computing:Randomized Algorithms and Probabilistic Analysis[M].Cambridge,UK: Cambridge University Press,2005.