基于中繼節點的多跳CR Ad Hoc網絡廣播算法

樓巧巧 趙知勁,2

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

0 引 言

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

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

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

1 系統模型與性能指標

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

表1 算法設計中使用的符號

本文中評估CR Ad Hoc網絡廣播算法性能的四個主要指標是：廣播成功率、廣播時延、廣播沖突和節點轉發率。

1.1 廣播成功率

廣播成功代表源節點成功發現目的節點。然而，每個SU的傳輸范圍有限，目的節點不一定在源節點的傳輸范圍內。因此，需要進行多跳廣播。

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

圖1 廣播成功舉例

當接收節點第一次接收到廣播消息時，以概率1作為中繼節點進行轉發可以保證100%的廣播成功率，但會造成大量的廣播時延和廣播沖突。因此，為了節約網絡資源，中繼節點的選擇尤為關鍵。

1.2 廣播時延

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

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

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

(1)

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

1.3 廣播沖突

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

圖2 廣播沖突發生條件

如圖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上同時接收到中繼節點v1和v2的廣播消息，從而造成廣播沖突。

圖3 廣播沖突舉例

1.4 綜合評價函數

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

(2)

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

2 基于中繼節點選擇的廣播算法

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

2.1 廣播序列構建

圖4 廣播序列構建

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

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

2.2 中繼節點選擇與調度

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

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

根據網絡中每個節點的鄰居情況，節點vi的轉發概率[7]為：

(3)

2.3 廣播算法

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

1) 計算ws、wr和Palter；

2) 確定源節點和目的節點；

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

4) 判斷中繼節點間有無下一跳公共節點，若有，為中繼節點生成對應隨機數；

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

6) 發送節點構建廣播序列并廣播，接收節點構建廣播序列并監聽；

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

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

9) 判斷是否為中繼節點，若是，轉3)，否則不轉發。

2.4 廣播沖突概率推導

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

(4)

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

(5)

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

(6)

因此，接收節點v3在時隙k第一次出現公共信道的概率為：

(7)

在接收節點v3的每個時隙上發生廣播沖突的概率為：

(8)

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

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

(9)

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

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

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

因此，由單個節點擴展到整個網絡，發生廣播沖突的平均概率為：

(10)

式中：N為網絡中的節點數目。

3 算法仿真與性能分析

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

3.1 節點數對算法性能影響

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

圖7 不同節點數下的廣播時延比較

圖8 不同節點數下的廣播沖突概率比較

圖9 不同節點數下的節點轉發率比較

圖10 不同節點數下的綜合評價函數比較

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

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

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

由圖9可知，本文廣播算法的節點轉發率最低，MDSBA的節點轉發率最高；隨著節點數的增大，三種算法的轉發率先增大，后下降，本文算法增大最慢下降最快，MDSBA增大最快下降最慢。MDSBA以較大的節點轉發率為代價，取得較好的廣播成功率和廣播時延，但網絡中轉發節點過多會增加網絡開銷，并可能導致廣播風暴，大大影響網絡和廣播性能。

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

3.2 信道數對算法性能影響

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

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

圖12 不同信道數下的廣播時延比較

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

圖14 不同信道數下的節點轉發率比較

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

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

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

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

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

4 結 語

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