樓巧巧 趙知勁,2

1(杭州電子科技大學(xué)通信工程學(xué)院 浙江 杭州 310018) 2(中國電子科技集團第36研究所通信系統(tǒng)信息控制技術(shù)國家級重點實驗室 浙江 嘉興 314001)

0 引 言

廣播[1-3]是移動自組織(Ad Hoc)網(wǎng)絡(luò)[4]中的一個重要環(huán)節(jié)，控制節(jié)點之間的信息交換。與有基礎(chǔ)設(shè)施的廣播相比，移動Ad Hoc網(wǎng)絡(luò)的廣播更容易產(chǎn)生廣播風(fēng)暴[5]和不可靠廣播，具體表現(xiàn)為信息冗余、信道爭搶和信號沖突，嚴(yán)重影響網(wǎng)絡(luò)性能。因此，眾多學(xué)者針對移動Ad Hoc網(wǎng)絡(luò)廣播算法展開了研究。

在傳統(tǒng)Ad Hoc網(wǎng)絡(luò)中，廣播在單個或多個公共信道上進行，網(wǎng)絡(luò)中所有節(jié)點可共享公共信道。在廣播過程中，相鄰節(jié)點只要調(diào)頻到公共信道就能實現(xiàn)成功廣播。節(jié)點通過一個時隙就可以使其所有相鄰節(jié)點接收到消息，即一個時隙就是確切的單跳廣播時延。其最簡單的廣播方式是泛洪，簡單易行且有高遍及率。但在節(jié)點密集網(wǎng)絡(luò)中，每個節(jié)點都轉(zhuǎn)發(fā)會產(chǎn)生大量信息冗余，甚至產(chǎn)生廣播風(fēng)暴。為了抑制這一現(xiàn)象，陸續(xù)提出了基于概率、區(qū)域、鄰居信息的廣播算法以及混合型廣播算法?；诟怕屎蛥^(qū)域的廣播算法復(fù)雜度低，但是不能保證覆蓋率。在基于鄰居信息的廣播算法中，典型代表有多點中繼廣播算法[6]，節(jié)點從鄰居節(jié)點中選取能夠完全覆蓋該節(jié)點兩跳鄰居的節(jié)點作為中繼節(jié)點進行轉(zhuǎn)發(fā)，控制冗余效果明顯且覆蓋率高，但中繼節(jié)點選取復(fù)雜度高?；旌闲蛷V播算法有MANET中基于節(jié)點鄰居度的動態(tài)廣播抑制算法[7],用鄰居度產(chǎn)生轉(zhuǎn)發(fā)廣播的概率和時延，并根據(jù)重復(fù)廣播數(shù)動態(tài)調(diào)整，有效降低廣播冗余和沖突。

認(rèn)知無線電(CR)技術(shù)允許次用戶(SU)在時變的環(huán)境下以機會的方式利用主用戶(PU)未使用的頻段，以提高頻譜利用率?；贑R的概念，多個節(jié)點在多個可用信道上機會性地共享許可頻譜，形成認(rèn)知無線電自組織網(wǎng)絡(luò)(CR Ad Hoc)[8]。在該網(wǎng)絡(luò)中，不同的SU擁有不同的可用信道集，不存在固定用于廣播的單個或多個公共信道。CR Ad Hoc網(wǎng)絡(luò)廣播算法研究才剛剛起步。由于信道可用性不均勻且非唯一，相鄰節(jié)點成功接收消息時間未知，即單跳廣播確切時延未知。與傳統(tǒng)Ad Hoc網(wǎng)絡(luò)相比，廣播時延增大，且轉(zhuǎn)發(fā)節(jié)點過多同樣可能產(chǎn)生廣播風(fēng)暴，因此信號沖突問題也更為嚴(yán)峻。文獻[9-10]假設(shè)全局網(wǎng)絡(luò)拓?fù)浜退蠸U的可用信道信息已知，文獻[10]中還采用了整個網(wǎng)絡(luò)的公共信令信道。這些算法雖然能夠保證廣播的成功率，但是假設(shè)都過于理想化，不適用于實際場景。文獻[11-13]提出了盲信息條件下基于QoS的廣播協(xié)議。網(wǎng)絡(luò)中所有節(jié)點在可用信道子集上廣播以減少廣播時延，具有較高的廣播成功率，但是沒有考慮廣播沖突問題。文獻[14-15]在基于QoS廣播協(xié)議的基礎(chǔ)上提出了BRACER廣播協(xié)議，該協(xié)議中含有廣播沖突避免方案。但是該方案在緩解廣播沖突的同時降低了廣播成功率。文獻[16]提出基于選擇性廣播信道集的低延遲廣播算法(MDSBA)，具有較高廣播成功率，但是節(jié)點轉(zhuǎn)發(fā)率和廣播沖突概率較高，網(wǎng)絡(luò)開銷較大。對此，本文提出基于中繼節(jié)點選擇的多跳CR Ad Hoc網(wǎng)絡(luò)廣播算法，希望在保證一定廣播成功率、廣播時延和廣播沖突率的前提下，降低節(jié)點轉(zhuǎn)發(fā)率，減少網(wǎng)絡(luò)中的冗余信息，通過建立綜合評價函數(shù)進行定量分析，從而實現(xiàn)一個綜合性能較好的廣播算法。

1 系統(tǒng)模型與性能指標(biāo)

假設(shè)CR Ad Hoc網(wǎng)絡(luò)的覆蓋區(qū)域為10×10 km2，其內(nèi)均勻分布著N個SU，節(jié)點的傳輸半徑為R，共有M個信道。本文使用“源節(jié)點”表示第一個發(fā)送該消息的SU，使用“發(fā)送(中繼)節(jié)點”表示剛收到消息并將轉(zhuǎn)發(fā)該消息的SU，使用“接收節(jié)點”表示尚未收到該消息的SU，使用“目的節(jié)點”表示該消息須要傳達到的SU。算法設(shè)計中使用的符號如表1所示。

表1 算法設(shè)計中使用的符號

本文中評估CR Ad Hoc網(wǎng)絡(luò)廣播算法性能的四個主要指標(biāo)是：廣播成功率、廣播時延、廣播沖突和節(jié)點轉(zhuǎn)發(fā)率。

1.1 廣播成功率

廣播成功代表源節(jié)點成功發(fā)現(xiàn)目的節(jié)點。然而，每個SU的傳輸范圍有限，目的節(jié)點不一定在源節(jié)點的傳輸范圍內(nèi)。因此，需要進行多跳廣播。

以單跳為例，說明廣播成功條件。發(fā)送節(jié)點按一定順序在其可用信道上跳躍并廣播消息，接收節(jié)點也按一定順序在其可用信道上跳躍并監(jiān)聽。如圖1所示，發(fā)送節(jié)點的可用信道廣播序列Tx為{1,3,7,10,13,15,16,17,18,19,20,22,25}，接收節(jié)點的可用信道廣播序列Rx為{2,4,5,6,9,11,12,13,14,19,21,23,27}。在信道19上，發(fā)送節(jié)點向接收節(jié)點成功廣播消息，即單跳廣播成功。

圖1 廣播成功舉例

當(dāng)接收節(jié)點第一次接收到廣播消息時，以概率1作為中繼節(jié)點進行轉(zhuǎn)發(fā)可以保證100%的廣播成功率，但會造成大量的廣播時延和廣播沖突。因此，為了節(jié)約網(wǎng)絡(luò)資源，中繼節(jié)點的選擇尤為關(guān)鍵。

1.2 廣播時延

廣播時延是源節(jié)點將消息成功發(fā)送到目的節(jié)點所消耗的最短時間。

同樣以單跳廣播為例，假設(shè)廣播序列中每個信道占據(jù)一個時隙。如圖1所示，在k=10時隙，單跳廣播成功，則該單跳時延t=10。因此，廣播時延表達式為：

T=min(t(v0,vi)+∑t(vi,vj)+t(vj,vs))vi≠vj

(1)

式中：vi和vj為v0到vs的廣播路徑上經(jīng)過的節(jié)點。選取不同路徑上的最短時間作為廣播時延。

1.3 廣播沖突

本文考慮的廣播沖突發(fā)生條件如圖2所示。在中繼節(jié)點v1發(fā)送廣播消息給接收節(jié)點v3時，若同時有中繼節(jié)點v2接收到廣播消息也要發(fā)給v3，則當(dāng)v1、v2存在公共可用信道時，可能造成廣播沖突。

圖2 廣播沖突發(fā)生條件

如圖3所示，v1的可用信道廣播序列Tx1為{1,3,7,10,13,15,16,17,18,19,20,22,25}，v2的可用信道廣播序列Tx2為{3,5,6,7,8,10,11,15,16,19,23,24,26}，v3的可用信道廣播序列Rx為{2,4,5,6,9,11,12,13,14,19,21,23,27}。在k=10時隙，v3在信道19上同時接收到中繼節(jié)點v1和v2的廣播消息，從而造成廣播沖突。

圖3 廣播沖突舉例

1.4 綜合評價函數(shù)

對廣播成功率、廣播時延、廣播沖突和節(jié)點轉(zhuǎn)發(fā)率進行綜合考慮，廣播成功率越大越好，廣播時延、廣播沖突和節(jié)點轉(zhuǎn)發(fā)率都是越小越好。因此，本文利用非線性加權(quán)綜合法，提出綜合評價函數(shù)y如下：

(2)

式中：y越大代表廣播算法的綜合性能越好。

2 基于中繼節(jié)點選擇的廣播算法

本文提出的基于中繼節(jié)點選擇的多跳CR Ad Hoc網(wǎng)絡(luò)廣播算法由兩部分組成，分別是廣播序列構(gòu)建和中繼節(jié)點選擇與廣播調(diào)度。假設(shè)每個SU已知其所有相鄰兩跳節(jié)點的信息，并且每次廣播源節(jié)點和目的節(jié)點唯一確定。

2.1 廣播序列構(gòu)建

圖4 廣播序列構(gòu)建

由于wr(vj)=max(ws(vi),vi∈N(vj))，則ws(vi)≤wr(vj)。又因為接收節(jié)點的每個可用信道都重復(fù)wr(vj)次，在這wr(vj)個連續(xù)時隙上，發(fā)送節(jié)點的每個可用信道至少出現(xiàn)一次。

也就是說，只要發(fā)送節(jié)點和接收節(jié)點之間存在公共信道，且發(fā)送節(jié)點的廣播序列長度大于接收節(jié)點的廣播序列長度，就必然存在一個時隙發(fā)送節(jié)點和接收節(jié)點跳轉(zhuǎn)到同一信道上，保證廣播成功。

2.2 中繼節(jié)點選擇與調(diào)度

本文中繼節(jié)點的選擇主要依賴可用信道集合大小和節(jié)點的鄰居情況。

如圖2所示，如果存在具有相同子節(jié)點的多個中間節(jié)點，則選擇具有最小ws且最大轉(zhuǎn)發(fā)概率的中間節(jié)點作為中繼節(jié)點重新廣播。當(dāng)中繼節(jié)點間存在下一跳公共節(jié)點時，對相應(yīng)中繼節(jié)點執(zhí)行廣播沖突避免方案，即將可用信道集隨機左移m位，m∈[1,ws]。

根據(jù)網(wǎng)絡(luò)中每個節(jié)點的鄰居情況，節(jié)點vi的轉(zhuǎn)發(fā)概率[7]為：

(3)

2.3 廣播算法

在廣播開始之前，每個節(jié)點利用兩跳位置信息計算自己和鄰居節(jié)點的ws、wr和Palter。根據(jù)上述信息，節(jié)點確定自己鄰居節(jié)點中的中繼節(jié)點。根據(jù)有無下一跳公共節(jié)點判定中繼節(jié)點是否需要執(zhí)行廣播沖突避免方案，若需要，生成對應(yīng)隨機數(shù)。在節(jié)點廣播消息前，將中繼節(jié)點和對應(yīng)隨機數(shù)信息以及目的節(jié)點信息添加到廣播包中。隨后，節(jié)點構(gòu)建廣播序列，并按照廣播序列在各信道上跳躍廣播。未發(fā)送廣播的節(jié)點均視為接收節(jié)點。接收節(jié)點構(gòu)建廣播序列，按照廣播序列在各信道上跳躍監(jiān)聽。第一次接收到該廣播消息的接收節(jié)點通過提取廣播包判斷自己是否為中繼節(jié)點或目的節(jié)點。若是中繼節(jié)點，繼續(xù)進行下一跳中繼節(jié)點選擇與調(diào)度并將信息添加到廣播包中，隨后立即轉(zhuǎn)發(fā)。若是目的節(jié)點，則廣播結(jié)束。因此，本文算法主要步驟如下：

1) 計算ws、wr和Palter；

2) 確定源節(jié)點和目的節(jié)點；

3) 選取鄰居節(jié)點中的中繼節(jié)點；

4) 判斷中繼節(jié)點間有無下一跳公共節(jié)點，若有，為中繼節(jié)點生成對應(yīng)隨機數(shù)；

5) 將中繼節(jié)點和隨機數(shù)信息以及目的節(jié)點信息添加到廣播包中；

6) 發(fā)送節(jié)點構(gòu)建廣播序列并廣播，接收節(jié)點構(gòu)建廣播序列并監(jiān)聽；

7) 接收節(jié)點接收到廣播后提取廣播包中的信息；

8) 判斷是否為目的節(jié)點，若是，則廣播成功，否則繼續(xù)；

9) 判斷是否為中繼節(jié)點，若是，轉(zhuǎn)3)，否則不轉(zhuǎn)發(fā)。

2.4 廣播沖突概率推導(dǎo)

本節(jié)分析上述算法的廣播沖突概率。如圖2所示，假設(shè)v1和v2是中繼節(jié)點，v3是接收節(jié)點。v1、v2、v3的可用信道集的大小分別記為ws(v1)、ws(v2)、ws(v3)。將v1與v3的公共可用信道數(shù)記為x，v2與v3的公共可用信道數(shù)記為y，v1、v2、v3的公共可用信道數(shù)記為z。則v1與v3有x個公共可用信道的概率表達式為：

(4)

同理，v2與v3有y個公共可用信道的概率表達式為：

(5)

v1、v2、v3有z個公共可用信道的概率表達式為：

(6)

因此，接收節(jié)點v3在時隙k第一次出現(xiàn)公共信道的概率為：

(7)

在接收節(jié)點v3的每個時隙上發(fā)生廣播沖突的概率為：

(8)

式中：K=ws(v3)·wr(v3)；X=min(ws(v1)，ws(v3))；Y=min(ws(v2)，ws(v3))；Z=min(x，y)。

加入隨機左移，引入平均移位因子α，在接收節(jié)點v3的每個時隙上發(fā)生廣播沖突的概率為：

(9)

由式(9)可知，在接收節(jié)點v3處發(fā)生廣播沖突概率主要受α和可用信道集大小ws(v1)、ws(v2)、ws(v3)和wr(v3)的影響，并且可用信道越多，發(fā)生廣播沖突的概率越低。為了證明上述推導(dǎo)和分析的正確性，以w(此時假設(shè)ws(v1)=ws(v2)=ws(v3)=wr(v3)=w)為自變量，對單個節(jié)點發(fā)生廣播沖突概率進行仿真并與理論推導(dǎo)結(jié)果相對比，結(jié)果如圖5所示。

圖5 不同w下的仿真和理論廣播沖突概率比較

由圖5可知，單個節(jié)點的廣播沖突概率的仿真值和理論值曲線基本重合，并且廣播沖突率隨w的增大而降低，可以證明上述推導(dǎo)和分析的正確性。

因此，由單個節(jié)點擴展到整個網(wǎng)絡(luò)，發(fā)生廣播沖突的平均概率為：

(10)

式中：N為網(wǎng)絡(luò)中的節(jié)點數(shù)目。

3 算法仿真與性能分析

本節(jié)分析比較本文廣播算法、分布式廣播協(xié)議BRACER[15]和MDSBA[16]的性能。假設(shè)所有移動節(jié)點具有相同的廣播傳輸半徑，R=4.5 km，廣播過程中節(jié)點被視為靜止，節(jié)點建立并維護二跳鄰居節(jié)點的信息表。對給定的節(jié)點數(shù)N和信道數(shù)M，利用MATLAB生成50個網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，隨后對每個網(wǎng)絡(luò)分別進行1 000次仿真，得到廣播成功率、廣播時延、廣播沖突和節(jié)點轉(zhuǎn)發(fā)率。

3.1 節(jié)點數(shù)對算法性能影響

令M=35，N=5、10、15、20、25時，三種廣播算法的廣播成功率、廣播時延、廣播沖突率、節(jié)點轉(zhuǎn)發(fā)率和綜合評價函數(shù)與節(jié)點數(shù)N的關(guān)系曲線分別如圖6至圖10所示。

圖7 不同節(jié)點數(shù)下的廣播時延比較

圖8 不同節(jié)點數(shù)下的廣播沖突概率比較

圖9 不同節(jié)點數(shù)下的節(jié)點轉(zhuǎn)發(fā)率比較

圖10 不同節(jié)點數(shù)下的綜合評價函數(shù)比較

由圖6可知，隨著節(jié)點數(shù)的增大，分布式廣播協(xié)議的成功率快速下降，而本文廣播算法的成功率基本不變，明顯優(yōu)于前者，但略低于MDSBA。

由圖7可知，隨著節(jié)點數(shù)的增大，本文廣播算法和MDSBA的時延略有降低，但分布式廣播協(xié)議的時延略有增大；且本文廣播算法時延低于分布式廣播協(xié)議，但略高于MDSBA。這是由于廣播時延的大小取決于中繼節(jié)點選擇與調(diào)度算法，獲取的廣播路徑越短，單跳時延越小，廣播成功率越高，廣播消息從源節(jié)點發(fā)送到目的節(jié)點的平均耗時越小。

由圖8可知，隨著節(jié)點數(shù)的增大，三種算法的沖突概率增大；本文廣播算法的沖突概率比MDSBA的低，但比分布式廣播協(xié)議的高。根據(jù)式(10)計算得到的本文算法的理論廣播沖突概率如曲線“*”所示，與仿真結(jié)果基本一致。

由圖9可知，本文廣播算法的節(jié)點轉(zhuǎn)發(fā)率最低，MDSBA的節(jié)點轉(zhuǎn)發(fā)率最高；隨著節(jié)點數(shù)的增大，三種算法的轉(zhuǎn)發(fā)率先增大，后下降，本文算法增大最慢下降最快，MDSBA增大最快下降最慢。MDSBA以較大的節(jié)點轉(zhuǎn)發(fā)率為代價，取得較好的廣播成功率和廣播時延，但網(wǎng)絡(luò)中轉(zhuǎn)發(fā)節(jié)點過多會增加網(wǎng)絡(luò)開銷，并可能導(dǎo)致廣播風(fēng)暴，大大影響網(wǎng)絡(luò)和廣播性能。

由圖10可知，在信道數(shù)M一定，節(jié)點數(shù)N改變的情況下，本文廣播算法的綜合性能更好，并且更適用于節(jié)點密度較高的網(wǎng)絡(luò)。

3.2 信道數(shù)對算法性能影響

令N=20，M=20、25、30、35、40時，三種廣播算法的廣播成功率、廣播時延、廣播沖突、節(jié)點轉(zhuǎn)發(fā)率和綜合評價函數(shù)與M的關(guān)系曲線分別如圖11至圖15所示。

圖11 不同信道數(shù)下的廣播成功率比較

圖12 不同信道數(shù)下的廣播時延比較

圖13 不同信道數(shù)下的廣播沖突概率比較

圖14 不同信道數(shù)下的節(jié)點轉(zhuǎn)發(fā)率比較

圖15 不同信道數(shù)下的綜合評價函數(shù)比較

由圖11和圖12可知，當(dāng)信道數(shù)目改變時，本文廣播算法的廣播成功率和廣播時延性能都優(yōu)于分布式廣播協(xié)議，但略差于MDSBA。隨著信道數(shù)的增加，廣播成功率提高，廣播時延變大。廣播時延變大是因為信道數(shù)增加導(dǎo)致廣播序列長度增加。

由圖13可知，三種廣播算法的廣播沖突概率都隨信道數(shù)目的增加而略有降低。本文廣播算法的沖突概率低于MDSBA1.52%，高于分布式廣播協(xié)議1.37%。根據(jù)式(10)計算得到的本文算法的理論廣播沖突概率也與本文算法的仿真結(jié)果基本一致。

由圖14可知，本文廣播算法的節(jié)點轉(zhuǎn)發(fā)率始終低于分布式廣播協(xié)議和MDSBA，且信道數(shù)目的增加對本文算法的影響不大，而分布式廣播協(xié)議和MDSBA的節(jié)點轉(zhuǎn)發(fā)率隨信道數(shù)目增加而略有增大。同樣，MDSBA以較大的節(jié)點轉(zhuǎn)發(fā)率為代價，取得較好的廣播成功率和廣播時延，但網(wǎng)絡(luò)中轉(zhuǎn)發(fā)節(jié)點過多會增加網(wǎng)絡(luò)開銷，并可能導(dǎo)致廣播風(fēng)暴，大大影響網(wǎng)絡(luò)和廣播性能。

由圖15可知，在節(jié)點數(shù)N一定，信道數(shù)M改變的情況下，也是本文廣播算法的綜合性能最好，并且信道數(shù)的變化對于綜合性能影響不大。

4 結(jié) 語

本文利用中繼節(jié)點選擇，實現(xiàn)了多跳CR Ad Hoc網(wǎng)絡(luò)的廣播，本文廣播算法與避免沖突的分布式廣播協(xié)議相比，提高了廣播成功率，降低了廣播時延和節(jié)點轉(zhuǎn)發(fā)率；與低延遲廣播算法相比，降低了節(jié)點轉(zhuǎn)發(fā)率和緩解了廣播沖突。但是，由綜合評價函數(shù)可知，本文廣播算法的綜合性能更好。