多跳無線傳感器網絡動態比例公平接入優化方法
2023-09-19 04:12:45 1
專利名稱：多跳無線傳感器網絡動態比例公平接入優化方法
技術領域：
本發明是一種適用於低複雜度，低成本，低功耗的環境監控，工業控制等領域 的多跳無線傳感器網絡的優化接入控制方法。在網絡中節點負荷不均勻的情況下可 以顯著提高節點的吞吐量公平性並降低丟包概率。
背景技術：
多跳無線傳感器網絡是一種mesh結構網絡，它是一種與傳統無線網絡完全不 同的新型無線網絡技術。在傳統網絡中，節點以單跳的方式接入網絡，即使多個節 點相鄰它們也只能和接入點(AP)進行直接通信。而在無線mesh網絡中，任何節點 都具有路由功能，網絡中的每個節點都可以發送和接收數據，每個節點都可以與一 個或者多個對等節點進行直接通信，也可以轉發其它節點的數據。在多跳無線傳感 器網絡中，節點一般是靜止的且拓撲結構比較穩定，所有節點採集的數據都通過多 跳發送到匯聚網關節點。無線傳感器網絡的協議通常依照IEEE802. 15.4[1]。標準執行，該標準定義了 無線個域網(WPAN)中設備間通信的協議，標準採用衝突避免的載波偵聽(CSMA/CA) 機制並支持星型和對等拓撲網絡。標準規定了 868/915MHZ和2. 4G兩個頻段的物理 層和MAC層規範，其傳輸速率分別為20kbps， 40Kbps和240Kbps,是一種低速率無線 網絡標準。IEEE802. 15. 5[2]。是WPAN mesh網絡的候選草案，支持高速和低速WPAN 網絡，前者主要是對IEEE802. 15. 3標準的網絡層擴展，而後者是對IEEE802. 15. 4標 準的擴展。IEEE802. 15. 4標準的MAC層採用CSMA/CA協議，根據網絡為信標使能和非信標 使能分為時隙CSMA/CA和非時隙CSMA/CA，為了支持mesh網絡，釆用非時隙CSMA/CA 協議實現起來比較方便。具體的算法流程如圖1所示。網絡中各個節點組成mesh 網絡，有數據要發送時通過CSMA/CA算法競爭信道，所有的節點都通過網關和外部 網絡通信，這樣靠近網關處的節點不光要發送自身的數據還要轉發其他節點的數據，而網絡邊緣的節點則只鬚髮送自身數據，網關的負載猶如多跳場景下的路由簇 頭負載，如果讓它們以均等的機會接入信道，則大量數據會積壓在網絡的瓶頸節點 處，導致全網吞吐率下降和大量的丟包，因此這樣依照標準的節點近似平均地接入 信道，沒有考慮節點的流量公平性，使得網絡性能下降。IEEE 802.15.4 MAC協議規定的非時隙CSMA/CA接入協議，它的一些具體參數是最大重發次數(Retry Count):取值為3; 最大退避次數(NB):取值為4; 最小退避指數(macMinBE):取值為3; 最大退避指數(macMaxBE):取值為5;節點發送數據時先進行退避，退避時間為[O， CWO]之間的隨機時隙， CW(H2AmacMinBE-l,退避完成後偵聽信道，如果在偵聽時間內信道忙則將退避窗口 加倍並重新進行退避，否則立刻進行發送。如果信道一直忙則重複上述過程直到退 避次數達到NB，此時將退避窗口重置並重發數據包，如果達到最大重法次數仍未 成功則丟棄該數據包。數據包發送不成功有兩種情況退避次數達到NB後信道仍然忙或者發送數據 包後沒有在規定的時間內收到正確的ACK包，此時認為產生了衝突。這種隨機接 入方法有以下兩個缺點(1)所有節點退避窗口大小相同 因為採用CSMA/CA接入算法，節點競爭到信道的能力近似和節點的退避窗口大 小成正比，如果對所有節點採用相同的初始退避窗口則節點近似公平地獲得接入信 道的能力。然而在多跳網絡中，數據通過多跳傳輸到網關節點，靠近網關的節點不 僅要發送自身的數據，還要轉發別的節點的數據，這樣同一個競爭區域裡節點的負 荷就不相同，形成業務的"冷區"和"熱區"。如圖2所示，假設每個節點的自身 數據量為G，則節點1的負荷為5G，節點2,3，4,5的負荷分別為1G,3G,1G和1G，如果節點的初始退避窗口相同，則可以認為它們的MAC層吞吐量之比為1: 1: 1: h 1， 網絡層要求的吞吐量之比為5: 1: 3: 1: 1，當網絡能夠承受這些容量時，可以滿 足節點的發送要求，但是當節點負荷超出網絡容量時，負荷大的節點由於不能得到 更多的發送機會，導致包的大量丟棄，成為網絡的瓶頸，從而影響網絡整體的吞吐量。如圖中所示，節點1和節點2公平的獲得信道的使用權，網絡的吞吐量被節點2 "拉低"。(2)節點的流量公平性差由於節點近似公平地獲得信道的使用權，節點不能獲得和其負荷成比例的吞吐 量，例如節點1和節點2的發送概率相當，負荷大的節點不能獲得更多的發送機會， 導致節點的流量公平性很差。[3]針對多跳網絡中各節點負荷不均勻的問題提出了一種根據節點負荷調整初 始競爭窗口大小的算法，提高了網關節點處的吞吐量，改善了網絡的公平性。該算法的基本思想為假設節點間通信鏈路採用固定速率傳輸，給每個節點賦 予一個權值,權值的大小表徵節點承擔的通信節點數量(流量)，包括它本身和其它節 點。該權值可以從網絡層獲得或認為根據拓撲指定，當節點發送能力和權值成正比 時，數據流可以在網絡內平穩流動,從而消除網絡瓶頸處造成丟包以及網絡無線資源 的浪費。節點維護兩種競爭窗口 ，成功發送窗口和衝突窗口 。成功發送窗口 successwindow, =B,/W,*SF,,其中S,為回退窗口基本常數，^表徵節點/的權值，S《為該節點的競爭窗口調節尺度因子。各節點的初始巧值是一樣的。/ ,與巧的初始值相同，為了避免具有相同權值的相鄰節點衝突，實際選擇的回退時間為 B,=a*successwindoWi ，其中a為
間的隨機數。當節點發生碰撞時，競爭窗 口 變為 collisionwindowrmin(CWmax,CWmit^(2"^漏'咖'-l))，回退時間計數器值為(O， CH^)間的隨機數，0^_和0^，，,,,為系統定義的最大，最小競爭窗口。當很多節點發生碰撞後，collisiomvindow,可以指數增加以避免再次碰撞；當節點成功發送後，節點的競爭窗口再次變為成功發送窗口successwind。w,。衝突計數器collisioncounteri的初始值為0，此時節點按成功發送窗口競爭信道，當節點與其它節點發生碰撞時衝突計數器遞增1, 當數據包超過重發次數時被丟棄，此時衝突計數器重置為0。該算法在節點負荷差別較大時取得了一定效果，網關節點處吞吐量有了一定提 高，但是對節點競爭窗口的調整不是最優，權值的選取方法對算法性能影響很大，方案中沒有提出有效的權值設置算法。另外該方案對競爭窗口的調整限制在標準規 定的最大窗口和最小窗口範圍內，不能使網絡性能得到很好的優化。由於對不同狀 況下退避窗口採用不同的設置，相比標準協議有較大的改變，實現起來有一定困難。 參考文獻(如專利/論文/標準)[1]"Part 15.4: Wireless medium access control (MAC) and physical layer (PHY) specifications for low rate wireless personal area networks (WPAN)" IEEE Standard 802. 15.4, Oct. 2003 [2]"Part 15.5:Mesh Enhancements for Low-Rate WPANs" ， IEEEP802. 15.5 Draft Candidate, July. 2006 [3]張勇，蔡傑,宋梅，宋俊德，"無線mesh網絡公平性研究"，中國科學技術大學學報，Vol 37， No. 2 [4] T. 0zugur, M. Naghshineh, P. Kermani, and J. A Copeland， "Fair Media Access for Wireless LANs，， ， [A], in proceedings of IEEE GL0BALC0M' 99. 1999, 570-579發明內容技術問題本發明的目的是提出了一種多跳無線傳感器網絡動態比例公平接入 優化方法，在節點負荷不均勻的多跳網絡中，使每個節點獲得與其負荷成正比的吞 吐率，提高節點的吞吐率比例公平性。技術方案首先根據節點的負荷估計其最優發送概率並由飽和狀態下退避過程的Markov模型推導出每個節點的最優初始退避窗口，然後根據節點實際獲得的吞吐 率動態調整初始退避窗口以提高節點的流量公平性。在多跳網絡中節點負荷差別較 大，靠近網關處節點成為網絡瓶頸的條件下取得了節點吞吐率流量公平性的較大提 高並顯著降低了系統丟包率，在非飽和情況下網關節點的吞吐率也有較大提高。首先定義縮略語和關鍵術語WPAN 無線個域網WSN 無線傳感器網絡MESH 網狀網MAC 媒體接入控制CSMA/CA 載波偵聽多點接入/衝突避免PF-CSMA/CA比例公平CSMA/CA CW 競爭窗口 ICW 初始競爭窗口 Markov 馬爾可夫 GW 網關 ACK 應答為了達到上述目的，我們提出了動態比例公平競爭接入(PF-CSMA/CA: Proportional Fairness CSMA/CA)方法，該方法的技術方案通過以下方法實現。首先我們認為網絡中每個節點產生的自身數據流量都相等且為G，採用固定路 由通過多跳向網關節點發送數據，每個節點都知道網絡中所有一跳和兩跳鄰居的負 荷信息(這可以通過簡單的路由層算法在網絡形成階段得到)。根據這些節點的負荷信息，我們可以計算出每個節點的最優發送概率為節點的 負荷與它競爭範圍內其它所有節點的負荷之和的比值。在飽和條件下按照正EE 802.15.4標準的規定我們可以建立節點退避過程的Markov模型。根據Markov模型我 們可以得到初始退避窗口和最優發送概率的關係，從而得到初始退避窗口的值。從第二次發送開始，我們將動態調整每個節點的退避窗口的初始值。首先，每 次發送過程中記錄節點自己發送的包數目和接收到的數據包的數目，分別作為自身 和競爭範圍內所有其它節點實際獲得的吞吐率的估計值，利用這兩個值來計算比例 公平指數；然後根據比例公平指數所在的範圍對初始退避窗口進行調整，如果指數 大於高門限，則增大退避窗口，如果在高門限和低門限之間則維持原有窗口不變， 否則減小退避窗口。本發明的方法具體如下a) 第一次發送時首先，節點計算其最優發送概率formula see original document page 8，式中fo"c/,為節點/的負荷，/。a《為節點/的競爭範圍內所有其它節點的負荷之和；其次，節點計算其偵聽到信道忙的概率A-l-p(l-O，式中M 為節點 Z的一跳鄰居數目；然後，節點計算其最優初始退避窗口，._ 2 * (卜a) * (卜2 A) * (1 - /V"+') - r' * (卜2p,.) * (卜p廣') W°' _ (1-A"(-2A",最後，節點選擇實際初始退避窗口的取值為 /C^ =1113乂(2湯"朋-1，1^,'), b) 下一次發送時首先，節點實時估計其本身獲得的吞吐率及其競爭範圍內其它所有節 點實際獲得的吞吐率之和，具體估計方法為節點Z'每發送一個數據包，就將其吞吐率的估計值^加1，同樣地，節點Z'每收到一個數據包，就將對其所有競爭節點的吞吐率之和的估計值K加1;其次，節點計算其公平性指數/>/^、.=|^4;最後，節點根據公平性指數所在的範圍動態調整其初始退避窗口，具體調整方法為[1]如果公平性指數/^,^大於高門限77/,一那麼初始退避窗口為/CW'=min(CWmi,x，CU ) [2]如果公平性指數/^,,血、,在[77/^ ，77/,』內，則初始退避窗口為[3]否則如果公平性指數/^,,', 小於低門限，那麼初始退避窗口為上述幾式中，C『隨為最大退避窗口 ，計算方法為CWmax = 2她"""-1 ， C^ni 為 最小退避窗口 ，計算方法為CWm, = 2。""服-1 ， C『啦為上次初始退避窗口的取值，r/^，和77/^分別為公平性指數的高低門限，77/,,/3的取值為1.1，^^/(自為^^,的倒數； 〃為減小窗口的調節參數，取值為o.8，相應地，"為增大窗口的調節參數，取值為"=1.0 + _P《W。Y /10.0 。c) 此後，節點每次發送前都重複執行b)中的操作過程.有益效果本發明提出了一種適用於基於IEEE802.15.4標準的多跳無線傳感器 網絡的優化的接入控制方法，在網絡中節點路由固定且負荷不均勻的情況下，可以 顯著提高節點的的吞吐率流量公平性，以及更低的系統丟包率和非飽和情況下更髙 的網關吞吐率。相比IEEE802.15.4標準中規定的非時隙CSMA/CA協議，在多跳網絡 中本算法提供了更好的性能。本發明應用在多跳傳感器網絡中能很好地適應網絡負 載不均衡的環境，且對標準算法改動較小，稍作修改就能直接應用，有很好的前景。為了證明本發明的有效性，我們用OPNET仿真了算法，仿真環境如下1. 10個節點隨機分布在5OH50m的空間內，其中一個為網關節點，9個為普通 節點。2. 節點的通信距離為10m。3. 物理層數據傳輸速率為250kbps，信道為理想信道，所有的傳輸錯誤均為衝 突引起。我們採用節點吞吐率，系統丟包率和公平指數來衡量網絡的性能，其中公平指 數採用了兩種準則，它們的定義如下節點吞吐率節點成功發送的有效負載大小與時間的比值。系統丟包率丟棄的包數目與時間的比值。公formula see original document page 10前面均有定義，分別為節點/，)實際獲得的吞吐率負荷。從下面的仿真結果圖可以看出，對比於正EE802.15.4標準裡的CSMA/CA算法， 我們提出的優化方法在節點吞吐率的流量公平性，系統丟包率和非飽和情況下節點 的吞吐率等方面都具有優勢，特別是在節點負荷差距較大，網絡中形成瓶頸節點的 情況下提供了更好的網絡性能。
圖l是非時隙CSMA/CA算法流程，圖2是多跳網絡節點負荷，圖3是網關節點吞吐率，圖4是系統丟包率，圖5是採用準則1的公平指數，圖6是採用準則2的公平指數。
具體實施方式
本發明中具體是基於多跳網絡中節點的負荷計算第一次發送時的初始退避窗 口，並從第二次發送開始對上次的初始退避窗口進行動態調整，調整方法為實時估 計節點實際獲得的吞吐率及其所有競爭節點獲得的吞吐率之和，然後根據這兩個值 和節點的負荷和其競爭範圍內的其它節點的負荷之和計算公平性指數，並根據計算 結果按照門限規定的範圍分別對初始退避窗口採用不同的調整方法。一個多跳無線傳感器網絡中有9個普通節點2~10和一個網關節點1,普通節點採 用固定的路由向網關節點l發送數據，節點9， 10發送給節點8，節點7， 8發送給節 點6，節點5， 6發送給節點2，節點3發送給節點4，而節點2和4又發送給網關節點1， 它們自身生成數據包的速度都相等且為G，這樣節點2 10的負荷分別為 {7G, 1G， 2G, 1G， 5G， 1G, 3G， 1G, 3G },根據它們的相鄰關係可以得到它們的一跳鄰居 個數分別為{3， 2， 3, 3， 5, 4, 5， 2, 3}，競爭範圍內的節點負荷之和分別為 {8G, 3G, 13G, 13G, 14G, IOG， 9G, 4G, 5G}。對網絡中節點2 10，採用本發明的多跳無線傳感器網絡動態比例公平接入優化 方法步驟如下a.第一次發送時首先，節點計算其最優發送概率《-7-^"7，式中/o^為節點,的 負荷，/oW。為節點/的競爭範圍內所有其它節點的負荷之和，例如對節點2， 其最優發送概率r; = , " j = ^ = 0.47 ,同樣可以得到節點2~10的最優發送概率分另ij為{0.47,0.06,0.13,0.06，0.26,0.05,0.14, 0.08,0.08 };其次，節點計算其偵聽到信道忙的概率P,i-ft(l-O,代入上一步計'=1算得到的結果和節點的競爭節點個數，可以得到節點偵聽到信道忙的概率， 例如對節點2有/ 2 =1-]^[(卜"=(1-(1-0.13)*0-0.06)*(卜0.26))=0.395，同樣可以得到其它節點偵聽到信道忙的概率；然後，節點計算其最優初始退避窗口* . — 2*(1 —p,.)*0 — 2A)*0-/7")-r'*(l-2p,)*(l—p,"'+')°' (卜2/7,"+')對節點2，代入上一步計算的信道忙概率;>2=0.395和最優發送概率《=0.47以及 m=3，可以計算出節點2第一次發送的最優初始退避窗口 w。,' = 1.575;最後，節點選擇實際初始退避窗口的取值為/C^ = maW -1,W ,')，對 節點2有，/Cff2 = max(2滿""'1 -1,w 2') = 7 。 b.下一次發送時首先，節點實時估計其本身獲得的吞吐率及其競爭範圍內其它所有節點實際獲得的吞吐率之和，具體估計方法為節點z'每發送一個數據包，就 將其吞吐率的估計值K加1,同樣地，節點z'每收到一個數據包，就將對其所有競爭節點的吞吐率之和的估計值R加1，例如節點2在發送第一個數據包時，發送了2次，則y-2，期間收到3個包，則^,=3;其次，節點計算其公平性指數，對節點2有最後，節點根據公平性指數所在的範圍動態調整其初始退避窗口，具 體調整方法為如果公平性指數/^ d 大於高門限27;,那麼初始退避窗口為/C^=min(C^ax，Cff，*a) 12如果公平性指數P/^、在[7^"，7T^]內，則初始退避窗口為否則如果公平性指數小於低門限，那麼初始退避窗口為 /C『,=maX(C)^in，Cf^*/ ) 上述幾式中，C^肌、為最大退避窗口，計算方法為0^股=2^*-1， CW咖為最小退避窗口 ，計算方法為CWm, = 2""'"腿-1, C『w為上次初始退避窗口的取值，7T^(，和:r/^分別為公平性指數的高低門限，7T^的取值為1. 1，^^，為"^p的倒數；"為減小窗口的調節參數，取值為o.8，相應地，"為增大窗口的調節參數，取值為"=1.0 +屍^&/10.0。對節點2，上一歩計算的公平性指數為;^,','.、. =^ = 0.762 ，因此它要小於低門限77/麵=0. 909，3/8所以第二次發送時的初始退避窗口應該按o中的方法調整，因此/C『2 = max(Cf^,',,CW鄉*/ ) = max(7,7* 0.8) = 7 ，即初始退避窗口仍然為7。 c.此後，節點每次發送前都重複執行b)中的操作過程。在多跳無線傳感器網絡中，所有數據都以多跳方式發送到網關設備，因此靠近 網關處的節點相比網絡邊沿的節點要承擔更大的負荷，因此可以採用本發明中的優 化退避方法提高網絡性能。為了計算節點的初始退避窗口並動態調整，我們假設節點採用固定路由且每個 節點自身生成的數據量都相等，另外節點已經通過網絡層的路由過程獲知了它的一 跳鄰居及其負荷信息和目的節點的一跳鄰居及其負荷信息。基於上述假設，我們可以對標準CSMA/CA算法進行優化。本發明提出了多跳無 線傳感器網絡中基於動態比例公平的接入優化方法，其主要包括根據節點及其競 爭範圍(一跳鄰居及目的節點的一跳鄰居)內的節點的負荷計算第一次發送時的初 始退避窗口，然後在以後的每次發送中動態估計節點實際獲得的吞吐率及其競爭範 圍內所有節點實際獲得的吞吐率之和，根據這兩個值計算出一個比例公平性指數， 按照這個指數所在的範圍對初始退避窗口進行動態調整。最終實現了網絡中節點吞 吐率公平性的提高，系統丟包率的降低和飽和情況下節點吞吐率的提高。
權利要求
1.一種多跳無線傳感器網絡動態比例公平接入優化方法，其特徵在於該方法包括如下步驟a.第一次發送時首先，節點計算其最優發送概率<![CDATA[ i *= loadi load i+ load o , ]]>式中loadi為節點i的負荷，loado為節點i的競爭範圍內所有其它節點的負荷之和；其次，節點計算其偵聽到信道忙的概率<![CDATA[ p i=1- i=1 N C i ( 1 - i ); ]]>然後，節點計算其最優初始退避窗口
全文摘要
多跳無線傳感器網絡動態比例公平接入優化方法是一種適用於低複雜度，低成本，低功耗的環境監控，工業控制以及軍事偵察等領域的無線傳感器網絡的優化接入控制方法。首先根據節點的負荷估計其最優發送概率並由飽和狀態下退避過程的Markov模型推導出每個節點的最優初始退避窗口，然後根據節點實際獲得的吞吐率動態調整初始退避窗口以提高節點的流量公平性。在多跳網絡中節點負荷差別較大，靠近網關處節點成為網絡瓶頸的條件下取得了節點吞吐率流量公平性的較大提高並顯著降低了系統丟包率，在非飽和情況下網關節點的吞吐率也有較大提高。在網絡中節點負荷不均勻的情況下可以顯著提高節點的吞吐量公平性並降低丟包概率。
文檔編號H04Q7/36GK101252511SQ200810018830
公開日2008年8月27日 申請日期2008年1月25日 優先權日2008年1月25日
發明者劉俊平, 張榮標, 徐平平, 趙迎新, 黃齊波 申請人:東南大學