基于最小覆蓋的多點中繼集及其選擇算法

陳明剛,張陸勇,劉 賀,陳 鵬

(北京郵電大學信息與通信工程學院,北京100876)

0 引言

無線網(wǎng)狀網(wǎng)(WMN)中,每個節(jié)點都可以在其他節(jié)點協(xié)助下以多跳方式與網(wǎng)絡中任何節(jié)點進行通信。由于WMN的多跳特性,傳統(tǒng)的泛洪(Flooding)廣播會占用大量的網(wǎng)絡資源。在WMN中,帶寬是寶貴的資源,有效利用帶寬,對提升網(wǎng)絡性能十分關鍵。文獻[1]提出了一種高效的廣播機制:多點中繼廣播。多點中繼廣播在保證全網(wǎng)節(jié)點都收到廣播分組的前提下,通過減少參與轉發(fā)廣播分組的節(jié)點數(shù)目來降低廣播對網(wǎng)絡的影響。同時文獻[1]證明多點中繼集的選取是一個NP完全問題,研究人員提出了不同的啟發(fā)式算法來解決這個問題。其中文獻[1]使用了一種貪婪構造算法來選取多點中繼集合。除了貪婪算法,一些現(xiàn)代的啟發(fā)式算法也被積極運用到多點中繼集的選取中來。文獻[1]使用遺傳算法來解決多點中繼集的選取問題,文獻[2]應用蟻群算法解決這個問題。

多點中繼集是多點中繼廣播機制實現(xiàn)的關鍵。目前基于圖論中最小控制集理論的多點中繼集是包含有最少1跳鄰居節(jié)點數(shù)目的集合。在WMN中,存在不同1跳鄰居節(jié)點對相同2跳鄰居節(jié)點的重疊覆蓋現(xiàn)象,導致同一個2跳鄰居節(jié)點會從不同的1跳鄰居節(jié)點接收到相同的廣播分組。這不但會造成帶寬和節(jié)點能量的浪費,甚至會引起分組碰撞,導致消息接收失敗,影響廣播的質量。但包含節(jié)點數(shù)目最少的多點中繼集并沒有考慮重疊覆蓋的影響。為了減少重疊覆蓋的影響,文章定義了一種使重疊覆蓋數(shù)最少的多點中繼集,并提出構造它的快速啟發(fā)式算法。

1 多點中繼廣播

多點中繼廣播機制通過控制參與轉發(fā)廣播分組的節(jié)點數(shù)目來減小廣播對網(wǎng)絡的影響。每個節(jié)點從它的1跳鄰居節(jié)點集合中選取一個子集來轉發(fā)廣播分組。這些被選中的1跳鄰居節(jié)點組成了這個節(jié)點的多點中繼集,這個節(jié)點自身被稱為多點中繼決策者。每個節(jié)點都維護一個多點中繼決策者集合,集合中包含當前將本節(jié)點選為多點中繼集的鄰居節(jié)點。每個節(jié)點都可以接收和處理分組,轉發(fā)來自多點中繼決策者的廣播分組,但并不能轉發(fā)來自多點中繼決策者集合以外的節(jié)點發(fā)送的廣播分組。

1.1 多點中繼集

多點中繼集是實現(xiàn)多點中繼廣播機制的關鍵。網(wǎng)絡中每個節(jié)點獨立計算自己的多點中繼集。一個節(jié)點的多點中繼集必須保證與其全部1跳鄰居節(jié)點集合具有相同的網(wǎng)絡覆蓋范圍。

一個節(jié)點的所有1跳、2跳鄰居節(jié)點以及1跳與2跳鄰居節(jié)點之間的連接關系(不考慮1跳或2跳鄰居節(jié)點內部的連接關系)組成了一個非連通偶圖,非連通偶圖由n個連通偶圖組成。從每個連通偶圖中選出節(jié)點的部分多點中繼集,那么這些部分多點中繼集的并集就是節(jié)點的多點中繼集。所以文章將主要研究節(jié)點在連通偶圖中的多點中繼集及其選擇算法。

節(jié)點S的多點中繼集(記為MPR(S)),是能夠覆蓋所有2跳鄰居節(jié)點,是具有最少節(jié)點數(shù)目的1跳鄰居節(jié)點的集合。但是由于重疊覆蓋現(xiàn)象的存在,僅僅使MPR(S)包含的1跳鄰居節(jié)點數(shù)目最少,顯然并不能使多點中繼廣播機制達到最好的效果。有效減少重疊覆蓋的數(shù)量,能使廣播對網(wǎng)絡的影響更小。所以最優(yōu)的多點中繼集是在保證覆蓋所有2跳鄰居節(jié)點的同時,使重疊覆蓋數(shù)最小的集合。

在理想情況下:

即MPR(S)中節(jié)點度的和等于2跳鄰居節(jié)點的個數(shù)。這樣既保證完全覆蓋2跳鄰居節(jié)點,又保證沒有重疊覆蓋現(xiàn)象的存在。

1.2 多點中繼集與集合覆蓋

構造2個向量 α和β,對應節(jié)點的1跳鄰居節(jié)點集合和2跳鄰居節(jié)點集合。通過 α和β,構造一個1跳鄰居節(jié)點與2跳鄰居節(jié)點之間的鄰接矩陣γ。使 γ=αT*β。在 γ中每一行代表的是一個1跳鄰居節(jié)點,每一列代表的是一個2跳鄰居節(jié)點。第i行與第j列交叉的元素nij表示1跳鄰居節(jié)點i和2跳鄰居節(jié)點j的鄰接關系。如果節(jié)點i和節(jié)點j直接相鄰,則nij=1,否則nij=0。所以 γ是一個0-1矩陣。定義,為 1 跳鄰居節(jié)點i所覆蓋的2跳鄰居節(jié)點數(shù)目。對于上面提到的2種多點中繼集合,給出如下定義:

定義1:MN_MPR(Minimum Number MPR):包含最少1跳鄰居節(jié)點數(shù)目并且覆蓋所有2跳鄰居節(jié)點的集合。

定義2:MC_MPR(Minimum Coverage MPR):累計覆蓋2跳鄰居節(jié)點數(shù)目最少并且覆蓋所有2跳鄰居節(jié)點的集合。

在 γ中,每一列代表一個2跳鄰居節(jié)點,覆蓋2跳鄰居節(jié)點j必須滿足所有2 跳鄰居節(jié)點都被覆蓋,就必須滿足:在完全覆蓋所有2跳鄰居節(jié)點的同時,要求具備最小的這顯然是對鄰接矩陣 γ的集合覆蓋問題。MC_ MPR便是集合覆蓋問題中待選擇的最小代價集,因此可以使用解決集合覆蓋問題的方法來選取MC_MPR。

2 多點中繼集選擇算法

多點中繼集選擇算法獲得的多點中繼集的質量將直接影響多點中繼廣播的效果。MC MPR的選取問題是集合覆蓋問題,集合覆蓋問題是一個NP困難問題。解決集合覆蓋問題,遺傳算法和模擬退火算法是十分優(yōu)秀的啟發(fā)式算法,但是它們要求大量的計算資源,耗費較長的時間,這在WMN中是難以應用的。在WMN中,需要一個能夠快速收斂的算法來計算節(jié)點的多點中繼集,同時由于節(jié)點的運算能力有限,要求算法的盡可能簡單,以減少節(jié)點的計算量。這樣集合覆蓋問題中基于拉格朗日松弛的漸進算法[3]需要大量的計算也無法在規(guī)定時間內完成MC_MPR的選取。貪婪算法作為一種成熟的快速啟發(fā)式算法可以在很短時間內得到一個合適的解,這保證了它能夠及時得到MC_ MPR,以保證多點中繼廣播的正常運行。結合WMN的特點,提出一種基于貪婪算法的快速啟發(fā)式算法來解決MC_MPR 的選擇問題。

2.1 多點中繼集參數(shù)定義

在描述算法前首先做相關定義:N(x)為節(jié)點x的1跳鄰居節(jié)點集合,N2(x)為節(jié)點x的2跳鄰居節(jié)點集合。I為1跳鄰居節(jié)點數(shù)目,J為2跳鄰居節(jié)點數(shù)目。ci為1跳鄰居節(jié)點i覆蓋的2跳鄰居節(jié)點數(shù)目。啟發(fā)式算法是一種逐次迭代算法,在每一次迭代過程中都會選取一個合適的1跳鄰居節(jié)點,將其從N(x)移入MPR(x),同時在N2(x)中將與選中1跳鄰居節(jié)點關聯(lián)的2跳鄰居節(jié)點刪除。N′(x)=N(x)-MPR(x)為待選1跳鄰居節(jié)點集合。uN2(x)為N2(x)中將與選中節(jié)點關聯(lián)的2跳鄰居節(jié)點刪除后,剩余未被MPR(x)覆蓋的2跳鄰居節(jié)點集合。ki為待選1跳鄰居節(jié)點即N′(x)中節(jié)點i覆蓋uN2(x)中的2跳鄰居節(jié)點數(shù)目。ki在每次迭代過程中都是變化的,在算法開始前ki=ci。

2.2 MC_MPR 選擇算法

MC_MPR選擇算法分為4個階段:

①初始化過程:完成算法所需數(shù)據(jù)的初始化工作。包括MPR(x)設置為空集,依據(jù)N2(x)初始化uN2(x),計算I,J,ci等參數(shù);

②優(yōu)選過程:由于存在某一2跳鄰居節(jié)點被特定1跳鄰居節(jié)點惟一覆蓋的現(xiàn)象。所以這個特定的1跳鄰居節(jié)點必然屬于MPR(x)。通過優(yōu)選過程,將這些特定1跳鄰居節(jié)點直接選入MPR(x)。同時從uN2(x)將與它們關聯(lián)的2跳鄰居節(jié)點刪除;

③迭代選擇:判斷uN2(x)是否為空,如果為空,說明MPR(x)已經(jīng)完全覆蓋所有2跳鄰居節(jié)點,可以進入優(yōu)化過程。如果uN2(x)非空,說明還有2跳鄰居節(jié)點沒有被覆蓋。還需繼續(xù)向MPR(x)填加合適的節(jié)點。計算N′(x)集合中每個節(jié)點的權值,比較它們的權值,從中選出權值最優(yōu)的節(jié)點加入MPR(x)中。重新進入迭代選擇過程;

④優(yōu)化過程:判斷MPR(x)是否存在冗余節(jié)點,刪除冗余節(jié)點。

2.3 權值規(guī)則

在MC_MPR 選擇算法的迭代選擇步驟中,集合的依據(jù)。權值的計算方法直接影響算法的性能。可以選取ki作為權值,在每一次迭代過程中選出當前迭代過程中對uN2(x)中2跳鄰居節(jié)點具有最大覆蓋的節(jié)點加入MPR(x)。但僅僅考慮當前迭代過程中的最大ki,無法選出合適的MC_MPR。在MC_MPR的選擇過程中,不僅需要考慮每次迭代過程中的ki,同時需要綜合考慮ci以及迭代過程造成的影響。

由上述分析可知,MC MPR的選取是一個集合覆蓋問題,在解決集合覆蓋問題時是貪婪漸進算法合適的權值計算方法。使用這樣的權值計算方能夠得到與理論值十分接近的結果。因此,采用作為 MC_MPR選擇算法中權值計算的規(guī)則。

2.4 算法性能分析

由以上MC_MPR選擇算法獲得的多點中繼集為MPR(x),定義服從MC_MPR定義的最優(yōu)解為MPR(x)*,Cmax為ci中的最大值。文獻[4]證明在使用貪婪算法解決集合覆蓋問題時有:

式中,Si為第i次迭代過程中選擇的集合,即第i次迭代過程中MC_MPR選擇算法選擇的1跳鄰居節(jié)點;為其所包含2跳鄰居節(jié)點的個數(shù);nij為相應γ矩陣中的元素;H(x)為x級調和級數(shù)。

由MC_MPR定義可知:

由式(2)經(jīng)推導可以得到:

由MC_MPR 選擇算法獲得的MC MPR解,相對于MC_MPR最優(yōu)解的近似率上界為H(Cmax)。

3 仿真結果

對MC_MPR多點中繼廣播進行仿真,并對仿真結果進行分析。為了盡可能減小網(wǎng)絡中其他因素對仿真結果的影響,特假設如下:

①無線信道為理想信道;

②節(jié)點的物理載波偵聽范圍等于接收范圍;N′(x)集合內節(jié)點的權值是選取節(jié)點進入MC_MPR

③網(wǎng)絡中僅存在廣播分組;

④對于每一個需要發(fā)送的廣播分組,需要隨機等待一個延遲時間T,然后發(fā)送;

⑤保證節(jié)點之間的連通性,不存在孤立節(jié)點。

3.1 仿真場景

在3 000 m×3 000 m的矩形區(qū)域中有200個節(jié)點,對不同節(jié)點密度的情況進行仿真。節(jié)點密度定義為:平均一個節(jié)點無線發(fā)射范圍內的鄰居節(jié)點數(shù)目。使用ns2仿真平臺,仿真環(huán)境配置如表1所示。

表1 仿真環(huán)境配置

3.2 結果分析

在多點中繼廣播過程中,參與轉發(fā)廣播分組的節(jié)點數(shù)目隨節(jié)點密度變化曲線如圖1(a)所示。

圖1 仿真結果

這個參數(shù)以相應節(jié)點密度MN_MPR的值歸一化后得到。從圖中可以看出隨著節(jié)點密度的增大,MC_MPR較MN_MPR參與轉發(fā)的節(jié)點的數(shù)目更少。在整個仿真過程中,每個節(jié)點以固定的速率發(fā)送廣播消息,所以全網(wǎng)初始化的廣播消息總量是固定的。仿真持續(xù)時間內,全網(wǎng)接收廣播分組量以MN_MPR 的值歸一化后隨節(jié)點密度變化曲線如圖1(b)所示。全網(wǎng)接收廣播分組量是網(wǎng)絡中所有節(jié)點在整個仿真過程中接收到的廣播消息分組的總和,這其中包含重復接收的廣播消息分組,這個參數(shù)反應了網(wǎng)絡中重疊覆蓋的情況。全網(wǎng)接收廣播分組越多,說明相同分組被重復接收的次數(shù)越多,網(wǎng)絡中重疊覆蓋現(xiàn)象越嚴重。從圖中可以看出,MC_ MPR可以明顯降低全網(wǎng)接收的廣播分組總數(shù),特別是在網(wǎng)絡密度較大的時候,MC_MPR 能夠較MN_MPR降低30%左右,MC_MPR能夠有效地降低廣播對全網(wǎng)的影響,提高無線資源的利用率。

廣播分組對網(wǎng)絡的實際覆蓋率隨節(jié)點密度變化的曲線如圖1(c)所示。廣播分組對網(wǎng)絡的實際覆蓋率定義為:對于一個廣播分組,網(wǎng)絡中實際接收到這個分組的節(jié)點數(shù)量與全網(wǎng)節(jié)點數(shù)量的比值。廣播的目的就是需要全網(wǎng)接收到被廣播的信息分組,所以無論使用什么方法,都需要盡可能保證廣播分組對網(wǎng)絡的實際覆蓋率盡可能等于1。從圖1(b)可以看出,無論使用MN_MPR還是MC_MPR當節(jié)點密度大于20以后廣播分組對網(wǎng)絡的實際覆蓋率都近似為1,說明它們都能完成廣播的任務。但當節(jié)點密度小于10的時候,廣播分組對網(wǎng)絡的實際覆蓋率就迅速惡化,在節(jié)點密度為4時,MC_MPR為0.7,同時MN_MPR 也僅為0.75,所以當網(wǎng)絡節(jié)點密度很小時,MPR廣播的實際覆蓋率較小。

在洪泛廣播過程中,一個廣播分組在網(wǎng)絡中的生存時間隨節(jié)點密度變化的曲線如圖1(d)所示。隨著節(jié)點密度的增加,廣播分組的生存時間也逐漸縮短。這是因為對于200個仿真節(jié)點,節(jié)點密度越大,網(wǎng)絡的實際直徑越小,需要的轉發(fā)次數(shù)越少,使廣播分組的生存時間更短。從圖中可以看出在不同節(jié)點密度條件下MC_MPR 較MN_MPR廣播分組的存活時間更短。

從仿真結果得出,使用MC_MPR可以有效提升多點中繼廣播的性能,特別在全網(wǎng)接收廣播分組量、參與轉發(fā)廣播分組節(jié)點數(shù)目和廣播分組實際生存時間這3個方面取得了很好的結果,僅僅在廣播分組實際覆蓋率這個指標上比其他權值的結果稍低,但是仍然能夠確保實際覆蓋率在0.96以上。

4 結束語

上述對多點中繼廣播,特別是多點中繼集進行了研究。在WMN多跳環(huán)境下,考慮1跳鄰居節(jié)點對相同2跳鄰居節(jié)點的重疊覆蓋現(xiàn)象,給出了一種最大限度避免重疊覆蓋的多點中繼集的定義MC_MPR ,并提出了一種快速啟發(fā)式算法來構造這種多點中繼集,對這種多點中繼集的性能進行了仿真和分析。仿真結果表明,MC MPR 能夠有效降低廣播分組在網(wǎng)絡中的存活時間,減少相同廣播分組被重復接收的次數(shù),降低廣播對網(wǎng)絡的影響,提高無線資源的利用率。

[1]CHIZARI H,HOSSEINI M,R S A.Multipoint Relay Selection Using GA[C].Kuala Lumpur:IEEE Symposium on Industrial Electronics and Applications(ISIEA 2009),2009:957-962.

[2]ZHAO X,SONG H,XIA H,et al.Using Ant Colony Algorithm for Solving Minimum MPR Set and OPENT Simulation[C].Nanjing:The1st International Conference on Information Science and Engineering(ICISE 2009),2009:3898-3901.

[3]CAPR ARA A,FISCHETTI M,TOTH P.A Heuristic Method for the Set Covering Problem[J].Operations Research,1999(47):730-743.

[4]HOCHBAUM D S.Approximation Algorithms for NP-hard Problems[M].Boston:PWS publishing company,1996:452-456.