[發(fā)明專利]一種基于帶寬自適應(yīng)代碼遷移的移動(dòng)設(shè)備節(jié)能方法

無(wú)效

• 申請(qǐng)?zhí)枺?/td>: 201210421845.9
• 申請(qǐng)日: 2012-10-30
• 公開(kāi)（公告）號(hào): CN102968173A
• 公開(kāi)（公告）日: 2013-03-13
• 發(fā)明（設(shè)計(jì)）人: 牛建偉;宋文芳
• 申請(qǐng)（專利權(quán)）人: 北京航空航天大學(xué)
• 主分類號(hào): G06F1/32
• 分類號(hào): G06F1/32;G06F9/44
• 代理公司: 北京永創(chuàng)新實(shí)專利事務(wù)所 11121
• 代理人: 周長(zhǎng)琪

1.一種基于帶寬自適應(yīng)代碼遷移的移動(dòng)設(shè)備節(jié)能方法，在移動(dòng)環(huán)境帶寬不斷變化的情況下，其特征在于，該移動(dòng)設(shè)備節(jié)能方法通過(guò)下面步驟實(shí)現(xiàn)：

步驟1：構(gòu)造加權(quán)對(duì)象關(guān)系圖，具體是：首先，進(jìn)行靜態(tài)程序分析，根據(jù)程序的方法調(diào)用關(guān)系，構(gòu)造程序初始的對(duì)象關(guān)系圖，對(duì)象關(guān)系圖中的各節(jié)點(diǎn)和邊分別對(duì)應(yīng)程序中的對(duì)象和對(duì)象間的調(diào)用關(guān)系；然后，通過(guò)動(dòng)態(tài)程序分析獲得對(duì)象關(guān)系圖中各節(jié)點(diǎn)對(duì)象的運(yùn)行時(shí)間以及每條邊的通信數(shù)據(jù)量，得到加權(quán)對(duì)象關(guān)系圖；

步驟2：基于加權(quán)對(duì)象關(guān)系圖，將帶寬作為一個(gè)變量，建立基于運(yùn)行時(shí)間和耗電量的程序分割優(yōu)化模型，具體是：令x_i標(biāo)識(shí)節(jié)點(diǎn)i的運(yùn)行位置，x_i=1和x_i=0分別表示節(jié)點(diǎn)i在移動(dòng)設(shè)備和服務(wù)器端運(yùn)行，程序分割方案表示為X＝{x₁,x₂,…,x_n}，n為加權(quán)對(duì)象關(guān)系圖中的節(jié)點(diǎn)個(gè)數(shù)，則程序分割優(yōu)化模型的目標(biāo)在于求得最優(yōu)分割方案滿足X_P為模型求解空間，b表示當(dāng)前帶寬，W(X,b)表示當(dāng)前帶寬為b時(shí)程序分割方案X的優(yōu)化模型，具體定義如下：

W(X,b)＝w_t×T(X,b)/T_Local+w_e×E(X,b)/E_Local

其中，T_Local和E_Local分別表示程序全部運(yùn)行在移動(dòng)設(shè)備的運(yùn)行時(shí)間和耗電量；w_t和w_e分別表示運(yùn)行時(shí)間和耗電量的權(quán)重，且滿足w_t+w_e＝1；T(X,b)和E(X,b)分別表示當(dāng)前帶寬為b時(shí)采用程序分割方案X的程序運(yùn)行時(shí)間和耗電量；

所述的模型求解空間X_P定義為：其中，帶寬閾值b_l為滿足概率P(b≥b_l)≥P_c的最大帶寬值，P_c為所設(shè)定的概率閾值；為帶寬b_l下最優(yōu)程序分割方案對(duì)應(yīng)的優(yōu)化模型值；經(jīng)驗(yàn)常數(shù)a＞0；

步驟3：進(jìn)行帶寬自適應(yīng)程序分割，在節(jié)點(diǎn)個(gè)數(shù)n不超過(guò)200時(shí)，采用分支定界程序分割方法尋找最優(yōu)分割方案，在節(jié)點(diǎn)個(gè)數(shù)n大于200時(shí)，采用基于最小割的貪心方法來(lái)尋找最優(yōu)分割方案；

所述的分支定界程序分割方法基于分支定界深度優(yōu)先搜索法，深度搜索的約束條件包括：

1）程序分割方案在當(dāng)前帶寬b下對(duì)應(yīng)的優(yōu)化模型值小于當(dāng)前保存的優(yōu)化模型的最小值；2）程序分割方案在帶寬閾值b_l下的模型目標(biāo)值不高于所設(shè)定模型上限值

所述的基于最小割的貪心方法，利用Stoer-Wagner最小割算法求得帶寬為b和b_l時(shí)對(duì)應(yīng)的運(yùn)行在移動(dòng)設(shè)備的節(jié)點(diǎn)集合C_b和運(yùn)行在服務(wù)器端的節(jié)點(diǎn)集合令待分割節(jié)點(diǎn)對(duì)V'中節(jié)點(diǎn)進(jìn)行分割，采用Stoer-Wagner最小割算法中的最大鄰接值排序算法對(duì)節(jié)點(diǎn)進(jìn)行排序，然后基于貪心策略，同時(shí)根據(jù)與分支定界程序分割方法中相同的深度搜索的約束條件選取最優(yōu)分割方案；

步驟4：根據(jù)得到的最優(yōu)分割方案，實(shí)現(xiàn)程序在移動(dòng)設(shè)備和服務(wù)器間的代碼遷移和分布式執(zhí)行。

2.根據(jù)權(quán)利要求1所述的一種基于帶寬自適應(yīng)代碼遷移的移動(dòng)設(shè)備節(jié)能方法，其特征在于，所述的概率閾值P_c設(shè)定為0.85。

3.根據(jù)權(quán)利要求1所述的一種基于帶寬自適應(yīng)代碼遷移的移動(dòng)設(shè)備節(jié)能方法，其特征在于，所述的經(jīng)驗(yàn)常數(shù)a設(shè)定為0.4。