分布式無線廣播的設計

王浩瀅

（山東科技大學智能裝備學院 山東省青島市 271021）

廣播是一種重要的信息傳輸形式，策略是通過節點之間的相互傳播，但在信息傳送的過程中必須解決發送互相沖突的問題，因此無線網的許多基礎通信協議都使用了令牌的方法來解決這個問題即節點之間依次按照規則順序發送。若每個通信節點都是一個低功率的發射器，對于他接收或者發送的其他節點而言，只有發送源距離在一定范圍之內才能收到信號，而且節點是一個動態的，會相互遠離或接近，所以每個節點需要不定期地、接續地發送信息，但需要不間斷的保持在接收信息的狀態避免錯過數據值，在分布式無線廣播網絡中，沒有網絡的基礎設施，每個節點發送消息，同時接收自己需要的信息，不需要持續不間斷的交換信息，只選擇自己需要的即可，但所有信息只能使用同一個頻率發送，這就導致一旦有兩個或多個節點的廣播占用同一時間段進行傳輸會發生碰撞產生沖突，這時原本接收到信息的節點就都能監聽到沖突。假設發送每條信息所占用的時間都是等長的使用同樣的內置算法，本文嘗試構造一個合理的指標來描述網絡的整體通信效率，并在每個節點需要發送信息時，設計一個方案來選擇發送的時間段，盡可能解決發送信息時沖突的問題，使網絡的整體通信效率盡可能高。[21][1]

1 基于BP神經網絡的網絡通信能力評估指標體系

1.1 基本設想

評估網絡的通信能力，是本文研究的首要問題，基于此問題利用改進的BP 神經網絡進行計算。在該網絡通信能力評估中，所需獲取的數據是效能評估指標體系中一些底層的數據同時也是神經元的代表，分別有7 個節點。[23][1]中間層是輸入模式的隱含表示，也正是利用中間層的數據傳輸使BP 神經網絡具有了識別非線性模式的功能。若假定為20 個中間單元，使得輸出層的節點數正好對應于優、良、中、差4 個效能評估等級，評估如表1 所示。

表1：評語集

表2：信息數據信號發送時間段

表3：每次發生時間重疊時n1, n2 值

表4：待發送數據字發送時間表

神經元輸入與輸出之間轉移函數選取Sigmoid 函數，即：

網絡誤差評價的過程就是比較期望值是否被達到，當神經網絡達到要求時，我們可以稱之具備了識別能力，網絡誤差公式如下：

式中，Ep是產生的神經網絡差錯值，tpi是第i 個輸出神經元的期望值，Opi是第i 個輸出神經元的實際值。[23][2]

1.2 不同分簇網絡通信能力的評估

模擬評估網絡通信能力時盡量消除外部環境因素等產生的影響。假定節點使用隨機的運動方式，傳輸的功率相等，即開始時候便確定好目標的運動方向，但在單位時間段后隨機改變節點的速度和方向，同時設定在規定的區域內移動，若超出范圍后按照規則反射回相應空間繼續運動，可以在圖1 中觀察網絡通信能力的變化趨勢。[3][24]

網絡使用WCA 分簇算法構建，但這種評估體系對于未知的因素無法進行準確預測，這是不足之處，給研究帶來了困難，所以建立一個合理準確的科學方法進行評價預估是我們目前呈需解決的重要問題。

2 提高網絡效率

2.1 設計方案

無線網通信廣播的信息發送過程中，如若確定周期，不同的數據同時發送，但時間軸唯一，這就容易導致不同的數據在傳輸過程中發生碰撞，所以需要進行碰撞檢測，問題分析，本文對可能產生時間沖突的區間展開研究，提出一種基于最小公倍周期與最大公約數的時間片的任務優化區間規劃的模型嘗試進行問題解決。

2.1.1 節點發送信息時間的沖突問題

節點發送一組工作信號，由L1 與L2 兩種不同數據值組成，假定其發送周期T 分別為20ms、15ms，信息從開始發送到發送完成的一組周期時間叫做傳輸時間，用Δ t 表示，等待傳輸的數據1由L1 組成，等待傳輸的數據12 由兩個持續的L2 構成，當出現連續傳輸的情況時，令則其傳輸時間分別為Δ t1、Δ t2。先發送數據1，待發送完成后，即Δ t 時刻，發送數據2，這樣進行周期性循環發送，推導發送公式為：[1][2][21]

圖1：網絡的通信能力隨節點傳輸范圍的變化

圖2：信息占用節點數據圖

圖3：生成結果統計圖

圖4：信道占用率標準差σ 隨時間變化

圖5：4 對節點下吞吐量隨時間的變化情況

圖6：4 對節點下公平性隨時間的變化情況

即可求得發送端第n 次發送L1 與L2 時的時間段集合s1,s2，分別為：

圖7：8 對節點下吞吐量隨時間的變化情況

圖8：8 對節點下公平性隨時間的變化情況

將假定的數值帶入公式其中，得到重疊部分的數據字交集區間段如表2 所示，利用區間交集算法，求得兩種數據字在發生沖突的時間段范圍內各自的發送次數n1, n2的值。如表3 所示。[5]

通過評估結果可以看到當時間軸設定為無限時，由于數據字的傳輸時間Δ t，發送端若周期性循環發送兩種數據字輸時間,會產生碰撞從而在時間軸上總會出現沖突的部分。所以出現兩種數據字發生時間沖突的時間段，多數情況下是由于具備不同特性的數據值構成的信號在同一時間進行傳輸，產生節點發送信息時間的沖突問題。通過不同數據字構成的發送周期和傳輸時間利用交集算法，可求得可能造成時間沖突的時間段在無限長的時間軸上，這時可以利用算法進行自動調整重發。

2.2 提高通信效率

2.2.1 網絡通信中信息傳輸關系的劃分

為了提高通信效率，擴大直接連接的物理信道寬度，得到傳輸速率，將網絡通信中信息傳輸關系分為不同的階段：

假設，由ωkl為信息質量，?op為節點數目，kpo為傳輸信息的總量，則任意節點間的傳輸速率為：[3][25]

式子中hlkl代表總信息傳輸流量。

利用本文提出的基于最小公倍周期與最大公約時間片的任務優化規劃方法進行驗證。如圖2 所示。

表5：退避窗口值

表6：仿真參數

以上時間段時，即在該時刻，需同時發送兩種或以上信息，即產生了時間沖突問題。帶入時間片規劃算法公式中，得到待發送區間的發送時間如表4 所示。

若在此基礎上以表中時間特性值編寫矩陣，順序發送，生成結果如圖3 所示。

實驗結果表明，經最小公倍周期與最大公約時間片規劃算法處理后，如果循環在固定的時間范圍內，且周期性傳遞，可以有效的避免時間軸上數據字的碰撞問題，有效的提高網絡的整體通信效率。

3 動態解決發送沖突問題

3.1 研究背景

在無線廣播網絡中當節點數增多對信道的競爭也越激烈，節點所占份額不同傳輸機會也不等從而發生碰撞產生沖突，此時需要自動調整然后重發。本文提出了CORAFA 算法，解決數據值傳輸過程中發生碰撞的問題。

3.2 CORAFA算法

假設網絡中節點對數目為n，定義該發送節點信道占用率為傳輸的有效時間與數據包傳送的間隔的比值為，記作S，則有

理想信道占用率就是保證公平，即信道的占用率相等，都為1/n。當S=1/n 時，為理想情況，保證絕對公平的。如果S＞1/n，該節點的利用率高于平均值，證明占用率偏大，則需適當增加競爭窗口值，以減少占用率。如果S＜1/n，則說明該節點對的占用率低于平均值，在該種情況下記錄當前競爭窗口值為W*，然后將競爭窗口值置為0，增加節點對的有效時間V。不斷重復此過程，直至S ≥1/n，即高于平均值后，恢復競爭窗口值為W*。本文通過對W 的調整，節點對的占用信道率隨之改變，趨向并保持相對公平的狀態。[23][22]

3.3 實例分析

假設在單沖突域內有8 個通信節點對，每個節點對均持續發送數據包，發包速率為1Mb/s，間隔時間設置為20μs，節點對隨機選擇發包前的退避窗口τ，計算公式為：

在實際工作時，如若τ按照如下方式選取，與實際情況更為貼近，如果重新設置隨機數，利用當前的時間段產生8 個隨機數不斷重復利用其生成隨機數種子，以此為基礎利用隨機數種子在[0,1]內生成8 個隨機數序列，分別對應一個節點對．使得產生的8 個隨機數種子與競爭窗口值W 進行乘法運算，得到當前的退避窗口τ。[23]

表5 為8 個節點對的部分退避窗口值，在數據值傳輸開始時每8 個隨機序列為一組，每組第一個第1 個數字與Wmin進行乘法運算，得到初始退避窗口值。此后每經過一個退避時間間隔進行減1 運算直至為零，標志著計算結束。之后循環重復上述過程，直到不發生節點沖突。[23][1]

對于CORAFA 算法，如果W 在[Wmin，h1)內，新的競爭窗口值仍為Wmin，表示傳輸成功。計算所有節點對信道占用率的標準差σ。

圖4 體現了信道占用率標準差隨時間變化情況，通過圖中數據折線顯示可以明顯的看出，CORAFA 算法的公平性明顯好于NAVB算法。[23]

3.4 仿真

為了驗證實驗結果進行仿真，從而比較CORAFA 算法與BEB算法、MILD 算法及NAVB 算法的吞吐量和公平性，在仿真實驗中本文選取節點對數為4 和8，分析仿真結果。

3.4.1 仿真場景

仿真中節點對利用簡單矩形拓撲結構的處理方式，節點位置隨機安排。如表6 所示。

3.4.2 結果及分析

首先選取4 對節點進行比較，通過仿真實驗結果圖（圖5）可以分析得出BEB 算法僅提高網絡吞吐量而不保證公平性，NAVB和CORAFA 算法在保證吞吐量的情況下也減少沖突碰撞，MILD算法競爭窗口值倍數增加，導致其長期偏大，使得低負載情況下多余的等待時間過長，吞吐量指標明顯偏低。[2][24]

由于在MTLD算法下多余的等待時間過長，節點無法接入信道，因此不算優良，而CORAFA 算法動態調整W 值依據不同情況下的負載值高低，因為使用倍數的方式增加或者減少，能夠在過程中快速的看到調整效果，表現較好。[23]4 對節點下公平性隨時間的變化情況如圖6 所示。

8 對節點情況下，根據仿真結果圖（圖7）可以看到當負載增加時導致數據傳輸的沖突增大，吞吐量受到影響有稍微下降趨勢，但BEB 算法和CORAFA 算法在考慮了公平性的條件下還有效的保證了吞吐量，在圖中可以看到沒有受到明顯的影響。而NAVB 算法受影響較大，MILD 算法在低負載的情況下線性減少窗口競爭之使得吞吐量呈緩慢上升的趨勢。[1][2][23]

圖7 為公平性隨時間變化的線性表示，其中MILD 算法在高負載條件下節點接入信道的平均時間變長，導致其公平性下降使得吞吐情況表現更差，改變明顯，而其他幾種算法與低負載情況相差不大，綜合來比較CORAFA 算法最優。[23]8 對節點下公平性隨時間的變化情況如圖8 所示。

綜上，比較幾種算法的吞吐量性能指標，CORAFA 算法與BEB 算法相似，遠優于其他2 種算法，同時CORAFA 算法的公平性在低負載場景下也遠優于BEB算法，高負載下與NAVB算法類似，基于多種指標衡定下，CORAFA 算法表現最優。[1][2][22]

4 結束語

本文首先構造合理的指標來描述網絡的整體通信效率。評估網絡通信能力的主要困難在于預估評定其中非定量無法確定的因素，所以需要建立數學關系，完善的評估指標輸入輸出的完整體系，提高評估結果的可信度。針對無線廣播網絡的特點，提出構建基于BP 神經網絡的網絡通信能力評估指標體系，對網絡的整體通信能力進行評估仿真，并得出網絡通信能力隨節點傳輸范圍的變化圖。[2]為達到整體通信效率最高的傳送時間段，本文對可能產生的沖突碰撞問題的時間軸區間范圍進行分析研究，提出一種基于最小公倍周期與最大公約時間片的任務優化規劃方法。進行信息傳輸的仿真驗證，調整時間沖突區間。該實驗結果解決了節點發送信息時可能產生的沖突問題，同時使網絡整體通信效率盡可能高。在無線廣播網絡中，隨著接入節點增多，對于信道傳輸中競爭越激烈，不同節點所占份額不同導致獲得的通信機會不等，是發生沖突碰撞的主要原因。此時需要自動調整然后重發。本文研究提出CORAFA 算法，提高網絡的整體通信效率，后續還需要針對提高整體通信效率的問題做進一步的研究。