基於量化無偏廣播Gossip算法的分布式負載均衡方法
2023-05-19 01:43:01
基於量化無偏廣播Gossip算法的分布式負載均衡方法
【專利摘要】基於量化無偏廣播Gossip算法的分布式負載均衡方法，本發明涉及分布式負載均衡方法。本發明是要解決分布式共識，具體為分布式負載均衡問題從而提出了經過量化的無偏廣播Gossip算法。一、對節點狀態值進行初始化並設置無線傳感器網絡的同步時鐘和最大迭代次數；二、無偏廣播Gossip算法的迭代和量化過程；三、當迭代次數達到預設最大迭代次數時，結束迭代；此時無線傳感器網絡中所有節點負載達到均衡，即完成基於量化無偏廣播Gossip算法的分布式負載均衡方法。本發明應用於通信領域。
【專利說明】基於量化無偏廣播Gossip算法的分布式負載均衡方法
【技術領域】
[0001]本發明涉及分布式負載均衡方法。
【背景技術】
[0002]Gossip算法在1984年由Tsitsiklis等人首次提出，該算法僅利用網絡節點的本地信息和其鄰居節點信息進行數據交換，解決了分布式條件下的平均共識問題。在實際的數字通信鏈路中，由於測量值的精度和通信信道容量的限制，以及有限的節點存儲容量使得對節點信息進行量化成為必要。
[0003]隨著無線技術的發展，無線傳感器網絡應運而生。無線傳感器網絡就是由大量具有無線通信、數據採集和處理、協同合作等功能的傳感器節點協同組織起來的簡單傳感器網絡。它是一個通過無線通信方式形成的一個多跳的自組織的網絡系統，其作用是協作和感知、採集和處理網絡覆蓋區域中感知對象的信息，並將該信息發送給觀察者。因此無線傳感器網絡為人們提供最直接、最有效、最真實的信息，具有快速部署、抗毀性強、實時性等特點，有著越來越廣泛的應用前景。
[0004]在無線傳感器網絡中，分布式平均共識問題是一個具有挑戰性的基礎性問題。平均共識指的是網絡根據各個節點的初始狀態通過信息的交換使各個節點最終達到一致狀態的過程。在工程應用中，很多實際問題最終都能夠轉化成平均共識問題，例如源定位問題、同步問題，以及在並行計算機或分布式網絡中存在的負載均衡問題。負載均衡是指將負載(工作任務)進行平衡、分攤到多個網絡節點或設備上進行執行，從而共同完成工作任務。由於現有網絡的各個核心部分隨著業務量的提高，訪問量和數據流量的快速增長，其處理能力和計算強度也相應地增大，使得單一的伺服器或網絡節點設備根本無法承擔。在此情況下，如果扔掉現有設備去做大量的硬體升級，這樣將造成現有資源的浪費，而且如果再面臨下一次業務量的提升時，這又將導致再一次硬體升級的高額成本投入，甚至性能再卓越的設備也不能滿足當前業務量增長的需求，因此網絡節點間的負載均衡過程很有必要。
[0005]由此可以看出，如何有效的解決分布式平均共識問題具有重要的實際應用價值。隨著通信基礎理論研究的不斷深入，平均共識問題在國際學術界得到了廣泛的關注，對於平均共識問題的研究取得了許多成果。其中，基於Gossip算法的平均共識問題在無線傳感器網絡中的應用更是研究的熱點。該算法通過相鄰節點間的信息交換，可以最終使網絡中的所有節點獲得它們信息的平均值。儘管國內外已經有很多關於無線傳感器網絡Gossip算法方面的研究成果，但是以前的研究主要側重於成對Gossip算法(Pairwise GossipAlgorithm)和地理 Gossip 算法(Geographic Gossip Algorithm)的研究。這兩類算法由於在每次更新時只有選定的節點進行數據交換，因此儘管可以使共識收斂於均值，但是卻只能用於雙向鏈路，沒有很好的利用無線信道的廣播特性。直到最近幾年，國際上才出現了對於廣播Gossip算法(Broadcast Gossip Algorithm BGA)的研究。這類算法中當一個節點廣播它的數據時，所有能接收到該數據的節點均可以更新它們的數據。由於不需要反向數據交換，所以這類算法更適合於非對稱的無線信道。同時，由於每次數據更新有更多的節點參與，因此這類算法的收斂速度更快。此外，由於廣播Gossip算法不再需要隨機選擇相鄰節點，從而使算法更加簡單並易於實現。
[0006]具體到負載均衡問題，由於數字通信鏈路的信道容量限制以及傳感器節點有限的存儲能力，需要在共識過程中引入量化步驟，稱為量化共識。
【發明內容】
[0007]本發明是要解決分布式共識，具體為分布式負載均衡問題從而提出了經過量化的無偏廣播Gossip算法。
[0008]基於量化無偏廣播Gossip算法的分布式負載均衡方法包括以下步驟:
[0009]一、對節點狀態值進行初始化並設置無線傳感器網絡的同步時鐘和最大迭代次數；
[0010]二、無偏廣播Gossip算法的迭代和量化過程；
[0011]三、當迭代次數達到預設最大迭代次數時，結束迭代；此時無線傳感器網絡中所有節點負載達到均衡，即完成基於量化無偏廣播Gossip算法的分布式負載均衡方法。
[0012]發明效果
[0013]本發明涉及一種分布式負載均衡技術，具體利用量化的廣播Gossip算法，通過網絡節點的本地信息和其鄰近節點信息重新分配網絡中排隊等候需要處理的任務，使得最終需要每個節點處理任務的數量幾乎相同，從而達到分布式負載均衡的目的。該技術能夠保證網絡中所有節點最終達到共識狀態。
[0014]因此本發明提出一種基於量化廣播Gossip算法的負載均衡技術。通過性能仿真證明量化廣播Gossip算法可以達到共識狀態，能夠達到負載均衡的目的。
[0015]在無偏廣播Gossip 算法(Unbiased broadcast gossip algorithms UBGAs)中，網絡中的一個節點隨機地被激活，並將自己的狀態值進行本地廣播。所有該節點的相鄰節點都可以接收到該狀態值，並和自己的本地狀態值進行加權平均。計算後的結果替換掉自己原來的狀態信息，就完成了一次更新或一次迭代。在這種方式下，每進行一次迭代就可以使多個節點進行狀態值的更新，並且不需要發送自己的狀態值給廣播節點。這能夠克服成對Gossip算法收斂緩慢的缺點，對無線通信的應用更有意義。
【專利附圖】
【附圖說明】
[0016]圖1是本發明流程圖；
[0017]圖2是仿真實驗中本發明在100個節點場景下的收斂誤差r(t)仿真結果圖；
[0018]圖3是仿真實驗中本發明在100個節點場景下的收斂速度q(t)仿真結果圖；
[0019]圖4是仿真實驗中本發明在500個節點場景下的收斂誤差r(t)仿真結果圖；
[0020]圖5是仿真實驗中本發明在500個節點場景下的收斂速度q(t)仿真結果圖。
【具體實施方式】
[0021]【具體實施方式】一:本實施方式的基於量化無偏廣播Gossip算法的分布式負載均衡方法包括以下步驟:
[0022]一、對節點狀態值進行初始化並設置無線傳感器網絡的同步時鐘和最大迭代次數；
[0023]二、無偏廣播Gossip算法的迭代和量化過程；
[0024]三、當迭代次數達到預設最大迭代次數時，結束迭代；此時無線傳感器網絡中所有節點負載達到均衡，即完成基於量化無偏廣播Gossip算法的分布式負載均衡方法。
[0025]【具體實施方式】二:本實施方式與【具體實施方式】一不同的是:所述步驟一具體為:
[0026](一)將無線傳感器網絡作為一個隨機的幾何圖模型G(N，R)，N代表傳感器節點個數，R為連通半徑，N個傳感器節點均勻地分布在網絡中；這N個傳感器節點的拓撲結構用NXN的相鄰矩陣A表示，如果兩個節點i和j間的歐氏距離小於傳輸半徑R，則認為兩個節點是彼此相鄰的，可以直接通信，則令Aij = I ;否則，兩個節點是不相鄰的，不能直接進行通信，則令Aij = O ;當i = j時，i和j代表同一個節點,則令Aij = O ;令Ni = {j e {I, 2,…，N} IAij幸0}表示節點i的所有相鄰節點；
[0027](二)無線傳感器網絡中的每個節點i保存有兩個變量，一個是當前網絡狀態平均值的估計值Xi⑴，另一個為伴隨變量Ji⑴；由傳感器測得的每個節點的初始狀態值Xi (O)為初始時刻每個節點i的負載數量，並設置伴隨變量Yi(O) = O ;同時採用量化算法Q(.)對\(0)進行量化得到量化後的初始值i,(O);
[0028](三)在無線傳感器網絡中設置統一定時器，所述定時器的計數值滿足指數分布，同時設置最大迭代次數。
[0029]其它步驟及參數與【具體實施方式】一相同。
[0030]【具體實施方式】三:本實施方式與【具體實施方式】一或二不同的是:所述步驟二中無偏廣播Gossip算法的迭代和量化過程具體為:
[0031]I)啟動定時器，開始計時:當開始本輪迭代時，判斷當前迭代次數是否已達到最大值，若未達到最大值，則進入本輪迭代過程；若已達到最大值，則退出迭代過程；
[0032]2)在本輪迭代過程中，判斷節點的定時器計數值是否已滿:若在時刻t節點k的計時期滿則該節點被隨機喚醒，否則節點不會被喚醒並進入等待接收狀態；被喚醒的節點
k向全網廣播它的當前量化狀態值Λ(0和量化伴隨變量值A⑴，同時節點k更新t+i時刻
自己的最終狀態值為h O +1) = Xk(t)，鮮+1) = (h
[0033]3)判斷其他未被喚醒的節點是否會在t時刻接收到節點k的廣播信息:若未接收到節點k的廣播信息，令這些節點為，則進入步驟4);若接收到節點k的廣播信
息，令這些節點為e N；,則這些節點按照以下方法更新自己t+Ι時刻的狀態信息Xj (t+1)和 y」(t+1):
【權利要求】
1.基於量化無偏廣播Gossip算法的分布式負載均衡方法，其特徵在於基於量化無偏廣播Gossip算法的分布式負載均衡方法包括以下步驟: 一、對節點狀態值進行初始化並設置無線傳感器網絡的同步時鐘和最大迭代次數； 二、無偏廣播Gossip算法的迭代和量化過程； 三、當迭代次數達到預設最大迭代次數時，結束迭代；此時無線傳感器網絡中所有節點負載達到均衡，即完成基於量化無偏廣播Gossip算法的分布式負載均衡方法。
2.根據權利要求1所述的基於量化無偏廣播Gossip算法的分布式負載均衡方法，其特徵在於所述步驟一具體為: (一)將無線傳感器網絡作為一個隨機的幾何圖模型G(N，R)，N代表傳感器節點個數，R為連通半徑，N個傳感器節點均勻地分布在網絡中；這N個傳感器節點的拓撲結構用NXN的相鄰矩陣A表示，如果兩個節點i和j間的歐氏距離小於傳輸半徑R，則認為兩個節點是彼此相鄰的，可以直接通信，則令Aij = I ;否則，兩個節點是不相鄰的，不能直接進行通信，則令Aij = O ;當i = j時，i和j代表同一個節點,則令Aij = O ;令Ni = {j e {I, 2,…，N} IAij幸0}表示節點i的所有相鄰節點； (二)無線傳感器網絡中的每個節點i保存有兩個變量，一個是當前網絡狀態平均值的估計值\(0，另一個為伴隨變量yi(t);由傳感器測得的每個節點的初始狀態值Xi(O)為初始時刻每個節 點i的負載數量，並設置伴隨變量Yi(O) = O ;同時採用量化算法Q(.)對Xi(O)進行量化得到量化後的初始值4(0); (三)在無線傳感器網絡中設置統一定時器，所述定時器的計數值滿足指數分布，同時設置最大迭代次數。
3.根據權利要求2所述的基於量化無偏廣播Gossip算法的分布式負載均衡方法，其特徵在於所述步驟二中無偏廣播Gossip算法的迭代和量化過程具體為: 1)啟動定時器，開始計時:當開始本輪迭代時，判斷當前迭代次數是否已達到最大值，若未達到最大值，則進入本輪迭代過程；若已達到最大值，則退出迭代過程； 2)在本輪迭代過程中，判斷節點的定時器計數值是否已滿:若在時刻t節點k的計時期滿則該節點被隨機喚醒，否則節點不會被喚醒並進入等待接收狀態；被喚醒的節點k向全網廣播它的當前量化狀態值-?(O和量化伴隨變量值Λ W，同時節點k更新t+Ι時刻自己的最終狀態值為，Λ(/+?) = ο ； 3)判斷其他未被喚醒的節點是否會在t時刻接收到節點k的廣播信息:若未接收到節點k的廣播信息，令這些節點為I'eAuW ,則進入步驟4);若接收到節點k的廣播信息，令這些節點為JeiVi'，則這些節點按照以下方法更新自己t+Ι時刻的狀態信息\(t+l)和yj(t+1):
4.根據權利要求3所述的基於量化無偏廣播Gossip算法的分布式負載均衡方法，其特徵在於所述無偏廣播Gossip算法的量化過程具體為: (一)無偏廣播Gossip算法 當某節點k在t時刻被激活時，它將會把它的這兩個變量值Xk(t)和yk(t)同時廣播給它的相鄰節點J'e Wi'?所有ie 節點收到這兩個狀態值並按如下規則更新自己的狀態信息
【文檔編號】H04W28/08GK104010329SQ201410270299
【公開日】2014年8月27日 申請日期:2014年6月17日 優先權日:2014年6月17日
【發明者】吳少川, 牛麗娟, 潘斯琦, 馬康健 申請人:哈爾濱工業大學