樓巧巧 趙知勁,2

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

0 引 言

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

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

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

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

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

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

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

1.1 廣播成功率

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

以單跳為例，說明廣播成功條件。發(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 廣播成功舉例

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

1.2 廣播時延

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

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

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

(1)

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

1.3 廣播沖突

本文考慮的廣播沖突發(fā)生條件如圖2所示。在中繼節(jié)點v1發(fā)送廣播消息給接收節(jié)點v3時，若同時有中繼節(jié)點v2接收到廣播消息也要發(fā)給v3，則當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 綜合評價函數

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

(2)

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

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

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

2.1 廣播序列構建

圖4 廣播序列構建

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

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

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

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

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

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

(3)

2.3 廣播算法

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

1) 計算ws、wr和Palter；

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

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

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

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

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

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

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

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

2.4 廣播沖突概率推導

本節(jié)分析上述算法的廣播沖突概率。如圖2所示，假設v1和v2是中繼節(jié)點，v3是接收節(jié)點。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)

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

(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ā)生廣播沖突的概率越低。為了證明上述推導和分析的正確性，以w(此時假設ws(v1)=ws(v2)=ws(v3)=wr(v3)=w)為自變量，對單個節(jié)點發(fā)生廣播沖突概率進行仿真并與理論推導結果相對比，結果如圖5所示。

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

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

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

(10)

式中：N為網絡中的節(jié)點數目。

3 算法仿真與性能分析

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

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

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

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

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

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

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

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

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

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

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

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

3.2 信道數對算法性能影響

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

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

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

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

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

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

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

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

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

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

4 結 語

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