一種自適應負載均衡的代碼分發方法
2023-08-01 12:43:16 3
一種自適應負載均衡的代碼分發方法
【專利摘要】本發明公開了一種自適應負載均衡的代碼分發方法，本方法的主要思想是利用無線傳感器網絡冗餘鏈路和廣播特性的優勢，結合網絡編碼的特點，在整個分發過程中採用自適應編碼策略和分布式節點選擇機制。本方法大大提高了代碼分發的可靠性，實現負載均衡，並能減少代碼分發過程中數據包的傳輸次數和重傳次數，這意味著不僅能減少碰撞衝突所產生的丟包重傳，也能節省能量延長網絡的壽命。
【專利說明】一種自適應負載均衡的代碼分發方法
【【技術領域】】
[0001]本發明涉及到無線傳感器網絡重編程領域，尤其涉及代碼分發機制。
【【背景技術】】
[0002]近年來,無線傳感器網絡(Wireless Sensor Network, WSN)作為一種新興的網絡形式，自本世紀初開始被廣泛研究。無線傳感器網絡的一個很重要的優勢是能夠長期在無人監守的情況下執行監測任務。為了適應變化，在傳感器節點布置後，節點不可避免地要對已有的應用程式修改或增加新的應用程式，比如修復先前程序的漏洞、變更單一節點甚至是整個傳感器網絡的執行任務、以及修補安全漏洞。在這種背景下，無線傳感器網絡重編程技術產生了。無線傳感器網絡重編程技術主要是無線更新傳感器節點程序代碼，關注的焦點在於如何將新的程序代碼通過Sink節點無線多跳分發到各個傳感器節點，並保證所接收到的程序代碼鏡像文件是完整且準確無誤的。
[0003]目前國內外所提出的代碼分發協議大致可以分為兩類:經典代碼分發協議和基於網絡編碼的代碼分發協議。前者傳輸數據的方式是存儲轉發，即除了數據的發送和接收以外，不對原始數據做任何處理；而後者發送節點採用不同的編碼方式對發送數據進行編碼，接收節點需要經過解碼操作獲得原始數據。基於網絡編碼思想的代碼分發協議，相比傳統的經典代碼分發協議，減少了代碼分發過程的數據量和控制開銷，其基本原理如附圖=Sink節點A廣播2個數據包a和b。如果節點只是簡單地轉發他們收到的數據包，A、B、C則總共需要發送6個 包(每個2個包)。如果使用網絡編碼的思想，B、C節點在收到a、b兩個包後，選取隨機參數，對其進行線性編碼，圖中的a+b和a+2b，然後分別廣播這兩個包。節點E、D在接收到這兩個包後通過解簡單的線性方程就能解出a、b，獲得原始數據包。這樣一來總共減少了 2個數據包。
[0004]
[0005]
[0006]但這些協議並未針對WSN的動態變化特性做出相應的處理，以及沒有針對負載均衡問題提出有效地解決方法。眾所周知，無線傳感器網絡的環境始終是動態變化的:一、節點可能隨時斷開或失效；二、節點間的鏈路質量也隨著時間在不斷變化。一個好的代碼分發機制需要良好地適應這種動態變化。已有的基於網絡編碼的代碼分發協議，採用固定的編碼方式，在協議中事先規定好了編碼策略，在代碼分發的過程沒有考慮到節點失效或低鏈路質量的情況，不能較好地適應WSN環境的動態變化，所以在這種情況下可能會增加額外的代價；已有的協議旨在完成代碼鏡像文件的可靠性傳輸，而未對傳輸過程中負載均衡的問題進行深入探究，如果有些節點因為負載過度而導致能耗過快而死亡，不利於整個網絡的連通性和覆蓋率。
【
【發明內容】
】
[0007]有鑑於此，有必要提供一種自適應負載均衡的代碼分發方法。[0008]一種自適應負載均衡的代碼分發方法，其主要思想是，在整個代碼分發過程中採用自適應編碼策略和分布式節點選擇機制。
[0009]在優選的實施方式中，所述自適應編碼策略包括如下步驟:無線傳感器網絡中各節點接收鄰居節點的廣播信息；無線傳感器網絡中各節點更新自身的局部拓撲信息；無線傳感器網絡中各節點自適應確定編碼方案；
[0010]在優選的實施方式中，所述鄰居節點的廣播信息包括:數據傳輸信息，即編碼數據包(每個編碼數據包由若干個原始數據包通過隨機線性編碼算法生成)；請求重傳信息，即NACK(Negative Acknowledgement)消息。
[0011]在優選的實施方式中，所述無線傳感器網絡中各節點接收鄰居節點的廣播信息的方法是:設定定時器；判斷所收到的廣播信息是否為節點所需的編碼數據包；如果是，則重啟定時器；如果不是，則重複判斷所收到的廣播信息。
[0012]在優選的實施方式中，所述無線傳感器網絡中各節點更新自身的局部拓撲信息的方法是:節點維護一個「有效鄰居節點數S」(有效鄰居節點即已經解碼成功的鄰居節點)來表示節點的局部拓撲信息，S的初始化值為O ;節點每收到一個鄰居節點廣播的編碼數據包，便判斷之前是否已從該鄰居節點收到過所需的編碼數據包，如果未收到過，則需要更新S的值將其增I ;否則不更新。
[0013]在優選的實施方式中，所述無線傳感器網絡中各節點自適應確定編碼方案包括如下步驟:節點解碼成功獲得M個原始數據包；節點根據「有效鄰居節點數S」來確定一個N值；節點對每N個原始數據包採用隨機線性編碼算法，生成M/N個編碼數據包；節點廣播得到的M/N個編碼數據包。
[0014] 在優選的實施方式中，所述分布式節點選擇機制包括如下步驟:某個節點廣播NACK消息；鄰居節點接收NACK消息；某個滿足條件的鄰居節點響應該NACK消息，該鄰居節點被選擇。
[0015]在優選的實施方式中，所述某個節點廣播NACK消息包括:設定定時器；判斷定時器是否被觸發，如果定時器被觸發，廣播一個NACK消息並重新設定定時器，定時間隔為上一次的2倍；如果定時器沒有被觸發，則重複判斷定時器是否被觸發。
[0016]在優選的實施方式中，所述鄰居節點接收NACK消息的方法是:每個鄰居節點判斷是否已經解碼成功且含有所請求的信息；如果解碼成功且含有所請求的信息才響應該NACK消息；否則忽略該NACK消息，不響應；
[0017]在優選的實施方式中，所述某個滿足條件的鄰居節點響應該NACK消息，該鄰居節點被選擇，包括如下步驟:節點隨機迴避一段時間；在此期間若偵聽到其他節點正在響應這個NACK消息，則不響應；若沒有偵聽到其他鄰居節點正在響應這個消息，則發送請求節點所需的息。
[0018]上述代碼分發方法，提高了代碼分發的可靠性，實現負載均衡，並能減少代碼分發過程中數據包的傳輸次數和重傳次數，這意味著不僅能減少碰撞衝突所產生的丟包重傳，也能節省能量延長網絡的壽命。
【【專利附圖】
【附圖說明】】
附圖是隨機線性網絡編碼的示意圖。
【【具體實施方式】】[0019]自適應負載均衡的代碼分發方法按如下所述步驟實施:
[0020]I)無線傳感器網絡中各節點啟動一個定時器Timer，設置定時值為timerValue ；並維護一個「有效鄰居節點數S」，設置初值為O。
[0021]2)判斷定時器是否被觸發，如果定時器被觸發，則執行步驟11 ;如果定時器沒有被觸發，則執行步驟3。
[0022]3)接收鄰居節點的廣播信息，判斷所收到的廣播信息的類型。如果是節點所需的編碼數據包，則執行步驟4 ;如果是一個NACK消息，則執行步驟8。
[0023]4)節點判斷之前是否已從該鄰居節點收到過所需的編碼數據包，如果未收到過，則需要更新S的值將其增I ;否則不更新。
[0024]5)重新啟動定時器Timer。
[0025]6)節點判斷是否解碼成功，如果解碼成功，則執行步驟7 ;如果未成功解碼，轉至步驟3。
[0026]7)節點解碼成功後獲得M個原始數據包，節點根據「有效鄰居節點數S」來確定一個N值，並對每N個原始數據包採用隨機線性編碼算法，生成M/N個編碼數據包，然後廣播得到的M/N個編碼數據包。
[0027]8)節點在收到鄰居節點的NACK消息後，首先判斷是否已經解碼成功且含有所請求的信息；如果解碼成功且含有所請求的信息，則執行步驟9 ;否則，轉至步驟10 ；
[0028]9)節點隨機迴避一段時間，在此期間若偵聽到其他節點正在響應這個NACK消息，則執行步驟10 ;若沒有偵聽到其他鄰居節點正在響應這個消息，則發送請求節點所需的信
肩、O
[0029]10)節點忽略該NACK消息，不響應；轉至步驟3。
[0030]11)廣播一個NACK消息，並重新設定定時器Timer,設置定時值timerValue =2*timerValue ;轉至步驟 2。
【權利要求】
1.一種自適應負載均衡的代碼分發方法，其特徵在於，在整個代碼分發過程中採用自適應編碼策略和分布式節點選擇機制。
2.根據權利要求1所述的方法，其特徵在於，所述自適應編碼策略包括如下步驟: 無線傳感器網絡中各節點接收鄰居節點的廣播信息； 無線傳感器網絡中各節點更新自身的局部拓撲信息； 無線傳感器網絡中各節點自適應確定編碼方案。
3.根據權利要求2所述的自適應編碼策略，其特徵在於，所述鄰居節點的廣播信息包括: 數據傳輸信息，即編碼數據包(一個編碼數據包由若干個原始數據包通過隨機線性編碼算法生成)； 請求重傳信息，即 NACK(Negative Acknowledgement)消息。
4.根據權利要求2所述的自適應編碼策略，其特徵在於，所述無線傳感器網絡中各節點接收鄰居節點的廣播信息的方法是: 51:設定定時器； 52:判斷所收到的廣播信息是否為節點所需的編碼數據包，如果是，執行S3 ;如果否，執行S2 ； 53:重啟定時器。
5.根據權利要求2所述的自適應編碼策略，其特徵在於，所述無線傳感器網絡中各節點更新自身的局部拓撲信息的方法是: 節點維護一個「有效鄰居節點數S」 (有效鄰居節點即已經解碼成功的鄰居節點)來表示節點的局部拓撲信息，S的初始化值為O ;節點每收到一個鄰居節點廣播的編碼包，便判斷之前是否已從該鄰居節點收到過所需的編碼數據包，如果未收到過，則需要更新S的值將其增I;否則不更新。
6.根據權利要求2所述的自適應編碼策略，其特徵在於，所述無線傳感器網絡中各節點自適應確定編碼方案包括如下步驟: 節點解碼成功獲得M個原始數據包； 節點根據「有效鄰居節點數S」確定對應的N值； 節點對每N個原始數據包採用隨機線性編碼算法，生成M/N個編碼數據包； 節點廣播得到的M/N個編碼數據包。
7.根據權利要求1所述的方法，其特徵在於，所述分布式節點選擇機制包括如下步驟: 某個節點廣播NACK消息； 鄰居節點接收NACK消息； 某個滿足條件的鄰居節點響應該NACK消息，該鄰居節點被選擇。
8.根據權利要求7所述分布式節點選擇機制，其特徵在於，所述某個節點廣播NACK消息包括: 51:設定定時器； 52:判斷定時器是否被觸發，如果是，執行S3 ;如果否，執行S2 ； 53:廣播一個NACK消息並重新設定定時器，定時間隔為上一次的2倍。
9.根據權利要求7所述分布式節點選擇機制，其特徵在於，所述鄰居節點接收NACK消息的方法是: 每個鄰居節點判斷是否已經解碼成功且含有所請求的信息；如果解碼成功且含有所請求的信息才響應該NACK消息；否則忽略該NACK消息，不響應。
10.根據權利要求7所述分布式節點選擇機制，其特徵在於，所述某個滿足條件的鄰居節點響應該NACK消息，該鄰居節點被選擇，方法是: 節點隨機迴避一段時間；在此期間若偵聽到其他節點正在響應這個NACK消息，則不響應；若沒有偵聽到其他鄰居節點正在響應這個消息，則發送請求節點所需的信息。
11.根據權利要 求4和權利要求8所述的定時器，其必須是相同的定時器。
【文檔編號】H04L1/16GK104010328SQ201310061878
【公開日】2014年8月27日 申請日期:2013年2月22日 優先權日:2013年2月22日
【發明者】董楚楚, 於峰崎 申請人:中國科學院深圳先進技術研究院