[發(fā)明專利]一種用于移動社交網(wǎng)絡(luò)的任務(wù)負(fù)載平衡方法

無效

• 申請?zhí)枺?/td>: 201310479561.X
• 申請日: 2013-10-14
• 公開（公告）號: CN103514047A
• 公開（公告）日: 2014-01-15
• 發(fā)明（設(shè)計）人: 楊盤隆;李晴瑜;閆宇博;向朝參
• 申請（專利權(quán)）人: 中國人民解放軍理工大學(xué)
• 主分類號: G06F9/50
• 分類號: G06F9/50
• 代理公司: 南京瑞弘專利商標(biāo)事務(wù)所(普通合伙) 32249
• 代理人: 楊曉玲

技術(shù)領(lǐng)域

本發(fā)明涉及一種移動社交網(wǎng)絡(luò)中任務(wù)再分配的方法，它的使用可以有效的提高工作效率，節(jié)約設(shè)備能源。

背景技術(shù)

近年來，智能手機(jī)以及相關(guān)的應(yīng)用程序使用率顯著上升。眾包及群智感知的出現(xiàn)讓更多的遙感信息持有者無意識、自愿地進(jìn)行合作。在這樣的移動計算環(huán)境中，更深層次的協(xié)作是必要的。移動用戶在共享和重新分配他們自身不同數(shù)量的任務(wù)時，也要考慮剩余能量和計算能力的高低。例如，電池電量不足的用戶將他們的任務(wù)卸載到通信范圍內(nèi)具有較高電池電量的用戶身上，當(dāng)然，任務(wù)也應(yīng)該分配給具有高運算能力的節(jié)點。

然而，以往的研究工作，由于關(guān)注多用戶共享與眾包數(shù)據(jù)收集，導(dǎo)致無法在用戶之間實現(xiàn)負(fù)載均衡。這種情況下，有些用戶的隊列長度可能是非常高的，這將不可避免地導(dǎo)致能源的耗盡和長時間的延遲。根本原因在于，這些工作都專注于數(shù)據(jù)共享的效率，而不是分配用戶之間的負(fù)載平衡。

傳統(tǒng)的負(fù)載均衡方案不能直接應(yīng)用于移動社交網(wǎng)絡(luò)。因為在移動社交網(wǎng)絡(luò)中，信息收集和任務(wù)分配都是分布式的。集中式的方案將不可行，移動社交網(wǎng)絡(luò)特有的接觸時間短、任務(wù)排隊動態(tài)等特點也使得一些已有的分布式算法在保證用戶負(fù)載均衡這方面失效。

發(fā)明內(nèi)容

技術(shù)問題：本發(fā)明提出了一種用于移動社交網(wǎng)絡(luò)的任務(wù)負(fù)載平衡方法，任務(wù)重新分配方法能夠有效地將任務(wù)遷移到更合適的設(shè)備去執(zhí)行，提高工作效率的同時也節(jié)約了設(shè)備能源。

技術(shù)方案：本發(fā)明的一種用于移動社交網(wǎng)絡(luò)的任務(wù)負(fù)載平衡方法為：移動社交網(wǎng)絡(luò)中的用戶在分配任務(wù)時，每次只需挑選兩個或兩個以上個用戶中負(fù)載最小者，而相比于最優(yōu)分配即每次選擇用戶中負(fù)載最小者以及隨機(jī)分配即每次從用戶中任意選擇一個用戶的方法，既不用知曉全局信息又能很好地達(dá)到用戶間的負(fù)載平衡，所述方法包括以下步驟：

1)在每個時隙中，每個用戶判斷其他用戶是否在通信范圍內(nèi)；

2)從通信范圍內(nèi)的所有用戶中任意挑選若干個用戶；

3)比較已挑選用戶的負(fù)載，找出用戶中負(fù)載最低者；

4)將任務(wù)分配給負(fù)載最低者；

5)若沒有用戶在通信范圍內(nèi)，等待下一個時隙的分配；

6)當(dāng)一個時隙內(nèi)所有用戶都將任務(wù)分配完，則開始下一時隙的分配；

7)結(jié)束。

在步驟1)中，

n個用戶在有限的地區(qū)進(jìn)行隨機(jī)游走，其中r為每個移動用戶的通信半徑，當(dāng)兩個節(jié)點都在相互的通信范圍內(nèi)時，任務(wù)可以被重新分配，判斷是否在通信范圍內(nèi)的依據(jù)是：

(X_i-X_j)²+(Y_i-Y_j)²＜r²

其中(X_i,Y_i)和(X_j,Y_j)分別為用戶i和用戶j的位置坐標(biāo)，如果上式成立則表明用戶i和用戶j在通信范圍內(nèi)，可以進(jìn)行信息交換和任務(wù)的再分配，如果上式不成立則標(biāo)記用戶i和用戶j不能通信。

用戶間的負(fù)載平衡，是指任務(wù)的均勻分布，最大限度地減少每一個用戶間隊列長度的差異，可由下式給出：

minΣi∈U|Qi-E[Qi]|]]>

其中，U={1,2,...n}為用戶集合，i∈U表示用戶i屬于集合U，Q_i表示用戶i的隊列長度，E[·]是隨機(jī)變量的平均值，min為取表達(dá)式的最小值。

有益效果：本發(fā)明與現(xiàn)有技術(shù)相比，其顯著優(yōu)點是:它是純分布式環(huán)境下的任務(wù)負(fù)載平衡，結(jié)合考慮能量水平和計算能力，可以應(yīng)用到異構(gòu)的移動社交網(wǎng)絡(luò)中。實現(xiàn)起來十分簡單，且當(dāng)d=2時已能達(dá)到很好的負(fù)載平衡效果。

附圖說明

圖1是任務(wù)再分配的基本場景。

圖2-圖5是通信半徑對本方法影響的仿真分析。

圖6-圖8是任務(wù)權(quán)重對本方法影響的仿真分析。