基于多中心性加權(quán)的Ad hoc網(wǎng)絡(luò)連通支配集算法

黃慶東, 郭 歡, 曹麗霞

(西安郵電大學(xué) 通信與信息工程學(xué)院， 陜西 西安 710121)

Ad hoc網(wǎng)絡(luò)是一種典型的無線自組織網(wǎng)絡(luò)，其拓?fù)渎酚晒芾砗途S護(hù)十分復(fù)雜但又至關(guān)重要[1-3]。連通支配集(connected dominating set，CDS)是構(gòu)建虛擬骨干網(wǎng)的一種方式[4]，能簡(jiǎn)化網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，快速開展路由，減少通信開銷[5-6]。通過連通支配集算法實(shí)現(xiàn)網(wǎng)絡(luò)高效管理，廣受關(guān)注。

基于層次圖的連通支配集算法[7]，結(jié)合貪心策略，可快速構(gòu)建支配集，但簡(jiǎn)化拓?fù)湫Ч⒉幻黠@。剪枝的連通支配集算法(2Rules-CDS算法)利用兩種縮減規(guī)則改善拓?fù)浣Y(jié)構(gòu)[8]，其進(jìn)一步改進(jìn)(3Rules-CDS算法)[9]，可使所得CDS規(guī)模最優(yōu)，且能解決生成連通支配集時(shí)存在的完全NP難問題。不過，這些算法局限于網(wǎng)絡(luò)單一影響因素，以生成最小連通支配集為目的，忽略了全網(wǎng)負(fù)載均衡性。

為改善最小連通支配集負(fù)載不均衡問題，本文擬結(jié)合加權(quán)方式[10]和網(wǎng)絡(luò)中心性[11]，給出一種基于中心性加權(quán)的連通支配集算法。融合多中心性計(jì)算網(wǎng)絡(luò)節(jié)點(diǎn)的權(quán)值，選取最大者為支配節(jié)點(diǎn)，再選其一跳鄰居中鏈路多者為支配鄰居，分布式完成支配集構(gòu)建，并對(duì)支配集的連通性進(jìn)行判斷和維護(hù)。

1 網(wǎng)絡(luò)模型和加權(quán)公式

1.1 網(wǎng)絡(luò)模型

Ad hoc網(wǎng)絡(luò)模型可簡(jiǎn)單抽象為圖論中無向連通圖G=(V,E)，V是G的頂點(diǎn)集，表示網(wǎng)絡(luò)中的節(jié)點(diǎn)集(包含|V|=K個(gè)元素)，E是G的邊集，表示節(jié)點(diǎn)之間能直接通信的鏈路集。圖譜論中表征節(jié)點(diǎn)連接關(guān)系的鄰接矩陣定義為A=[akq]K×K，若節(jié)點(diǎn)k與節(jié)點(diǎn)q相連(q∈Nk，Nk表示節(jié)點(diǎn)k的鄰居開集)，則元素akq=1，反之a(chǎn)kq=0。

1.2 網(wǎng)絡(luò)中心性加權(quán)公式

連通支配集，指網(wǎng)絡(luò)中一個(gè)連通的子網(wǎng)。網(wǎng)絡(luò)任一節(jié)點(diǎn)存在兩種狀態(tài)，或者在這個(gè)子網(wǎng)中，或者與這個(gè)子網(wǎng)中的節(jié)點(diǎn)相鄰。在Ad hoc網(wǎng)絡(luò)中，連通支配集被廣泛用于構(gòu)建虛擬骨干網(wǎng)，其支配節(jié)點(diǎn)長(zhǎng)期處于消息處理和轉(zhuǎn)發(fā)的工作狀態(tài)，而支配鄰居則定期進(jìn)入休眠狀態(tài)，能耗遠(yuǎn)大于被支配節(jié)點(diǎn)。選擇性能優(yōu)良的節(jié)點(diǎn)充當(dāng)支配節(jié)點(diǎn)對(duì)于更好地管控整個(gè)網(wǎng)絡(luò)非常關(guān)鍵。基于網(wǎng)絡(luò)拓?fù)淅碚?，考慮以下影響因素。

(1) 度中心性

節(jié)點(diǎn)的度是指其周圍鄰居節(jié)點(diǎn)的個(gè)數(shù)。節(jié)點(diǎn)的度體現(xiàn)了節(jié)點(diǎn)在網(wǎng)絡(luò)中的局部位置特性。選取度較大的節(jié)點(diǎn)作為支配節(jié)點(diǎn)，可獲得較小支配集。由于支配節(jié)點(diǎn)比其他節(jié)點(diǎn)承擔(dān)更多通信任務(wù)，支配鄰居過多易導(dǎo)致支配節(jié)點(diǎn)負(fù)載過重而出現(xiàn)信息擁堵，使負(fù)載不均衡而降低網(wǎng)絡(luò)壽命，因此,度中心性(degree centrality，DC)是影響支配節(jié)點(diǎn)選取的重要因素[11]。定義節(jié)點(diǎn)k的度中心性為

cD(k)=|Nk|。

(1)

其中，|Nk|表示節(jié)點(diǎn)k一跳范圍內(nèi)的鄰居數(shù)。

(2) 特征矢量中心性

某節(jié)點(diǎn)的鄰居節(jié)點(diǎn)越多，且各鄰居節(jié)點(diǎn)所連接的鄰居節(jié)點(diǎn)越多，則該節(jié)點(diǎn)的影響力越大，其特征矢量中心性(eigenvector centrality，EC)值越高。區(qū)別于度中心性僅考慮一跳范圍內(nèi)節(jié)點(diǎn)的局部影響力，特征矢量中心性旨在衡量節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)的整體影響，可作為選取支配節(jié)點(diǎn)的關(guān)鍵因素[12]。節(jié)點(diǎn)k的中心性值cE(k)滿足

其中α為歸一化因子，akq為鄰接矩陣A的元素值，且只有在節(jié)點(diǎn)k和節(jié)點(diǎn)q存在鏈路時(shí)為1，其余為0。設(shè)C是所有節(jié)點(diǎn)特征矢量中心性值構(gòu)成的向量，則有向量形式

αC=AC。

(2)

可見，C為鄰接矩陣A的特征向量。

由Perron-Frobenius定理可知，矩陣A存在一個(gè)由最大特征值α對(duì)應(yīng)的最大特征向量，即特征矢量中心性向量C。

(3) 緊密中心性

緊密中心性(closeness centrality，CC)代表一個(gè)節(jié)點(diǎn)與網(wǎng)絡(luò)中其他節(jié)點(diǎn)距離的大小程度[11]。若一個(gè)節(jié)點(diǎn)越接近網(wǎng)絡(luò)中心位置，則該節(jié)點(diǎn)與其他節(jié)點(diǎn)距離越短，越緊密，CC值越大。根據(jù)距離因素選取網(wǎng)絡(luò)中心位置的節(jié)點(diǎn)作為支配節(jié)點(diǎn)，可使支配集更優(yōu)。定義節(jié)點(diǎn)k與網(wǎng)絡(luò)中其他所有節(jié)點(diǎn)距離的平均值dk為

其中，dkq為節(jié)點(diǎn)k和節(jié)點(diǎn)q之間的距離，K表示網(wǎng)絡(luò)的節(jié)點(diǎn)總數(shù)。則節(jié)點(diǎn)k的緊密中心性為

(3)

可見，dk越小，節(jié)點(diǎn)k越接近其他節(jié)點(diǎn)，則該節(jié)點(diǎn)的緊密中心性越大。

表征局部影響的度中心性、全網(wǎng)拓?fù)溆绊懙奶卣魇噶恐行男?、基于距離影響的緊密中心性，對(duì)網(wǎng)絡(luò)支配節(jié)點(diǎn)的選取產(chǎn)生不同程度的影響。通過加權(quán)方式綜合3種因素，定義節(jié)點(diǎn)k的中心性加權(quán)公式

W(k)=λ1cE(k)+λ2cD(k)+λ3cC(k)。

(4)

其中，λ1、λ2和λ3分別代表著各因素的相對(duì)重要性(λ1+λ2+λ3=1)，哪個(gè)因素越重要，其相對(duì)的權(quán)重因子值越大。在支配集構(gòu)建過程中，優(yōu)先選擇權(quán)值W(k)大的節(jié)點(diǎn)為支配節(jié)點(diǎn)。

2 基于中心性加權(quán)的連通支配集算法

大多數(shù)連通支配集算法僅考慮構(gòu)建最小連通支配集，忽略了網(wǎng)絡(luò)負(fù)載均衡性。這些算法中的支配集可能會(huì)因通信任務(wù)繁重而迅速消耗自身能量，導(dǎo)致整個(gè)網(wǎng)絡(luò)隔斷。利用中心性加權(quán)公式可得出一種新的連通支配集生成算法。

2.1 連通支配集算法

步驟1以隨機(jī)的方式在一定區(qū)域范圍內(nèi)依次拋撒K個(gè)節(jié)點(diǎn)并編號(hào)，且標(biāo)記為初始狀態(tài)，形成通信半徑為r的初始化連通網(wǎng)絡(luò)拓?fù)洹?/p>

步驟2由式(1)、式(2)、式(3)分別計(jì)算初始拓?fù)渲兴谐跏脊?jié)點(diǎn)的度中心性值、特征矢量中心性值和緊密中心性值。

步驟3根據(jù)度中心性、特征矢量中心性和緊密中心性在網(wǎng)絡(luò)中的影響程度，給權(quán)重因子分配適當(dāng)數(shù)值，結(jié)合步驟2，通過式(4)計(jì)算每個(gè)初始節(jié)點(diǎn)的權(quán)值，并按從大到小的順序排序。

步驟4選取最大值的初始節(jié)點(diǎn)標(biāo)記為第一個(gè)支配節(jié)點(diǎn)。

步驟5將其一跳范圍內(nèi)連通效果較好的節(jié)點(diǎn)標(biāo)記為支配鄰居狀態(tài)。

步驟6再從剩余初始節(jié)點(diǎn)中選擇權(quán)值最大的作為下一個(gè)支配節(jié)點(diǎn)。

步驟7繼續(xù)執(zhí)行步驟5到步驟6，依次遍歷拓?fù)渲兴泄?jié)點(diǎn)。

2.2 支配集連通性維護(hù)

由于Ad hoc網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)可變，為維護(hù)支配集的連通性，保證網(wǎng)絡(luò)的可靠性和穩(wěn)定性，有必要引入可達(dá)性矩陣[13]。

(5)

則圖G′的可達(dá)性矩陣可記為P(G′)=[pkq]n×n。根據(jù)圖G′的鄰接矩陣A(G′)計(jì)算

(6)

其中，l表示迭代次數(shù)。

將Q(G′)的非零元素改為1，而零元素不變，變換后的矩陣即為可達(dá)性矩陣。

利用所得可達(dá)性矩陣對(duì)支配集的連通性進(jìn)行判斷，并選取最少連接節(jié)點(diǎn)維護(hù)支配集連通性。

步驟1執(zhí)行連通支配集生成算法，得到n個(gè)支配節(jié)點(diǎn)，構(gòu)成支配集。

步驟2由式(5)和(6)計(jì)算得到可達(dá)矩陣，并判斷該支配集是否連通：若矩陣中不包含零元素，則表示該支配集連通；否則不連通，需要從所有非支配集中選取權(quán)值最大的節(jié)點(diǎn)，標(biāo)記為臨時(shí)連接節(jié)點(diǎn)，并添加到支配集中，形成新的支配集。

步驟3根據(jù)可達(dá)矩陣判斷所得支配集是否連通：若連通，則標(biāo)記臨時(shí)連接節(jié)點(diǎn)的狀態(tài)為連接節(jié)點(diǎn)，選取完成；若不連通，則重新選取權(quán)值次大的節(jié)點(diǎn)作為臨時(shí)連接節(jié)點(diǎn)，以此類推。

步驟4若一個(gè)連接節(jié)點(diǎn)無法滿足支配集連通，則需要添加多個(gè)連接節(jié)點(diǎn)來維護(hù)其連通性。默認(rèn)將第一個(gè)連接節(jié)點(diǎn)添加到支配集中，重復(fù)上述步驟進(jìn)行下一連接節(jié)點(diǎn)選取，直至網(wǎng)絡(luò)中所有支配節(jié)點(diǎn)連通。

通過對(duì)生成的支配集進(jìn)行連通性維護(hù)，形成由連通支配集構(gòu)建的虛擬骨干網(wǎng)，可使骨干節(jié)點(diǎn)和非骨干節(jié)點(diǎn)分布更均衡，進(jìn)而延長(zhǎng)網(wǎng)絡(luò)生命周期，保障網(wǎng)絡(luò)高效地開展路由，完成節(jié)點(diǎn)之間數(shù)據(jù)的發(fā)送、接收和轉(zhuǎn)發(fā)。

通過引入無線通信能耗模型[14]，可證實(shí)所給算法能夠延長(zhǎng)網(wǎng)絡(luò)生命周期。

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

為了驗(yàn)證所提算法的性能，采用MATLAB軟件平臺(tái)進(jìn)行仿真研究，并與2Rules-CDS算法以及3Rules-CDS改進(jìn)算法進(jìn)行對(duì)比。

構(gòu)建一個(gè)隨機(jī)網(wǎng)絡(luò)拓?fù)鋱D，在歸一化二維空間隨機(jī)分布K個(gè)相同的網(wǎng)絡(luò)節(jié)點(diǎn)，并預(yù)置歐氏距離r。若任意兩節(jié)點(diǎn)間的通信距離皆小于r，則各節(jié)點(diǎn)間有邊相連，形成無向連通拓?fù)鋱D。應(yīng)用所給算法、2Rules-CDS算法和3Rules-CDS算法，分別取網(wǎng)絡(luò)節(jié)點(diǎn)為20個(gè)、30個(gè)、40個(gè)、50個(gè)和60個(gè)，各自重復(fù)實(shí)驗(yàn)100次，計(jì)算產(chǎn)生的支配節(jié)點(diǎn)數(shù)、網(wǎng)絡(luò)負(fù)載均衡性和網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)平均剩余能量，并求其平均值作為實(shí)驗(yàn)結(jié)果。

當(dāng)歸一化距離r=0.6時(shí),由3種算法得到的支配集規(guī)模曲線如圖1所示。

圖1 支配節(jié)點(diǎn)規(guī)模對(duì)比

從中可見，隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的增加，3種算法得到的支配節(jié)點(diǎn)數(shù)都有一定增長(zhǎng)，但增長(zhǎng)速度比網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的增長(zhǎng)速度小。本文算法所得支配節(jié)點(diǎn)數(shù)優(yōu)于2Rules-CDS算法，而次于3Rules-CDS算法。這是因?yàn)?Rules-CDS算法以得到最小連通支配集為目的，忽略了網(wǎng)絡(luò)負(fù)載均衡性；本文算法既優(yōu)化了連通支配集規(guī)模，對(duì)負(fù)載均衡也有所改善。

定義負(fù)載均衡因子[15]

(7)

其中，n表示支配節(jié)點(diǎn)數(shù)，μd表示支配節(jié)點(diǎn)d的支配鄰居數(shù)，v表示各支配節(jié)點(diǎn)的平均鄰居節(jié)點(diǎn)數(shù)，即

其中K表示網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)。

負(fù)載均衡因子值F越大，表示網(wǎng)絡(luò)負(fù)載均衡性越優(yōu)良，即整個(gè)網(wǎng)絡(luò)的支配節(jié)點(diǎn)數(shù)和支配鄰居數(shù)分布更均衡，從而可延長(zhǎng)網(wǎng)絡(luò)生命周期。

負(fù)載均衡性隨網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的變化趨勢(shì)如圖2所示，隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的增加，3種算法的網(wǎng)絡(luò)負(fù)載均衡性皆呈下降趨勢(shì)。這是因?yàn)椋珻DS算法在節(jié)點(diǎn)密集部署的監(jiān)測(cè)環(huán)境中，拓?fù)浣Y(jié)構(gòu)更加復(fù)雜，節(jié)點(diǎn)間通信鏈路增多，會(huì)造成鏈路之間互相干擾變大，使負(fù)載均衡性下降。本文算法的網(wǎng)絡(luò)負(fù)載均衡性之所以高于其他兩種算法，是因?yàn)樗o算法通過度中心性、特征矢量中心性和緊密中心性三方面加權(quán)選取權(quán)值最大的節(jié)點(diǎn)作為支配節(jié)點(diǎn)，其鄰居節(jié)點(diǎn)中連通性好的為支配鄰居，依次迭代，完成連通支配集的構(gòu)建，使得網(wǎng)絡(luò)中支配節(jié)點(diǎn)數(shù)目和支配鄰居節(jié)點(diǎn)數(shù)目分布更合理，故能提高網(wǎng)絡(luò)負(fù)載均衡能力。

圖2 負(fù)載均衡性對(duì)比

網(wǎng)絡(luò)中各節(jié)點(diǎn)平均剩余能量隨網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的變化趨勢(shì)如圖3所示。從中可見，3種算法的各節(jié)點(diǎn)平均剩余能量都隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的增加呈下降趨勢(shì)。本文算法的各節(jié)點(diǎn)平均剩余能量之所以優(yōu)于其余兩種算法，是因?yàn)樗o算法考慮了網(wǎng)絡(luò)負(fù)載均衡因子，使得網(wǎng)絡(luò)中支配節(jié)點(diǎn)和支配鄰居節(jié)點(diǎn)分布更均衡，提高了網(wǎng)絡(luò)的負(fù)載均衡性，從而節(jié)省了網(wǎng)絡(luò)節(jié)點(diǎn)的能量消耗，進(jìn)而延長(zhǎng)了網(wǎng)絡(luò)生命周期。

圖3 網(wǎng)絡(luò)剩余能量對(duì)比

4 結(jié)語

考慮網(wǎng)絡(luò)的度中心性、特征矢量中心性和緊密中心性這3個(gè)網(wǎng)絡(luò)影響因素,作為選取支配節(jié)點(diǎn)的標(biāo)準(zhǔn)，并引入連通維護(hù)策略保障網(wǎng)絡(luò)中支配集的連通性，構(gòu)建一種新的分布式連通支配集生成算法。所給算法綜合考慮節(jié)點(diǎn)在網(wǎng)絡(luò)中的局部、全局和物理位置方面對(duì)網(wǎng)絡(luò)負(fù)載均衡的影響因素，可有效改善利用最小連通支配集算法所建網(wǎng)絡(luò)拓?fù)洳⒎蔷哂辛己秘?fù)載均衡性的問題。與2Rules-CDS算法和3Rules-CDS算法相比，本文所給算法使整個(gè)網(wǎng)絡(luò)中支配節(jié)點(diǎn)和被支配節(jié)點(diǎn)分布更加均勻，明顯改善了網(wǎng)絡(luò)負(fù)載均衡性，進(jìn)而延長(zhǎng)了虛擬骨干網(wǎng)壽命。