基于現場可編程邏輯門陣列的多優先級改進型載波感知多址協議在Ad Hoc網絡中的實現和性能

丁洪偉，陸旭，2，楊志軍，3，保利勇，柳虔林，4

(1.云南大學 信息學院，云南 昆明 650500；2.武警云南省總隊 昆明支隊，云南 昆明 650051；3.云南省教育廳 科學教育研究院，云南 昆明 650223；4.云南省軍區，云南 昆明 650051)

0 引言

Ad Hoc網絡的自組織性、抗毀性、抗干擾性等是軍隊實現有效通信的關鍵指標[1-2]。Ad Hoc網絡中的媒體訪問控制(MAC)層協議決定了節點接入信道的方式，對網絡的連通具有極其重要的意義[3]，而載波感知多址(CSMA)協議是MAC層被廣泛應用的隨機多址接入控制協議之一。婁思佳等[4]分析了通信干擾條件下Ad Hoc網絡的效能，證實了實施通信干擾的實踐可行性。王海濤等[5]闡述了Ad Hoc網絡面臨的可生存性問題和技術挑戰，并對可生存網絡連接和可生存通信服務進行了全面剖析。劉廣鐘等[6]改進了高速無線局域網媒體競爭接入協議，有效改善了高密度節點競爭接入無線局域網 (WLAN)的性能。周圣杰等[7]實現了基于空閑時隙、傳輸時隙和退避控制時隙的三維概率CSMA協議，但是在現場可編程邏輯門陣列(FPGA)中時序電路不能捕捉到退避策略控制時隙，該方法不能通過硬件電路系統實現。徐智等[8]實現了基于FPGA的雙優先級CSMA協議。

本文一方面改進傳統的時隙分配方法，以增加傳輸節點針對不同信道狀態的發送概率，有效改善節點接入數量較大情況下系統的吞吐量；另一方面增加多優先級控制策略，以實現針對不同用戶需求的區分服務，同時為網絡系統付費服務提供參考。

1 改進型三維概率CSMA協議模型的建立和計算機仿真

1.1 改進型三維概率CSMA協議

在未對Ad Hoc網絡中的傳輸節點設定優先級時，假設所有傳輸節點的優先級相同，均采用公平競爭的方式接入信道。改進型三維概率CSMA協議的接入控制策略為：需要發送數據包的節點首先對信道進行檢測，如果檢測到信道處于空閑、成功、碰撞狀態，則該節點分別以概率Pi、Pu、Pb決定發送數據(以概率(1-Pi)、(1-Pu)和(1-Pb)決定放棄發送)。

對改進型三維概率CSMA協議的模型作如下假設與變量定義：

1)傳輸信道無噪聲干擾，為理想狀態[9]。

2)信息分組的到達過程滿足泊松分布，傳輸信道在時間t內到達k個信息分組的概率[10-11]為

(1)

式中：w為時間t內到達的信息分組數；k為非負整數；λ為信息分組的到達率；t為仿真時長。

3)歸一化空閑時隙長度和時延長度都為a，有信息分組發送成功的時隙長度歸一化為1(1是a的整數倍)[12-13]，信息分組發生碰撞的時隙長度定義為b.

結合(1)式，推導得出改進型三維概率CSMA協議系統的吞吐量S為

(2)

式中：v=e-(b+a)Pbλ+(b+a)Pbλe-(b+a)Pbλ；x=e-(1-b)λ；y=1-e-aPiλ；z=1-(1+a)Puλe-(1+a)Puλ.

根據(2)式，對改進型三維概率CSMA協議模型在碰撞時隙長度分別為歸一化0.1、0.3、0.5、0.7、0.9條件下的吞吐量進行計算機仿真，得到如圖1所示的結果。

分析圖1可知，在硬件工藝設計允許的條件下，分配的碰撞時隙長度越短，得到的系統吞吐量越大。

1.2 改進型三維概率CSMA協議和其他接入控制協議的吞吐量比較

根據隨機多址控制協議的接入策略和(1)式，首先對傳統的P堅持CSMA協議和1堅持CSMA協議模型的吞吐量進行分析。

傳統的P堅持CSMA協議的吞吐量Stp[14]為

(3)

傳統的1堅持CSMA協議的吞吐量St1[15]為

(4)

分析(3)式和(4)式可以發現它們之間特殊的聯系：1堅持CSMA協議是P堅持CSMA協議的一種特殊形式，當概率為1時，P堅持CSMA協議就變成1堅持CSMA協議。

對兩種傳統接入控制協議的吞吐量進行仿真，得到如圖2所示的結果。

圖2 傳統接入控制協議的吞吐量比較Fig.2 Throughputs of traditional access control protocols

分析圖2可知，在1<λ<10的區間，P堅持CSMA協議的吞吐量大于1堅持CSMA協議，因此P堅持CSMA協議在λ較大的情況下表現更佳。

下面對改進的隨機多址接入控制協議模型進行分析。

圖3所示為改進型三維概率CSMA接入控制協議模型[16-17]。圖3中，箭頭表示信息分組的到達，箭頭的數目表示到達的信息分組數，U、B和I分別表示信息分組成功發送、發生碰撞和空閑3種信道狀態，Tn表示一個平均周期，1、a、b分別表示信息分組發送成功、信道空閑、發生碰撞占用的1個時隙長度。

圖3 改進后的協議模型Fig.3 Optimized protocol model

傳統的P堅持CSMA協議模型的數據分組碰撞和成功發送都為其分配歸一化為1的時隙長度；改進型P堅持CSMA協議模型將碰撞時隙長度定義為變長的b.根據圖3，再結合(1)式、(2)式、(3)式和(4)式，得到改進型P堅持CSMA協議的吞吐量Sip為

(5)

式中：xip=e-(1-b)λ；yip=1-e-aPipλ；zip=1-(1+a)λe-(1+a)λ；vip=e-(b+a)λ+(b+a)λe-(b+a)λ.

改進型二維概率CSMA協議在改進型P堅持CSMA協議的基礎上，增加對數據分組發生碰撞和成功發送兩種狀態的檢測概率Pbu.根據(1)式和(5)式，得出改進型二維概率CSMA協議的吞吐量Si2為

(6)

式中：xi2=e-(1-b)λ；yi2=1-e-aPi2λ；zi2=1-(1+a)·Pbuλe-(1+a)Pbuλ；vbu=e-(b+a)Pbuλ+(b+a)·Pbuλe-(b+a)Pbuλ.

將改進型二維概率CSMA協議的碰撞狀態檢測概率改為Pb，得到改進型三維概率CSMA的協議模型。根據改進型隨機多址接入控制協議模型和(2)式、(3)式、(4)式、(5)式和(6)式，通過計算機仿真，得到改進型三維概率CSMA協議與傳統P堅持CSMA協議、傳統1堅持CSMA協議、改進型P堅持CSMA、改進型二維概率CSMA協議的吞吐量對比，如圖4所示。

圖4 不同隨機多址模型的吞吐量對比Fig.4 Throughputs of different random multiple access models

由圖4可知：在λ<1的情況下，改進后協議模型和傳統協議模型的吞吐量基本一致，但是λ>1后，改進后協議模型的性能優于傳統協議模型，尤其改進型三維概率CSMA協議的性能明顯優于圖4中的其他4種隨機多址協議；與傳統1堅持CSMA協議吞吐量的最大值相比，改進后三維概率CSMA協議增長24.34%；當λ=7.35時，傳統1堅持CSMA協議模型的吞吐量下降為0，而改進型三維概率CSMA協議的吞吐量為0.431 8；當λ=10時，傳統P堅持CSMA協議模型的吞吐量也下降為0，而改進型三維概率CSMA協議的吞吐量為0.330 8.

2 多優先級改進型三維概率CSMA協議的數學模型建立

針對Ad Hoc網絡中的MAC層不同接入業務具有不同傳輸要求的特點，設計多優先級接入控制模型，以滿足不同傳輸需求。考慮到不同業務的收費不一，繳納費用越高的用戶，對傳輸質量要求越高，傳輸內容可能也越多，因此優先級也可以為收費標準的制作提供參考。本文針對不同優先級的傳輸節點，設置優先級1～N，發送數據的信道為N條。通過采用優先級越高的節點占用的信道數越多的控制方案，達到有效利用有限信道資源的目的。圖5所示為優先級和信道數皆為N的多優先級信道負載均衡接入控制模型。

圖5 多優先級接入控制模型Fig.5 Multi-priority access control model

由圖5可知，優先級從低到高依次為優先級1，優先級2，…，優先級N.優先級越高，占用的信道資源也越多，處于優先級N的節點占用信道1～信道N.因此，優先級節點為y的節點在通道x上的到達率[18-21]為

(7)

式中：Gx為信道x的容量。

考慮到信道的負載均衡，每條信道的容量是有限的并且是一致的。在對多優先級改進型三維概率CSMA接入控制協議進行分析前，對如下變量進行定義：

1) 傳輸節點的優先級總數和總的信道數量都為N.

2) 由于信道負載均衡，信道容量為Gx=G(x=1，2，3，…，N)。

3) 優先級為y的節點在無線信道x上的到達率為λy.

4)KUi、KIi和KBi分別表示信道i中的成功事件、空閑事件和碰撞事件的平均數目；E(Ui)、E(Ii)和E(Bi)分別表示信道i中的成功事件、空閑事件和碰撞事件的占用時隙平均長度；Sy表示優先級為y的節點吞吐量；SN表示多優先級改進型三維概率CSMA接入控制協議的系統吞吐量。

Ad Hoc網絡中MAC層的N優先級改進型三維概率CSMA接入控制協議的吞吐量[18-21]為

(8)

多優先級改進型三維概率CSMA協議系統優先級為y的節點吞吐量[18-21]為

(9)

對三優先級系統吞吐量進行計算機仿真，得到如圖6所示的結果。

圖6 多優先級模型的系統吞吐量Fig.6 System throughput of multi-priority model

分析圖6可知：傳輸節點的優先級越高，吞吐量越高。根據(7)式可以得到優先級為1、2和3的節點分別占據一條信道容量的1/3、5/6和11/6.圖6中沒有設定優先級的節點吞吐量大于優先級1和優先級2，但是明顯小于優先級3，該結論與理論值剛好吻合，同時三優先級改進型三維概率CSMA協議系統的吞吐量是沒有設定優先級的3倍，亦與信道均衡的原理相符，從而證明了本文模型的合理性。

3 基于FPGA的多優先級改進型三維概率CSMA協議實現

FPGA應用于硬件電路設計有許多優勢，通過FPGA的設計能夠實現異步傳輸；部分功能模塊可以通過編程實現，縮短開發周期；電路系統是分模塊設計，對部分功能做出調整時無需改變電路全局。

根據理論分析，在進行多優先級改進型三維概率CSMA協議的硬件設計時，有4方面需要重點改進：重新對信道狀態進行定義和分類；調整時隙分配的策略；針對不同信道狀態設定不同的發送概率；添加多優先級模塊，使信道資源得到更加合理地利用。多優先級改進型三維概率CSMA協議的硬件實現模塊分為數據源模塊、信道狀檢測分類模塊、時隙分配模塊、多優先級模塊和數據接收統計模塊。系統設計模型如圖7所示。

圖7 硬件實現的系統圖Fig.7 System diagram of hardware implementation

若無特殊說明，硬件設計均采用以下參數。分別設定碰撞時隙長度b=0.5，檢測概率Pi=0.9、Pu=0.8、Pb=0.5.下面對各個硬件功能模塊進行逐一介紹。

1)數據源模塊。數據源模塊模擬了信息分組的到達過程，該模塊通過Quartus Ⅱ中的只讀存儲器(ROM)和計數器讀取MATLAB軟件產生的泊松數據。圖8中，INPUT表示數據源模塊的輸入；count5000為計數器；VCC表示接入電路電壓，是系統的電源端；ROM1表示ROM模塊；address[15..0]是計數器count5000的輸出和ROM模塊存取的控制端；clock為ROM模塊的時鐘控制信號；Block type:AUTO表明ROM的類型為自動；q[3..0]表示ROM讀取數據的輸出；OUTPUT為數據源模塊的輸出。MATLAB軟件提供的泊松數據源能夠更好地保證信號源隨機性原則，為后續驗證系統的正確性提供保證[8]。

圖8 數據源模塊的硬件實現Fig.8 Hardware implementation of data source module

2)信道狀態檢測和分類模塊。在總線結構中，通過檢測當前的信道狀態為節點確定發送概率提供參考條件，采用不同的二進制數值代表檢測出的信道狀態[8](沒有數據包發送用“00010001”(即十進制的17)表示；只有一個數據包發送用“00010010”(即十進制的18)表示；超過一個數據包發送用“00010011”(即十進制的19)表示)。具體的FPGA設計如圖9所示。圖9中，g[7..0]表示狀態檢測的輸出；gc[3..0]表示節點發送的信息分組數；s1表示信號源模塊；div8是八分頻模塊，通過八分頻實現一個字節八位的時鐘控制；CT表示信道的檢測分類模塊。

圖9 信道狀態檢測和分類模塊Fig.9 Channel state detection and classification module

對信道狀態檢測和分類模塊的硬件實現進行驗證，結果如圖10所示。

圖10 信道狀態檢測和分類模塊仿真結果圖Fig.10 Simulated results of channel state detection and classification module

圖10中，clk為系統的時鐘控制信號；rst為復位信號；g表示檢測到的信道狀態，gc表示節點發送的信息分組。節點發送的信息分組數分別為0、1、2、3、1、0、1、2、1，檢測到的信道狀態分別為17、18、19、19、18、17、18、19、18.節點發送信息分組數和檢測到信道狀態完全吻合，表明該模塊設計的正確性。

3)時隙分配模塊。進行該模塊的硬件設計時，根據理論模型的時隙分配方法，為碰撞狀態分配歸一化為0.5的時隙長度；為成功狀態分配歸一化為1的時隙長度，為空閑狀態分配歸一化為0.1的時隙長度。通過異步先入先出(FIFO)在不同時鐘控制下完成數據的讀寫，反饋控制模塊control針對信道的實時狀態完成時隙分配并將分配情況反饋到異步FIFO.FPGA設計如圖11所示。圖11中，data[7..0]表示未進行時隙控制的輸出；site1表示反饋控制信號；q[7..0]表示完成時隙控制的輸出；Switch1是完成狀態檢測分類的集成模塊；FIFO為異步FIFO，control為反饋控制模塊。

圖11 時隙分配模塊的硬件實現Fig.11 Hardware implementation of slot allocation module

對時隙分配模塊的硬件實現進行驗證，結果如圖12所示。

圖12 時隙分配模塊的硬件實現仿真結果Fig.12 Simulated results of hardware implementation of slot allocation module

圖12中，ena為時隙控制的使能端；q表示通過反饋控制模塊control后的輸出，data表示沒有進行時隙控制情況下的輸出。

從圖12中可以看出：17作為信道的空閑狀態時，反饋前后的時隙長度一致；18作為數據包成功發送的狀態，被延長為10倍；19作為數據包發生碰撞的狀態，被延長為5倍。驗證結果和理論分析完全一致，表明該模塊設計的正確性。

4)多優先級模塊。該模塊為不同發送節點提供不同的帶寬，優先級越高，獲得的帶寬越寬，發送的數據量越大。FPGA設計如圖13所示。圖13中，P1、P2和P3分別表示優先級為1、2和3的傳輸節點發送信息分組情況。

圖13 多優先級模塊的硬件實現Fig.13 Hardware implementation of multi-priority module

5)數據接收統計模塊。在進行該模塊設計時，為了確保接收的數據準確性，必須保證接收時鐘和時隙分配時鐘一致。FPGA設計如圖14所示。

圖14中，CH1模塊表示信道1中傳輸的數據，statiscs1模塊用以實現對信道1中數據的接收、統計。

圖14 接收情況統計模塊的硬件實現Fig.14 Hardware implementation of receiving statistics module

4 系統性能分析

4.1 吞吐量分析

4.1.1 改進型三維概率CSMA協議硬件系統的吞吐量統計分析

將不同到達率下硬件系統的吞吐量測試值和理論值進行對比，驗證硬件系統設計的合理性。

發送數據的最小單元為1個字節，設定系統時鐘是10 ns，最小時隙的長度為80 ns，即空閑狀態占用的時隙長度；數據成功發送占用的有效時隙長度為最小時隙的10倍，其占用的時隙長度為800 ns；數據發生碰撞占用的有效時隙長度為最小時隙的5倍，其占用的時隙長度為400 ns.因此硬件系統的吞吐量為

(10)

式中：Sh為硬件系統的吞吐量；KU為發送成功的信息分組數；T為仿真的總時長。

對硬件系統在到達率λ取值為1～7時的吞吐量進行統計分析，具體結果如圖15～圖21所示。

圖15 到達率為1的信息分組接收情況Fig.15 Information packet receiving with arrival rate of 1

由圖15可見，每成功接收一個信息分組，成功事件“sucess”的統計就加1.500 μs的測試時間內，成功接收的信息分組數為327，應用(10)式得到系統吞吐量為0.523 2，根據(2)式可求出系統的理論吞吐量為0.523 9.故硬件測試值和理論值的相對誤差為0.134%.

由圖16可見，500 μs的測試時間內，成功接收的信息分組數為368，應用(10)式得到系統吞吐量為0.588 8，根據(2)式可求出系統的理論吞吐量為0.585 1.故硬件測試值和理論值的相對誤差為0.632%.

圖16 到達率為2的信息分組接收情況Fig.16 Information packet receiving with arrival rate of 2

由圖17可見，500 μs的測試時間內，成功接收的信息分組數為342，應用(10)式得到系統吞吐量為0.547 2，根據(2)式可求出系統的理論吞吐量為0.558 5.故硬件測試值和理論值的相對誤差為2.02%.

圖17 到達率為3的信息分組接收情況Fig.17 Information packet receiving with arrival rate of 3

由圖18可見，500 μs的測試時間內，成功接收的信息分組數為321，應用(10)式得到系統的吞吐量為0.513 6，根據(2)式可求出系統的理論吞吐量為0.515 4.故硬件測試值和理論值的相對誤差為0.35%.

圖18 到達率為4的信息分組接收情況Fig.18 Information packet receiving with arrival rate of 4

由圖19可見，500 μs的測試時間內，成功接收的信息分組數為290，應用(10)式得到系統吞吐量為0.464，根據(2)式可求出系統的理論吞吐量為0.469 1.故硬件測試值和理論值的相對誤差為0.51%.

圖19 到達率為5的信息分組接收情況Fig.19 Information packet receiving with arrival rate of 5

由圖20可見，500 μs的測試時間內，成功接收的信息分組數為267，應用(10)式得到系統的吞吐量為0.427 2，根據(2)式可求出系統的理論吞吐量為0.422 2.故硬件測試值和理論值的相對誤差為1.18%.

圖20 到達率為6的信息分組接收情況Fig.20 Information packet receiving with arrival rate of 6

由圖21可見，500 μs的測試時間內，成功接收的信息分組數為234，應用(10)式得到系統吞吐量為0.374 4，根據(2)式可求出系統的理論吞吐量為0.375 4.故硬件測試值和理論值的相對誤差為0.27%.

圖21 到達率為7的信息分組接收情況Fig.21 Information packet receiving with arrival rate of 7

根據圖15～圖21，得到硬件系統的測試值和理論值的對比如表1所示。

表1 硬件系統的測試值和理論值比較Tab.1 Comparison of simulated and theoretical values of hardware system

由表1可知：基于FPGA設計的硬件電路系統吞吐量的測試值和理論值基本吻合，相對誤差最大值也僅為2.02%，證明了系統設計的合理性。

4.1.2 多優先級的改進型三維概率CSMA協議硬件系統的吞吐量統計分析

根據(7)式設置硬件系統中優先級為1的節點到達率為4，優先級為2的節點到達率為10，優先級為3的節點到達率為22.對多優先級硬件系統成功接收信息分組的情況進行統計，得到如圖22所示結果。

圖22 系統信息分組的接收情況統計Fig.22 Statistics on the receiving of system information packets

圖22中，500 μs的測試時間內，channel1_*顯示優先級為1的節點在信道1中成功發送的信息分組數分別為352和357；channel2_*顯示優先級為2的節點在信道1和2中成功發送的信息分組數分別為357、339、349、343、356；channel3_*顯示了優先級為3的節點在信道1、2和3中成功發送的信息分組數分別為348、359、350、351、352、364、345、357、345、353、349.優先級為1、2和3的節點占用信道的比例分別為0.336 2、0.827 1和1.836 7.根據(9)式可得優先級為1、2和3的節點占用信道的比例分別為0.333 3、0.833 3和1.833 3.因此，硬件系統中各優先級占用信道的比例和理論值一致，證明了系統設計的正確性。

4.2 時延分析

4.2.1 理論模型的時延分析

在Ad Hoc網絡的接入控制模型中，Edi表示第i條信道中時延平均長度，Sdi表示第i條信道中時延占仿真時長的比例。則平均時延和時延占仿真時長的比例分別[16-17]為

Edi=N·a·(KUi+KBi)；

(11)

(12)

對改進前后系統的時延占比進行仿真分析，結果如圖23、圖24所示。

圖23 改進后模型的理論時延占比情況Fig.23 Delay proportion of the modified model

圖24 傳統模型的理論時延占比情況Fig.24 Delay proportion of traditional model

由圖23和圖24可見，隨著到達率的增加系統，時延所占的比例不斷增加，但是圖24在到達率大于6后不再增加，因為此時系統的吞吐量基本趨近于0，改進后模型則在到達率大于20后才趨于穩定，間接證明了改進后系統在到達率較大情況下的吞吐量明顯大于改進前。相同到達率情況下，改進后模型的時延占比大于改進前，但是改進后模型在相同仿真時間下，成功接收信息分組的數更多。

4.2.2 硬件系統的時延分析

為了驗證系統的時延性能，在λ=2的條件下，對改進前后硬件系統進行仿真，并統計碰撞事件、空閑事件和成功事件的數量。計算出系統的時延為

τ=T-800KU-400KB-80KI.

(13)

系統設定仿真時長T為500 000 ns，統計結果如圖25和圖26所示。

圖25 到達率為2的傳統CSMA協議接收信息分組情況Fig.25 Information packets received by traditional CSMA protocol with arrival rate of 2

圖26 到達率為2的改進型CSMA協議接收信息分組的情況Fig.26 Information packets received by improved CSMA protocol with arrival rate of 2

圖25中，“success”表示成功接收的信息分組數，“collision”表示碰撞事件數，“idle”表示空閑事件數。每成功發送1個信息分組，“success”的數目加1；1個碰撞事件發生時，“collision”的數目加1；每個空閑事件發生時，“idle”的數目加1.500 μs的測試時間內，成功事件(success)、空閑事件(idle)和碰撞事件(collision)的數量最終統計分別為284、209和265.根據(13)式得到系統總時延為44 080 ns，占仿真長度的8.816%，因此平均成功發送一個信息分組的時延為155.211 ns.理論時延占比為8.109%，仿真時延占比和該值僅相差0.71%.

圖26中，500 μs的測試時間內，成功事件、空閑事件和碰撞事件的數量最終統計分別為359、287和335.根據(13)式得到系統時延為54 400 ns，占仿真長度的11.168%，因此平均成功發送一個信息分組的時延為151.53 ns.理論時延占比為10.16%，仿真時延占比和該值僅相差1.008%.

由此可知，改進后系統時延占比增加了2.352%，但是改進后系統成功發送的信息分組比改進前增加了75，平均成功發送一個信息分組時延減少了3.681 ns.因此，改進后系統有效減少了系統時延，改善了Ad Hoc網絡傳輸數據的實時效果。

5 結論

本文針對Ad Hoc網絡中MAC層的傳統隨機接入控制協議吞吐量不高、時延較大的問題，在傳統協議基礎上加入三維概率Pi、Pu和Pb，為空閑、成功和碰撞3種不同狀態分配不同的時隙長度，增加區分服務的優先級，得到多優先級改進型三維概率CSMA協議。通過數學實驗工具MATLAB軟件分析，結果表明該協議有效改善了Ad Hoc網絡傳輸的吞吐量和時延，增強了Ad Hoc的可靠性，減少了傳輸時延。結合FPGA模塊化設計易于改進、異步傳輸等特點，在理論推導基礎上設計了多優先級改進型三維概率CSMA接入控制協議的硬件電路系統，并對硬件系統吞吐量和時延進行測試分析，得到吞吐量測試結果和理論值的相對誤差不大于2.02%，改進后系統傳輸時延比改進前減少了3.681 ns，吞吐量最大值增長了24.34%.由此可見，基于FPGA設計的多優先級改進型三維概率CSMA協議模型在Ad Hoc網絡MAC層具有明顯的優勢。