一種用於移動社交網絡的任務負載平衡方法
2023-05-10 12:38:46 1
一種用於移動社交網絡的任務負載平衡方法
【專利摘要】本發明公開了一種用於移動社交網絡的任務負載平衡方法，該方法包括以下步驟：1、在每個時隙中，每個用戶判斷其他用戶是否在通信範圍內；2、從通信範圍內的所有用戶中任意挑選d個用戶；3、比較d個用戶的負載；4、將任務分配給d個用戶中負載最低者；5、若通信範圍內用戶不足d個，將任務分配給其中負載最低者；6、若沒有用戶在通信範圍內，等待下一個時隙的分配；7、當一個時隙內所有用戶都將任務分配完，則開始下一時隙的分配；8結束。本發明是純分布式環境下的任務負載平衡，結合考慮能量水平和計算能力，可以應用到異構的移動社交網絡中。實現起來十分簡單，且當d=2時已能達到很好的負載平衡效果。
【專利說明】一種用於移動社交網絡的任務負載平衡方法
【技術領域】
[0001]本發明涉及一種移動社交網絡中任務再分配的方法，它的使用可以有效的提高工作效率，節約設備能源。
【背景技術】
[0002]近年來，智慧型手機以及相關的應用程式使用率顯著上升。眾包及群智感知的出現讓更多的遙感信息持有者無意識、自願地進行合作。在這樣的移動計算環境中，更深層次的協作是必要的。移動用戶在共享和重新分配他們自身不同數量的任務時，也要考慮剩餘能量和計算能力的高低。例如，電池電量不足的用戶將他們的任務卸載到通信範圍內具有較高電池電量的用戶身上，當然，任務也應該分配給具有高運算能力的節點。
[0003]然而，以往的研究工作，由於關注多用戶共享與眾包數據收集，導致無法在用戶之間實現負載均衡。這種情況下，有些用戶的隊列長度可能是非常高的，這將不可避免地導致能源的耗盡和長時間的延遲。根本原因在於，這些工作都專注於數據共享的效率，而不是分配用戶之間的負載平衡。
[0004]傳統的負載均衡方案不能直接應用於移動社交網絡。因為在移動社交網絡中，信息收集和任務分配都是分布式的。集中式的方案將不可行，移動社交網絡特有的接觸時間短、任務排隊動態等特點也使得一些已有的分布式算法在保證用戶負載均衡這方面失效。
【發明內容】
[0005]技術問題:本發明提出了一種用於移動社交網絡的任務負載平衡方法，任務重新分配方法能夠有效地將任務遷移到更合適的設備去執行，提高工作效率的同時也節約了設備能源。
[0006]技術方案:本發明的一種用於移動社交網絡的任務負載平衡方法為:移動社交網絡中的用戶在分配任務時，每次只需挑選兩個或兩個以上個用戶中負載最小者，而相比於最優分配即每次選擇用戶中負載最小者以及隨機分配即每次從用戶中任意選擇一個用戶的方法，既不用知曉全局信息又能很好地達到用戶間的負載平衡，所述方法包括以下步驟:
[0007]I)在每個時隙中，每個用戶判斷其他用戶是否在通信範圍內；
[0008]2)從通信範圍內的所有用戶中任意挑選若干個用戶；
[0009]3)比較已挑選用戶的負載，找出用戶中負載最低者；
[0010]4)將任務分配給負載最低者；
[0011]5)若沒有用戶在通信範圍內，等待下一個時隙的分配；
[0012]6)當一個時隙內所有用戶都將任務分配完，則開始下一時隙的分配；
[0013]7)結束。
[0014]在步驟I)中，
[0015]η個用戶在有限的地區進行隨機遊走，其中r為每個移動用戶的通信半徑，當兩個節點都在相互的通信範圍內時，任務可以被重新分配，判斷是否在通信範圍內的依據是:
[0016](X1-Xj)2+ (Y1-Yj)2 < r2
[0017]其中(Xi, Yi)和％，Yj)分別為用戶i和用戶j的位置坐標，如果上式成立則表明用戶i和用戶j在通信範圍內，可以進行信息交換和任務的再分配，如果上式不成立則標記用戶i和用戶j不能通信。
[0018]用戶間的負載平衡，是指任務的均勻分布，最大限度地減少每一個用戶間隊列長度的差異，可由下式給出:
【權利要求】
1.一種用於移動社交網絡的任務負載平衡方法，其特徵在於，移動社交網絡中的用戶在分配任務時，每次只需挑選兩個或兩個以上個用戶中負載最小者，而相比於最優分配即每次選擇用戶中負載最小者以及隨機分配即每次從用戶中任意選擇一個用戶的方法，既不用知曉全局信息又能很好地達到用戶間的負載平衡，所述方法包括以下步驟: .1)在每個時隙中，每個用戶判斷其他用戶是否在通信範圍內；. 2)從通信範圍內的所有用戶中任意挑選若干個用戶； . 3)比較已挑選用戶的負載，找出用戶中負載最低者； . 4)將任務分配給負載最低者； .5)若沒有用戶在通信範圍內，等待下一個時隙的分配； . 6)當一個時隙內所有用戶都將任務分配完，則開始下一時隙的分配； . 7)結束。
2.根據權利要求1所述的一種用於移動社交網絡的任務負載平衡方法，其特徵是:在步驟I)中， η個用戶在有限的地區進行隨機遊走，其中r為每個移動用戶的通信半徑，當兩個節點都在相互的通信範圍內時，任務可以被重新分配，判斷是否在通信範圍內的依據是:(X1-Xj)^(Y1-Yj)2 < r2 其中(Xji)和(Xy YP分別為用戶i和用戶j的位置坐標，如果上式成立則表明用戶i和用戶j在通信範圍內，可以進行信息交換和任務的再分配，如果上式不成立則標記用戶i和用戶j不能通信。
3.根據權利要求1所述的一種用於移動社交網絡的任務負載平衡方法，其特徵是: 用戶間的負載平衡，是指任務的均勻分布，最大限度地減少每一個用戶間隊列長度的差異，可由下式給出:
【文檔編號】G06F9/50GK103514047SQ201310479561
【公開日】2014年1月15日 申請日期:2013年10月14日 優先權日:2013年10月14日
【發明者】楊盤隆, 李晴瑜, 閆宇博, 向朝參 申請人:中國人民解放軍理工大學