分布式無(wú)線廣播的設(shè)計(jì)

王浩瀅

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

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

1 基于BP神經(jīng)網(wǎng)絡(luò)的網(wǎng)絡(luò)通信能力評(píng)估指標(biāo)體系

1.1 基本設(shè)想

評(píng)估網(wǎng)絡(luò)的通信能力，是本文研究的首要問(wèn)題，基于此問(wèn)題利用改進(jìn)的BP 神經(jīng)網(wǎng)絡(luò)進(jìn)行計(jì)算。在該網(wǎng)絡(luò)通信能力評(píng)估中，所需獲取的數(shù)據(jù)是效能評(píng)估指標(biāo)體系中一些底層的數(shù)據(jù)同時(shí)也是神經(jīng)元的代表，分別有7 個(gè)節(jié)點(diǎn)。[23][1]中間層是輸入模式的隱含表示，也正是利用中間層的數(shù)據(jù)傳輸使BP 神經(jīng)網(wǎng)絡(luò)具有了識(shí)別非線性模式的功能。若假定為20 個(gè)中間單元，使得輸出層的節(jié)點(diǎn)數(shù)正好對(duì)應(yīng)于優(yōu)、良、中、差4 個(gè)效能評(píng)估等級(jí)，評(píng)估如表1 所示。

表1：評(píng)語(yǔ)集

表2：信息數(shù)據(jù)信號(hào)發(fā)送時(shí)間段

表3：每次發(fā)生時(shí)間重疊時(shí)n1, n2 值

表4：待發(fā)送數(shù)據(jù)字發(fā)送時(shí)間表

神經(jīng)元輸入與輸出之間轉(zhuǎn)移函數(shù)選取Sigmoid 函數(shù)，即：

網(wǎng)絡(luò)誤差評(píng)價(jià)的過(guò)程就是比較期望值是否被達(dá)到，當(dāng)神經(jīng)網(wǎng)絡(luò)達(dá)到要求時(shí)，我們可以稱之具備了識(shí)別能力，網(wǎng)絡(luò)誤差公式如下：

式中，Ep是產(chǎn)生的神經(jīng)網(wǎng)絡(luò)差錯(cuò)值，tpi是第i 個(gè)輸出神經(jīng)元的期望值，Opi是第i 個(gè)輸出神經(jīng)元的實(shí)際值。[23][2]

1.2 不同分簇網(wǎng)絡(luò)通信能力的評(píng)估

模擬評(píng)估網(wǎng)絡(luò)通信能力時(shí)盡量消除外部環(huán)境因素等產(chǎn)生的影響。假定節(jié)點(diǎn)使用隨機(jī)的運(yùn)動(dòng)方式，傳輸?shù)墓β氏嗟龋撮_始時(shí)候便確定好目標(biāo)的運(yùn)動(dòng)方向，但在單位時(shí)間段后隨機(jī)改變節(jié)點(diǎn)的速度和方向，同時(shí)設(shè)定在規(guī)定的區(qū)域內(nèi)移動(dòng)，若超出范圍后按照規(guī)則反射回相應(yīng)空間繼續(xù)運(yùn)動(dòng)，可以在圖1 中觀察網(wǎng)絡(luò)通信能力的變化趨勢(shì)。[3][24]

網(wǎng)絡(luò)使用WCA 分簇算法構(gòu)建，但這種評(píng)估體系對(duì)于未知的因素?zé)o法進(jìn)行準(zhǔn)確預(yù)測(cè)，這是不足之處，給研究帶來(lái)了困難，所以建立一個(gè)合理準(zhǔn)確的科學(xué)方法進(jìn)行評(píng)價(jià)預(yù)估是我們目前呈需解決的重要問(wèn)題。

2 提高網(wǎng)絡(luò)效率

2.1 設(shè)計(jì)方案

無(wú)線網(wǎng)通信廣播的信息發(fā)送過(guò)程中，如若確定周期，不同的數(shù)據(jù)同時(shí)發(fā)送，但時(shí)間軸唯一，這就容易導(dǎo)致不同的數(shù)據(jù)在傳輸過(guò)程中發(fā)生碰撞，所以需要進(jìn)行碰撞檢測(cè)，問(wèn)題分析，本文對(duì)可能產(chǎn)生時(shí)間沖突的區(qū)間展開研究，提出一種基于最小公倍周期與最大公約數(shù)的時(shí)間片的任務(wù)優(yōu)化區(qū)間規(guī)劃的模型嘗試進(jìn)行問(wèn)題解決。

2.1.1 節(jié)點(diǎn)發(fā)送信息時(shí)間的沖突問(wèn)題

節(jié)點(diǎn)發(fā)送一組工作信號(hào)，由L1 與L2 兩種不同數(shù)據(jù)值組成，假定其發(fā)送周期T 分別為20ms、15ms，信息從開始發(fā)送到發(fā)送完成的一組周期時(shí)間叫做傳輸時(shí)間，用Δ t 表示，等待傳輸?shù)臄?shù)據(jù)1由L1 組成，等待傳輸?shù)臄?shù)據(jù)12 由兩個(gè)持續(xù)的L2 構(gòu)成，當(dāng)出現(xiàn)連續(xù)傳輸?shù)那闆r時(shí)，令則其傳輸時(shí)間分別為Δ t1、Δ t2。先發(fā)送數(shù)據(jù)1，待發(fā)送完成后，即Δ t 時(shí)刻，發(fā)送數(shù)據(jù)2，這樣進(jìn)行周期性循環(huán)發(fā)送，推導(dǎo)發(fā)送公式為：[1][2][21]

圖1：網(wǎng)絡(luò)的通信能力隨節(jié)點(diǎn)傳輸范圍的變化

圖2：信息占用節(jié)點(diǎn)數(shù)據(jù)圖

圖3：生成結(jié)果統(tǒng)計(jì)圖

圖4：信道占用率標(biāo)準(zhǔn)差σ 隨時(shí)間變化

圖5：4 對(duì)節(jié)點(diǎn)下吞吐量隨時(shí)間的變化情況

圖6：4 對(duì)節(jié)點(diǎn)下公平性隨時(shí)間的變化情況

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

圖7：8 對(duì)節(jié)點(diǎn)下吞吐量隨時(shí)間的變化情況

圖8：8 對(duì)節(jié)點(diǎn)下公平性隨時(shí)間的變化情況

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

通過(guò)評(píng)估結(jié)果可以看到當(dāng)時(shí)間軸設(shè)定為無(wú)限時(shí)，由于數(shù)據(jù)字的傳輸時(shí)間Δ t，發(fā)送端若周期性循環(huán)發(fā)送兩種數(shù)據(jù)字輸時(shí)間,會(huì)產(chǎn)生碰撞從而在時(shí)間軸上總會(huì)出現(xiàn)沖突的部分。所以出現(xiàn)兩種數(shù)據(jù)字發(fā)生時(shí)間沖突的時(shí)間段，多數(shù)情況下是由于具備不同特性的數(shù)據(jù)值構(gòu)成的信號(hào)在同一時(shí)間進(jìn)行傳輸，產(chǎn)生節(jié)點(diǎn)發(fā)送信息時(shí)間的沖突問(wèn)題。通過(guò)不同數(shù)據(jù)字構(gòu)成的發(fā)送周期和傳輸時(shí)間利用交集算法，可求得可能造成時(shí)間沖突的時(shí)間段在無(wú)限長(zhǎng)的時(shí)間軸上，這時(shí)可以利用算法進(jìn)行自動(dòng)調(diào)整重發(fā)。

2.2 提高通信效率

2.2.1 網(wǎng)絡(luò)通信中信息傳輸關(guān)系的劃分

為了提高通信效率，擴(kuò)大直接連接的物理信道寬度，得到傳輸速率，將網(wǎng)絡(luò)通信中信息傳輸關(guān)系分為不同的階段：

假設(shè)，由ωkl為信息質(zhì)量，?op為節(jié)點(diǎn)數(shù)目，kpo為傳輸信息的總量，則任意節(jié)點(diǎn)間的傳輸速率為：[3][25]

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

利用本文提出的基于最小公倍周期與最大公約時(shí)間片的任務(wù)優(yōu)化規(guī)劃方法進(jìn)行驗(yàn)證。如圖2 所示。

表5：退避窗口值

表6：仿真參數(shù)

以上時(shí)間段時(shí)，即在該時(shí)刻，需同時(shí)發(fā)送兩種或以上信息，即產(chǎn)生了時(shí)間沖突問(wèn)題。帶入時(shí)間片規(guī)劃算法公式中，得到待發(fā)送區(qū)間的發(fā)送時(shí)間如表4 所示。

若在此基礎(chǔ)上以表中時(shí)間特性值編寫矩陣，順序發(fā)送，生成結(jié)果如圖3 所示。

實(shí)驗(yàn)結(jié)果表明，經(jīng)最小公倍周期與最大公約時(shí)間片規(guī)劃算法處理后，如果循環(huán)在固定的時(shí)間范圍內(nèi)，且周期性傳遞，可以有效的避免時(shí)間軸上數(shù)據(jù)字的碰撞問(wèn)題，有效的提高網(wǎng)絡(luò)的整體通信效率。

3 動(dòng)態(tài)解決發(fā)送沖突問(wèn)題

3.1 研究背景

在無(wú)線廣播網(wǎng)絡(luò)中當(dāng)節(jié)點(diǎn)數(shù)增多對(duì)信道的競(jìng)爭(zhēng)也越激烈，節(jié)點(diǎn)所占份額不同傳輸機(jī)會(huì)也不等從而發(fā)生碰撞產(chǎn)生沖突，此時(shí)需要自動(dòng)調(diào)整然后重發(fā)。本文提出了CORAFA 算法，解決數(shù)據(jù)值傳輸過(guò)程中發(fā)生碰撞的問(wèn)題。

3.2 CORAFA算法

假設(shè)網(wǎng)絡(luò)中節(jié)點(diǎn)對(duì)數(shù)目為n，定義該發(fā)送節(jié)點(diǎn)信道占用率為傳輸?shù)挠行r(shí)間與數(shù)據(jù)包傳送的間隔的比值為，記作S，則有

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

3.3 實(shí)例分析

假設(shè)在單沖突域內(nèi)有8 個(gè)通信節(jié)點(diǎn)對(duì)，每個(gè)節(jié)點(diǎn)對(duì)均持續(xù)發(fā)送數(shù)據(jù)包，發(fā)包速率為1Mb/s，間隔時(shí)間設(shè)置為20μs，節(jié)點(diǎn)對(duì)隨機(jī)選擇發(fā)包前的退避窗口τ，計(jì)算公式為：

在實(shí)際工作時(shí)，如若τ按照如下方式選取，與實(shí)際情況更為貼近，如果重新設(shè)置隨機(jī)數(shù)，利用當(dāng)前的時(shí)間段產(chǎn)生8 個(gè)隨機(jī)數(shù)不斷重復(fù)利用其生成隨機(jī)數(shù)種子，以此為基礎(chǔ)利用隨機(jī)數(shù)種子在[0,1]內(nèi)生成8 個(gè)隨機(jī)數(shù)序列，分別對(duì)應(yīng)一個(gè)節(jié)點(diǎn)對(duì)．使得產(chǎn)生的8 個(gè)隨機(jī)數(shù)種子與競(jìng)爭(zhēng)窗口值W 進(jìn)行乘法運(yùn)算，得到當(dāng)前的退避窗口τ。[23]

表5 為8 個(gè)節(jié)點(diǎn)對(duì)的部分退避窗口值，在數(shù)據(jù)值傳輸開始時(shí)每8 個(gè)隨機(jī)序列為一組，每組第一個(gè)第1 個(gè)數(shù)字與Wmin進(jìn)行乘法運(yùn)算，得到初始退避窗口值。此后每經(jīng)過(guò)一個(gè)退避時(shí)間間隔進(jìn)行減1 運(yùn)算直至為零，標(biāo)志著計(jì)算結(jié)束。之后循環(huán)重復(fù)上述過(guò)程，直到不發(fā)生節(jié)點(diǎn)沖突。[23][1]

對(duì)于CORAFA 算法，如果W 在[Wmin，h1)內(nèi)，新的競(jìng)爭(zhēng)窗口值仍為Wmin，表示傳輸成功。計(jì)算所有節(jié)點(diǎn)對(duì)信道占用率的標(biāo)準(zhǔn)差σ。

圖4 體現(xiàn)了信道占用率標(biāo)準(zhǔn)差隨時(shí)間變化情況，通過(guò)圖中數(shù)據(jù)折線顯示可以明顯的看出，CORAFA 算法的公平性明顯好于NAVB算法。[23]

3.4 仿真

為了驗(yàn)證實(shí)驗(yàn)結(jié)果進(jìn)行仿真，從而比較CORAFA 算法與BEB算法、MILD 算法及NAVB 算法的吞吐量和公平性，在仿真實(shí)驗(yàn)中本文選取節(jié)點(diǎn)對(duì)數(shù)為4 和8，分析仿真結(jié)果。

3.4.1 仿真場(chǎng)景

仿真中節(jié)點(diǎn)對(duì)利用簡(jiǎn)單矩形拓?fù)浣Y(jié)構(gòu)的處理方式，節(jié)點(diǎn)位置隨機(jī)安排。如表6 所示。

3.4.2 結(jié)果及分析

首先選取4 對(duì)節(jié)點(diǎn)進(jìn)行比較，通過(guò)仿真實(shí)驗(yàn)結(jié)果圖（圖5）可以分析得出BEB 算法僅提高網(wǎng)絡(luò)吞吐量而不保證公平性，NAVB和CORAFA 算法在保證吞吐量的情況下也減少?zèng)_突碰撞，MILD算法競(jìng)爭(zhēng)窗口值倍數(shù)增加，導(dǎo)致其長(zhǎng)期偏大，使得低負(fù)載情況下多余的等待時(shí)間過(guò)長(zhǎng)，吞吐量指標(biāo)明顯偏低。[2][24]

由于在MTLD算法下多余的等待時(shí)間過(guò)長(zhǎng)，節(jié)點(diǎn)無(wú)法接入信道，因此不算優(yōu)良，而CORAFA 算法動(dòng)態(tài)調(diào)整W 值依據(jù)不同情況下的負(fù)載值高低，因?yàn)槭褂帽稊?shù)的方式增加或者減少，能夠在過(guò)程中快速的看到調(diào)整效果，表現(xiàn)較好。[23]4 對(duì)節(jié)點(diǎn)下公平性隨時(shí)間的變化情況如圖6 所示。

8 對(duì)節(jié)點(diǎn)情況下，根據(jù)仿真結(jié)果圖（圖7）可以看到當(dāng)負(fù)載增加時(shí)導(dǎo)致數(shù)據(jù)傳輸?shù)臎_突增大，吞吐量受到影響有稍微下降趨勢(shì)，但BEB 算法和CORAFA 算法在考慮了公平性的條件下還有效的保證了吞吐量，在圖中可以看到?jīng)]有受到明顯的影響。而NAVB 算法受影響較大，MILD 算法在低負(fù)載的情況下線性減少窗口競(jìng)爭(zhēng)之使得吞吐量呈緩慢上升的趨勢(shì)。[1][2][23]

圖7 為公平性隨時(shí)間變化的線性表示，其中MILD 算法在高負(fù)載條件下節(jié)點(diǎn)接入信道的平均時(shí)間變長(zhǎng)，導(dǎo)致其公平性下降使得吞吐情況表現(xiàn)更差，改變明顯，而其他幾種算法與低負(fù)載情況相差不大，綜合來(lái)比較CORAFA 算法最優(yōu)。[23]8 對(duì)節(jié)點(diǎn)下公平性隨時(shí)間的變化情況如圖8 所示。

綜上，比較幾種算法的吞吐量性能指標(biāo)，CORAFA 算法與BEB 算法相似，遠(yuǎn)優(yōu)于其他2 種算法，同時(shí)CORAFA 算法的公平性在低負(fù)載場(chǎng)景下也遠(yuǎn)優(yōu)于BEB算法，高負(fù)載下與NAVB算法類似，基于多種指標(biāo)衡定下，CORAFA 算法表現(xiàn)最優(yōu)。[1][2][22]

4 結(jié)束語(yǔ)

本文首先構(gòu)造合理的指標(biāo)來(lái)描述網(wǎng)絡(luò)的整體通信效率。評(píng)估網(wǎng)絡(luò)通信能力的主要困難在于預(yù)估評(píng)定其中非定量無(wú)法確定的因素，所以需要建立數(shù)學(xué)關(guān)系，完善的評(píng)估指標(biāo)輸入輸出的完整體系，提高評(píng)估結(jié)果的可信度。針對(duì)無(wú)線廣播網(wǎng)絡(luò)的特點(diǎn)，提出構(gòu)建基于BP 神經(jīng)網(wǎng)絡(luò)的網(wǎng)絡(luò)通信能力評(píng)估指標(biāo)體系，對(duì)網(wǎng)絡(luò)的整體通信能力進(jìn)行評(píng)估仿真，并得出網(wǎng)絡(luò)通信能力隨節(jié)點(diǎn)傳輸范圍的變化圖。[2]為達(dá)到整體通信效率最高的傳送時(shí)間段，本文對(duì)可能產(chǎn)生的沖突碰撞問(wèn)題的時(shí)間軸區(qū)間范圍進(jìn)行分析研究，提出一種基于最小公倍周期與最大公約時(shí)間片的任務(wù)優(yōu)化規(guī)劃方法。進(jìn)行信息傳輸?shù)姆抡骝?yàn)證，調(diào)整時(shí)間沖突區(qū)間。該實(shí)驗(yàn)結(jié)果解決了節(jié)點(diǎn)發(fā)送信息時(shí)可能產(chǎn)生的沖突問(wèn)題，同時(shí)使網(wǎng)絡(luò)整體通信效率盡可能高。在無(wú)線廣播網(wǎng)絡(luò)中，隨著接入節(jié)點(diǎn)增多，對(duì)于信道傳輸中競(jìng)爭(zhēng)越激烈，不同節(jié)點(diǎn)所占份額不同導(dǎo)致獲得的通信機(jī)會(huì)不等，是發(fā)生沖突碰撞的主要原因。此時(shí)需要自動(dòng)調(diào)整然后重發(fā)。本文研究提出CORAFA 算法，提高網(wǎng)絡(luò)的整體通信效率，后續(xù)還需要針對(duì)提高整體通信效率的問(wèn)題做進(jìn)一步的研究。