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

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

0 引言

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

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

1 多點(diǎn)中繼廣播

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

1.1 多點(diǎn)中繼集

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

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

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

在理想情況下:

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

1.2 多點(diǎn)中繼集與集合覆蓋

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

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

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

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

2 多點(diǎn)中繼集選擇算法

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

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

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

2.2 MC_MPR 選擇算法

MC_MPR選擇算法分為4個(gè)階段:

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

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

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

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

2.3 權(quán)值規(guī)則

在MC_MPR 選擇算法的迭代選擇步驟中,集合的依據(jù)。權(quán)值的計(jì)算方法直接影響算法的性能?？梢赃x取ki作為權(quán)值,在每一次迭代過(guò)程中選出當(dāng)前迭代過(guò)程中對(duì)uN2(x)中2跳鄰居節(jié)點(diǎn)具有最大覆蓋的節(jié)點(diǎn)加入MPR(x)。但僅僅考慮當(dāng)前迭代過(guò)程中的最大ki,無(wú)法選出合適的MC_MPR。在MC_MPR的選擇過(guò)程中,不僅需要考慮每次迭代過(guò)程中的ki,同時(shí)需要綜合考慮ci以及迭代過(guò)程造成的影響。

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

2.4 算法性能分析

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

式中,Si為第i次迭代過(guò)程中選擇的集合,即第i次迭代過(guò)程中MC_MPR選擇算法選擇的1跳鄰居節(jié)點(diǎn);為其所包含2跳鄰居節(jié)點(diǎn)的個(gè)數(shù);nij為相應(yīng)γ矩陣中的元素;H(x)為x級(jí)調(diào)和級(jí)數(shù)。

由MC_MPR定義可知:

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

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

3 仿真結(jié)果

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

①無(wú)線信道為理想信道;

②節(jié)點(diǎn)的物理載波偵聽(tīng)范圍等于接收范圍;N′(x)集合內(nèi)節(jié)點(diǎn)的權(quán)值是選取節(jié)點(diǎn)進(jìn)入MC_MPR

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

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

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

3.1 仿真場(chǎng)景

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

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

3.2 結(jié)果分析

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

圖1 仿真結(jié)果

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

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

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

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

4 結(jié)束語(yǔ)

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

[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.