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

黃慶東, 郭 歡, 曹麗霞

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

Ad hoc網(wǎng)絡是一種典型的無線自組織網(wǎng)絡，其拓撲路由管理和維護十分復雜但又至關重要[1-3]。連通支配集(connected dominating set，CDS)是構建虛擬骨干網(wǎng)的一種方式[4]，能簡化網(wǎng)絡拓撲結構，快速開展路由，減少通信開銷[5-6]。通過連通支配集算法實現(xiàn)網(wǎng)絡高效管理，廣受關注。

基于層次圖的連通支配集算法[7]，結合貪心策略，可快速構建支配集，但簡化拓撲效果并不明顯。剪枝的連通支配集算法(2Rules-CDS算法)利用兩種縮減規(guī)則改善拓撲結構[8]，其進一步改進(3Rules-CDS算法)[9]，可使所得CDS規(guī)模最優(yōu)，且能解決生成連通支配集時存在的完全NP難問題。不過，這些算法局限于網(wǎng)絡單一影響因素，以生成最小連通支配集為目的，忽略了全網(wǎng)負載均衡性。

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

1 網(wǎng)絡模型和加權公式

1.1 網(wǎng)絡模型

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

1.2 網(wǎng)絡中心性加權公式

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

(1) 度中心性

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

cD(k)=|Nk|。

(1)

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

(2) 特征矢量中心性

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

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

αC=AC。

(2)

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

由Perron-Frobenius定理可知，矩陣A存在一個由最大特征值α對應的最大特征向量，即特征矢量中心性向量C。

(3) 緊密中心性

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

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

(3)

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

表征局部影響的度中心性、全網(wǎng)拓撲影響的特征矢量中心性、基于距離影響的緊密中心性，對網(wǎng)絡支配節(jié)點的選取產生不同程度的影響。通過加權方式綜合3種因素，定義節(jié)點k的中心性加權公式

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

(4)

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

2 基于中心性加權的連通支配集算法

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

2.1 連通支配集算法

步驟1以隨機的方式在一定區(qū)域范圍內依次拋撒K個節(jié)點并編號，且標記為初始狀態(tài)，形成通信半徑為r的初始化連通網(wǎng)絡拓撲。

步驟2由式(1)、式(2)、式(3)分別計算初始拓撲中所有初始節(jié)點的度中心性值、特征矢量中心性值和緊密中心性值。

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

步驟4選取最大值的初始節(jié)點標記為第一個支配節(jié)點。

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

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

步驟7繼續(xù)執(zhí)行步驟5到步驟6，依次遍歷拓撲中所有節(jié)點。

2.2 支配集連通性維護

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

(5)

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

(6)

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

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

利用所得可達性矩陣對支配集的連通性進行判斷，并選取最少連接節(jié)點維護支配集連通性。

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

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

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

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

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

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

3 仿真及結果分析

為了驗證所提算法的性能，采用MATLAB軟件平臺進行仿真研究，并與2Rules-CDS算法以及3Rules-CDS改進算法進行對比。

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

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

圖1 支配節(jié)點規(guī)模對比

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

定義負載均衡因子[15]

(7)

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

其中K表示網(wǎng)絡中節(jié)點個數(shù)。

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

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

圖2 負載均衡性對比

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

圖3 網(wǎng)絡剩余能量對比

4 結語

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