黃慶東, 郭 歡, 曹麗霞
(西安郵電大學 通信與信息工程學院, 陜西 西安 710121)
Ad hoc網(wǎng)絡(luò)是一種典型的無線自組織網(wǎng)絡(luò),其拓撲路由管理和維護十分復(fù)雜但又至關(guān)重要[1-3]。連通支配集(connected dominating set,CDS)是構(gòu)建虛擬骨干網(wǎng)的一種方式[4],能簡化網(wǎng)絡(luò)拓撲結(jié)構(gòu),快速開展路由,減少通信開銷[5-6]。通過連通支配集算法實現(xiàn)網(wǎng)絡(luò)高效管理,廣受關(guān)注。
基于層次圖的連通支配集算法[7],結(jié)合貪心策略,可快速構(gòu)建支配集,但簡化拓撲效果并不明顯。剪枝的連通支配集算法(2Rules-CDS算法)利用兩種縮減規(guī)則改善拓撲結(jié)構(gòu)[8],其進一步改進(3Rules-CDS算法)[9],可使所得CDS規(guī)模最優(yōu),且能解決生成連通支配集時存在的完全NP難問題。不過,這些算法局限于網(wǎng)絡(luò)單一影響因素,以生成最小連通支配集為目的,忽略了全網(wǎng)負載均衡性。
為改善最小連通支配集負載不均衡問題,本文擬結(jié)合加權(quán)方式[10]和網(wǎng)絡(luò)中心性[11],給出一種基于中心性加權(quán)的連通支配集算法。融合多中心性計算網(wǎng)絡(luò)節(jié)點的權(quán)值,選取最大者為支配節(jié)點,再選其一跳鄰居中鏈路多者為支配鄰居,分布式完成支配集構(gòu)建,并對支配集的連通性進行判斷和維護。
Ad hoc網(wǎng)絡(luò)模型可簡單抽象為圖論中無向連通圖G=(V,E),V是G的頂點集,表示網(wǎng)絡(luò)中的節(jié)點集(包含|V|=K個元素),E是G的邊集,表示節(jié)點之間能直接通信的鏈路集。圖譜論中表征節(jié)點連接關(guān)系的鄰接矩陣定義為A=[akq]K×K,若節(jié)點k與節(jié)點q相連(q∈Nk,Nk表示節(jié)點k的鄰居開集),則元素akq=1,反之a(chǎn)kq=0。
連通支配集,指網(wǎng)絡(luò)中一個連通的子網(wǎng)。網(wǎng)絡(luò)任一節(jié)點存在兩種狀態(tài),或者在這個子網(wǎng)中,或者與這個子網(wǎng)中的節(jié)點相鄰。在Ad hoc網(wǎng)絡(luò)中,連通支配集被廣泛用于構(gòu)建虛擬骨干網(wǎng),其支配節(jié)點長期處于消息處理和轉(zhuǎn)發(fā)的工作狀態(tài),而支配鄰居則定期進入休眠狀態(tài),能耗遠大于被支配節(jié)點。選擇性能優(yōu)良的節(jié)點充當支配節(jié)點對于更好地管控整個網(wǎng)絡(luò)非常關(guān)鍵。基于網(wǎng)絡(luò)拓撲理論,考慮以下影響因素。
(1) 度中心性
節(jié)點的度是指其周圍鄰居節(jié)點的個數(shù)。節(jié)點的度體現(xiàn)了節(jié)點在網(wǎng)絡(luò)中的局部位置特性。選取度較大的節(jié)點作為支配節(jié)點,可獲得較小支配集。由于支配節(jié)點比其他節(jié)點承擔更多通信任務(wù),支配鄰居過多易導(dǎo)致支配節(jié)點負載過重而出現(xiàn)信息擁堵,使負載不均衡而降低網(wǎng)絡(luò)壽命,因此,度中心性(degree centrality,DC)是影響支配節(jié)點選取的重要因素[11]。定義節(jié)點k的度中心性為
cD(k)=|Nk|。
(1)
其中,|Nk|表示節(jié)點k一跳范圍內(nèi)的鄰居數(shù)。
(2) 特征矢量中心性
某節(jié)點的鄰居節(jié)點越多,且各鄰居節(jié)點所連接的鄰居節(jié)點越多,則該節(jié)點的影響力越大,其特征矢量中心性(eigenvector centrality,EC)值越高。區(qū)別于度中心性僅考慮一跳范圍內(nèi)節(jié)點的局部影響力,特征矢量中心性旨在衡量節(jié)點對網(wǎng)絡(luò)的整體影響,可作為選取支配節(jié)點的關(guān)鍵因素[12]。節(jié)點k的中心性值cE(k)滿足
其中α為歸一化因子,akq為鄰接矩陣A的元素值,且只有在節(jié)點k和節(jié)點q存在鏈路時為1,其余為0。設(shè)C是所有節(jié)點特征矢量中心性值構(gòu)成的向量,則有向量形式
αC=AC。
(2)
可見,C為鄰接矩陣A的特征向量。
由Perron-Frobenius定理可知,矩陣A存在一個由最大特征值α對應(yīng)的最大特征向量,即特征矢量中心性向量C。
(3) 緊密中心性
緊密中心性(closeness centrality,CC)代表一個節(jié)點與網(wǎng)絡(luò)中其他節(jié)點距離的大小程度[11]。若一個節(jié)點越接近網(wǎng)絡(luò)中心位置,則該節(jié)點與其他節(jié)點距離越短,越緊密,CC值越大。根據(jù)距離因素選取網(wǎng)絡(luò)中心位置的節(jié)點作為支配節(jié)點,可使支配集更優(yōu)。定義節(jié)點k與網(wǎng)絡(luò)中其他所有節(jié)點距離的平均值dk為
其中,dkq為節(jié)點k和節(jié)點q之間的距離,K表示網(wǎng)絡(luò)的節(jié)點總數(shù)。則節(jié)點k的緊密中心性為
(3)
可見,dk越小,節(jié)點k越接近其他節(jié)點,則該節(jié)點的緊密中心性越大。
表征局部影響的度中心性、全網(wǎng)拓撲影響的特征矢量中心性、基于距離影響的緊密中心性,對網(wǎng)絡(luò)支配節(jié)點的選取產(chǎn)生不同程度的影響。通過加權(quán)方式綜合3種因素,定義節(jié)點k的中心性加權(quán)公式
W(k)=λ1cE(k)+λ2cD(k)+λ3cC(k)。
(4)
其中,λ1、λ2和λ3分別代表著各因素的相對重要性(λ1+λ2+λ3=1),哪個因素越重要,其相對的權(quán)重因子值越大。在支配集構(gòu)建過程中,優(yōu)先選擇權(quán)值W(k)大的節(jié)點為支配節(jié)點。
大多數(shù)連通支配集算法僅考慮構(gòu)建最小連通支配集,忽略了網(wǎng)絡(luò)負載均衡性。這些算法中的支配集可能會因通信任務(wù)繁重而迅速消耗自身能量,導(dǎo)致整個網(wǎng)絡(luò)隔斷。利用中心性加權(quán)公式可得出一種新的連通支配集生成算法。
步驟1以隨機的方式在一定區(qū)域范圍內(nèi)依次拋撒K個節(jié)點并編號,且標記為初始狀態(tài),形成通信半徑為r的初始化連通網(wǎng)絡(luò)拓撲。
步驟2由式(1)、式(2)、式(3)分別計算初始拓撲中所有初始節(jié)點的度中心性值、特征矢量中心性值和緊密中心性值。
步驟3根據(jù)度中心性、特征矢量中心性和緊密中心性在網(wǎng)絡(luò)中的影響程度,給權(quán)重因子分配適當數(shù)值,結(jié)合步驟2,通過式(4)計算每個初始節(jié)點的權(quán)值,并按從大到小的順序排序。
步驟4選取最大值的初始節(jié)點標記為第一個支配節(jié)點。
步驟5將其一跳范圍內(nèi)連通效果較好的節(jié)點標記為支配鄰居狀態(tài)。
步驟6再從剩余初始節(jié)點中選擇權(quán)值最大的作為下一個支配節(jié)點。
步驟7繼續(xù)執(zhí)行步驟5到步驟6,依次遍歷拓撲中所有節(jié)點。
由于Ad hoc網(wǎng)絡(luò)拓撲動態(tài)可變,為維護支配集的連通性,保證網(wǎng)絡(luò)的可靠性和穩(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é)點,構(gòu)成支配集。
步驟2由式(5)和(6)計算得到可達矩陣,并判斷該支配集是否連通:若矩陣中不包含零元素,則表示該支配集連通;否則不連通,需要從所有非支配集中選取權(quán)值最大的節(jié)點,標記為臨時連接節(jié)點,并添加到支配集中,形成新的支配集。
步驟3根據(jù)可達矩陣判斷所得支配集是否連通:若連通,則標記臨時連接節(jié)點的狀態(tài)為連接節(jié)點,選取完成;若不連通,則重新選取權(quán)值次大的節(jié)點作為臨時連接節(jié)點,以此類推。
步驟4若一個連接節(jié)點無法滿足支配集連通,則需要添加多個連接節(jié)點來維護其連通性。默認將第一個連接節(jié)點添加到支配集中,重復(fù)上述步驟進行下一連接節(jié)點選取,直至網(wǎng)絡(luò)中所有支配節(jié)點連通。
通過對生成的支配集進行連通性維護,形成由連通支配集構(gòu)建的虛擬骨干網(wǎng),可使骨干節(jié)點和非骨干節(jié)點分布更均衡,進而延長網(wǎng)絡(luò)生命周期,保障網(wǎng)絡(luò)高效地開展路由,完成節(jié)點之間數(shù)據(jù)的發(fā)送、接收和轉(zhuǎn)發(fā)。
通過引入無線通信能耗模型[14],可證實所給算法能夠延長網(wǎng)絡(luò)生命周期。
為了驗證所提算法的性能,采用MATLAB軟件平臺進行仿真研究,并與2Rules-CDS算法以及3Rules-CDS改進算法進行對比。
構(gòu)建一個隨機網(wǎng)絡(luò)拓撲圖,在歸一化二維空間隨機分布K個相同的網(wǎng)絡(luò)節(jié)點,并預(yù)置歐氏距離r。若任意兩節(jié)點間的通信距離皆小于r,則各節(jié)點間有邊相連,形成無向連通拓撲圖。應(yīng)用所給算法、2Rules-CDS算法和3Rules-CDS算法,分別取網(wǎng)絡(luò)節(jié)點為20個、30個、40個、50個和60個,各自重復(fù)實驗100次,計算產(chǎn)生的支配節(jié)點數(shù)、網(wǎng)絡(luò)負載均衡性和網(wǎng)絡(luò)中每個節(jié)點平均剩余能量,并求其平均值作為實驗結(jié)果。
當歸一化距離r=0.6時,由3種算法得到的支配集規(guī)模曲線如圖1所示。
圖1 支配節(jié)點規(guī)模對比
從中可見,隨著網(wǎng)絡(luò)節(jié)點數(shù)的增加,3種算法得到的支配節(jié)點數(shù)都有一定增長,但增長速度比網(wǎng)絡(luò)節(jié)點數(shù)的增長速度小。本文算法所得支配節(jié)點數(shù)優(yōu)于2Rules-CDS算法,而次于3Rules-CDS算法。這是因為3Rules-CDS算法以得到最小連通支配集為目的,忽略了網(wǎng)絡(luò)負載均衡性;本文算法既優(yōu)化了連通支配集規(guī)模,對負載均衡也有所改善。
定義負載均衡因子[15]
(7)
其中,n表示支配節(jié)點數(shù),μd表示支配節(jié)點d的支配鄰居數(shù),v表示各支配節(jié)點的平均鄰居節(jié)點數(shù),即
其中K表示網(wǎng)絡(luò)中節(jié)點個數(shù)。
負載均衡因子值F越大,表示網(wǎng)絡(luò)負載均衡性越優(yōu)良,即整個網(wǎng)絡(luò)的支配節(jié)點數(shù)和支配鄰居數(shù)分布更均衡,從而可延長網(wǎng)絡(luò)生命周期。
負載均衡性隨網(wǎng)絡(luò)節(jié)點數(shù)的變化趨勢如圖2所示,隨著網(wǎng)絡(luò)節(jié)點數(shù)的增加,3種算法的網(wǎng)絡(luò)負載均衡性皆呈下降趨勢。這是因為,CDS算法在節(jié)點密集部署的監(jiān)測環(huán)境中,拓撲結(jié)構(gòu)更加復(fù)雜,節(jié)點間通信鏈路增多,會造成鏈路之間互相干擾變大,使負載均衡性下降。本文算法的網(wǎng)絡(luò)負載均衡性之所以高于其他兩種算法,是因為所給算法通過度中心性、特征矢量中心性和緊密中心性三方面加權(quán)選取權(quán)值最大的節(jié)點作為支配節(jié)點,其鄰居節(jié)點中連通性好的為支配鄰居,依次迭代,完成連通支配集的構(gòu)建,使得網(wǎng)絡(luò)中支配節(jié)點數(shù)目和支配鄰居節(jié)點數(shù)目分布更合理,故能提高網(wǎng)絡(luò)負載均衡能力。
圖2 負載均衡性對比
網(wǎng)絡(luò)中各節(jié)點平均剩余能量隨網(wǎng)絡(luò)節(jié)點數(shù)的變化趨勢如圖3所示。從中可見,3種算法的各節(jié)點平均剩余能量都隨著網(wǎng)絡(luò)節(jié)點數(shù)的增加呈下降趨勢。本文算法的各節(jié)點平均剩余能量之所以優(yōu)于其余兩種算法,是因為所給算法考慮了網(wǎng)絡(luò)負載均衡因子,使得網(wǎng)絡(luò)中支配節(jié)點和支配鄰居節(jié)點分布更均衡,提高了網(wǎng)絡(luò)的負載均衡性,從而節(jié)省了網(wǎng)絡(luò)節(jié)點的能量消耗,進而延長了網(wǎng)絡(luò)生命周期。
圖3 網(wǎng)絡(luò)剩余能量對比
考慮網(wǎng)絡(luò)的度中心性、特征矢量中心性和緊密中心性這3個網(wǎng)絡(luò)影響因素,作為選取支配節(jié)點的標準,并引入連通維護策略保障網(wǎng)絡(luò)中支配集的連通性,構(gòu)建一種新的分布式連通支配集生成算法。所給算法綜合考慮節(jié)點在網(wǎng)絡(luò)中的局部、全局和物理位置方面對網(wǎng)絡(luò)負載均衡的影響因素,可有效改善利用最小連通支配集算法所建網(wǎng)絡(luò)拓撲并非具有良好負載均衡性的問題。與2Rules-CDS算法和3Rules-CDS算法相比,本文所給算法使整個網(wǎng)絡(luò)中支配節(jié)點和被支配節(jié)點分布更加均勻,明顯改善了網(wǎng)絡(luò)負載均衡性,進而延長了虛擬骨干網(wǎng)壽命。