GCTMHA:基于啟發(fā)式群組命令傳輸模型

章　剛，陳慶奎，2

(1.上海理工大學(xué)管理學(xué)院，上海200093; 2.上海理工大學(xué)光電信息與計(jì)算機(jī)工程學(xué)院，上海200093)

?

GCTMHA:基于啟發(fā)式群組命令傳輸模型

章剛1，陳慶奎1，2

(1.上海理工大學(xué)管理學(xué)院，上海200093; 2.上海理工大學(xué)光電信息與計(jì)算機(jī)工程學(xué)院，上海200093)

摘要：Internet盡力而為的服務(wù)模式在支持群組命令傳輸過程中，容易產(chǎn)生命令之間路徑競(jìng)爭(zhēng).定義出有效路徑統(tǒng)計(jì)網(wǎng)絡(luò)，并進(jìn)一步定義出基于有效路徑統(tǒng)計(jì)網(wǎng)絡(luò)的群組多約束多目標(biāo)優(yōu)化問題.針對(duì)該問題，提出基于啟發(fā)式群組命令傳輸模型.實(shí)驗(yàn)從群組命令傳輸成功率驗(yàn)證該模型對(duì)支持群組命令傳輸?shù)暮侠硇?

關(guān)鍵詞：群組命令傳輸;群組多約束多目標(biāo)優(yōu)化;啟發(fā)式算法

ZHANG Gang1，CHEN Qing-kui1，2
(1.Business School，University of Shanghai for Science and Technology，Shanghai 200093，China; 2.School of Optical-Electrical and Computer Engineering，University of Shanghai for Science and Technology，Shanghai 200093，China)

Abstract:The Internet with best-effort service for group command transmission produces path competition between commands easily.This paper firstly defines effective path statistics network(EPSN)based on Internet，and defines the group multi-constraints multi-objectives optimization problem based on the EPSN further.Aiming at the problem，this paper puts forward to the model GCTMHA(Group Command Transmission Model based on Heuristic Algorithm).The experiment verifies the reasonableness of the model from transmission success rate.

Key words:group command transmission;group multi-constraints multi-objectives optimization problem;heuristic algorithm

1　引言

物聯(lián)網(wǎng)運(yùn)營(yíng)中心(中心)作為物聯(lián)網(wǎng)“可控”思想的核心技術(shù)已經(jīng)受到各行各業(yè)的重視［1］.其主要功能是使得一組具有多約束的命令能夠通過Internet網(wǎng)絡(luò)全部傳輸?shù)椒稚⒃诓煌髤^(qū)域(跨省、市、區(qū))的終端設(shè)備.在傳輸過程中，任何單一命令傳輸丟失，都被視為群組命令傳輸失敗.中心本質(zhì)是基于Internet網(wǎng)絡(luò)的群組命令傳輸(Group Command Transmission，GCT)過程.

然而，Internet盡力而為的服務(wù)模式并不支持GCT傳輸.主要原因是，Internet為GCT中每個(gè)命令提供路徑，容易產(chǎn)生多個(gè)命令競(jìng)爭(zhēng)同一路徑，當(dāng)該路徑無法同時(shí)滿足所有命令需求時(shí)，會(huì)造成網(wǎng)絡(luò)擁塞.

當(dāng)前，針對(duì)GCT問題的研究鮮為人見［2］.文獻(xiàn)［3］提出一種權(quán)值非負(fù)無環(huán)K條最短路徑算法(KSPR)，該算法通過啟發(fā)式枚舉策略使得尋找K條最短路徑的時(shí)間復(fù)雜度為線性復(fù)雜度.Liu［4］提出一種多約束K-shortest路徑算法KMCSP，該算法在每次迭代過程中，通過路徑代價(jià)函數(shù)評(píng)估前K條最短路徑.但以上算法在面對(duì)GCT問題時(shí)依然存在路徑競(jìng)爭(zhēng)可能.針對(duì)此，本文在Internet上配置一些通信服務(wù)代理(Communication Service Agent，CSA)，通過CSA構(gòu)建有效路徑統(tǒng)計(jì)網(wǎng)絡(luò)(Effective Path Statistics Network，EPSN)，并構(gòu)建有效路徑EP(Effective Path，EP)集，進(jìn)而基于EP集支持GCT傳輸過程.

EPSN網(wǎng)絡(luò)構(gòu)建意義在于，通過測(cè)量與統(tǒng)計(jì)手段實(shí)時(shí)挖掘出Internet路徑上的有效“空隙”(EP集)，利用這些有效“空隙”(EP集)更好地實(shí)施GCT傳輸過程.

在GCT中，每個(gè)單一命令傳輸過程都可以看成是多約束多目標(biāo)優(yōu)化問題(Multi-Constraints Multi-Objectives Optimization Problem，MCMOOP).對(duì)GCT而言，其可以看成是群組多約束多目標(biāo)優(yōu)化問題(Group Multi-Constraints Multi-Objectives Optimization Problem，GMCMOOP).

綜上，本文主要考慮的問題是，基于EPSN網(wǎng)絡(luò)的GMCMOOP問題.

2　問題描述

設(shè)G =(V，E)表示為EPSN網(wǎng)絡(luò)，其中V為CSA集合，E為CSA之間鏈路集合，每條鏈路e∈E上都擁有一組度量參數(shù)j(j = 1，2，…)，fj表示參數(shù)j所對(duì)應(yīng)的子目標(biāo)函數(shù)，現(xiàn)給定一組子目標(biāo)函數(shù)fj(j = 1，2，…)的約束值Cj(j =1，2，…)，則:

基于EPSN網(wǎng)絡(luò)MCMOOP建模:在EPSN上尋找一組非劣解x，在x所對(duì)應(yīng)的每個(gè)分量子目標(biāo)函數(shù)fj(x)(j =1，2，…)滿足其約束Cj(j = 1，2，…)條件下，使得當(dāng)前MCMOOP問題總體目標(biāo)函數(shù)f(x)最優(yōu):

其中，GEP表示滿足式(1)的非劣解集，EP表示基于測(cè)量與統(tǒng)計(jì)的有效路徑集.

基于EPSN網(wǎng)絡(luò)GMCMOOP建模:尋找多組不相交的非劣解集GEP1，GEP2，…，且使得任意GEPj，j = 1，2，…，滿足式(1):

其中F表示當(dāng)前GMCMOOP問題總體目標(biāo)函數(shù)，F(xiàn)j表示第j個(gè)MCMOOP問題，GEPj表示MCMOOPj的非劣解集.

3　GCTMHA模型

GCTMHA主要思想:轉(zhuǎn)化GMCMOOP問題為資源分配問題(Resource Allocation Problem，RAP).引入0 -1整型規(guī)劃建立模型，并針對(duì)0 -1整型規(guī)劃計(jì)算問題的解.

3.1RAP問題描述

給定任務(wù)集mf，其中每個(gè)元素表示為命令請(qǐng)求，任務(wù)消耗量集U(mf)表示任務(wù)集合mf對(duì)應(yīng)的消耗量集，資源量集H(EP)表示有效路徑集EP對(duì)應(yīng)的資源量，函數(shù)Θ(U(mfi)，H(EPj))表示任務(wù)mfi，i =1，2，…的消耗量與有效路徑EPj，j = 1，2，…的資源量之間的匹配度，且Θ(U(mfi)，H(EPj))根據(jù)切比雪夫距離計(jì)算:

式(3)中，k為維數(shù)變量，ν為參數(shù).

RAP問題描述:尋找一種分配方案，在一個(gè)任務(wù)只能被一個(gè)有效路徑資源所處理，同時(shí)一個(gè)有效路徑資源也只能處理一個(gè)任務(wù)情況下，使得U(mf)與H(EP)之間的匹配度Θ(U(mf)，H(EP))最大.

3.20-1整型規(guī)劃建模

設(shè)引入0 -1變量xij，i，j =1，2，…

其中，xij= 1表示U(mfi)被H(EPj)處理，則0 - 1整型規(guī)劃模型:

3.3GCTMHA模型實(shí)現(xiàn)

Step 1:初始化GMCMOOP問題及相關(guān)參數(shù)，根據(jù)式(3)及式(4)，構(gòu)建0 -1整型規(guī)劃模型.設(shè)定沖突對(duì)集合CF、沖突標(biāo)識(shí)集合CF-S，同時(shí)初始化CF、CF-S，CF中每個(gè)元素為存在沖突的有效路徑構(gòu)成的N元組N≥2，CF-S中每個(gè)元素為CF中對(duì)應(yīng)元素的狀態(tài)值，轉(zhuǎn)入Step 2;

Step 2:初始化?i，U(mfi)，i = 1，2，…和?j，H(EPj)，j =1，2，…，對(duì)于?i，U(mfi)，i =1，2，…計(jì)算其與?j，H(EPj)，j = 1，2，…之間匹配度Θ(U(mfi)，H(EPj))，i，j =1，2，…，根據(jù)計(jì)算結(jié)果建立?i，U(mfi)，i =1，2，…的匹配度集合SWAP并進(jìn)行從大到小排序，轉(zhuǎn)入Step 3;

Step 3:從任務(wù)U(mf1)到任務(wù)U(mfn)，分別依次從所對(duì)應(yīng)的匹配排序集合SWAP中分別提取出與當(dāng)前最大匹配度Θ，并根據(jù)此產(chǎn)生一組解集s(EP)，解集s(EP)中每個(gè)元素為匹配度Θ對(duì)應(yīng)的有效路徑，轉(zhuǎn)入Step 4;

Step 4:把解集s(EP)代入到0 -1整型規(guī)劃模型約束中，若此解集滿足約束條件，轉(zhuǎn)入Step 7;否則轉(zhuǎn)入Step 5;

Step 5:從當(dāng)前解集s(EP)中依次選定不滿足約束及產(chǎn)生沖突的有效路徑，存入沖突對(duì)集合CF，轉(zhuǎn)入Step 6;

Step 6:依次從CF每個(gè)元素中，隨機(jī)選中沖突有效路徑，并設(shè)置其CF-S值為已選，分別找到對(duì)應(yīng)的匹配度集，從對(duì)應(yīng)的匹配度集中分別選擇次優(yōu)值，產(chǎn)生一組子解集s'(EP)，將s'(EP)替換CF中已選的有效路徑，判定CF是否存在未選的沖突有效路徑，如果是，轉(zhuǎn)入Step6;否則，利用CF更新s(EP)中存在沖突的有效路徑解，并設(shè)置CF中所有有效路徑的CF-S值為未選，轉(zhuǎn)入Step 4;

Step 7:記錄當(dāng)前有效解并退出.

4　實(shí)驗(yàn)與分析

實(shí)驗(yàn)環(huán)境:曙光集群20個(gè)服務(wù)器及利用Waxmam模型［5］隨機(jī)生成的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu).其中，隨機(jī)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)具有20個(gè)節(jié)點(diǎn)，28條鏈路，并在每條鏈路上隨機(jī)產(chǎn)生n，n≥2個(gè)度量參數(shù).

群組命令規(guī)模:通過統(tǒng)計(jì)與分析，群組命令規(guī)模平均最小和最大值分別為50、150.

測(cè)試性能:驗(yàn)證EPSN網(wǎng)絡(luò)規(guī)模不斷變化下，不同算法之間的GCT傳輸成功率(Transmission Success，TS)性能比較: TS =傳輸成功數(shù)/傳輸總數(shù).

圖1中，橫坐標(biāo)表示EPSN規(guī)模，縱坐標(biāo)表示傳輸成功率.當(dāng)EPSN規(guī)模數(shù)為5～10時(shí)，GCTMHA傳輸成功率接近71%，KSPR算法傳輸成功率接近68%，KMCSP算法傳輸成功率接近67%，GCTMHA傳輸成功率相對(duì)于KSPR和KMCSP的算法分別提高了4.41%和5.63%;當(dāng)EPSN規(guī)模數(shù)為15～20時(shí)，GCTMHA傳輸成功率接近87%，KSPR算法傳輸成功率接近81%，KMCSP算法傳輸成功率接近82%，GCTMHA傳輸成功率相對(duì)于KSPR和KMCSP的算法分別提高了7.4%和6.09%.

圖2中，橫坐標(biāo)表示EPSN規(guī)模，縱坐標(biāo)表示傳輸成功率.當(dāng)EPSN規(guī)模數(shù)為5～10時(shí)，GCTMHA傳輸成功率接近56.65%，KSPR算法傳輸成功率接近46.6%，KMCSP算法傳輸成功率接近46.65%，GCTMHA傳輸成功率相對(duì)于KSPR和KMCSP的算法分別提高了21.5%和21.4%;當(dāng)EPSN規(guī)模數(shù)為15～20時(shí)，GCTMHA傳輸成功率接近77.6%，KSPR算法傳輸成功率接近71.3%，KMCSP算法傳輸成功率接近74.6%，GCTMHA傳輸成功率相對(duì)于KSPR和KMCSP的算法分別提高了8.83%和10.93%.

5　結(jié)束語

本文針對(duì)基于Internet的GCT問題，提出基于啟發(fā)式群組命令傳輸模型GCTMHA.該模型從資源分配問題角度解決GCT傳輸問題.但本文提出的GCTMHA模型，并未考慮群體命令傳輸失敗后的重傳機(jī)制.因此，未來工作重點(diǎn)將考慮群組命令在傳輸失敗后重傳機(jī)制.

參考文獻(xiàn)

［1］錢志鴻，王義君.物聯(lián)網(wǎng)技術(shù)與應(yīng)用研究［J］.電子學(xué)報(bào)，2012，40(5): 1023 -1029.Qian Zhihong，Wang Yijun.IoT technology and application ［J］.Acta Electronica Sinica，2012，40(5): 1023 - 1029.(in Chinese)

［2］Luigi Atzori，Antonio Lera.From“smart objects”to“social objects”.the next evolutionary step of the Internet of Things［J］.IEEE Communications Magazine，2014，52(1): 97 -106.

［3］W Matthew Carlyle，R Kevin Wood.Near-shortest and K-shortest simple paths［J］.Networks，2005，46(2): 98 -109.

［4］Gang Liu，Ramakrishnan K G.A* Prune: an algorithm for finding K shortest paths subject to multiple constraints ［A］.Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies(INFOCOM 2001)Vol 2［C］.IEEE，2001.743 -749.

［5］Waxman B M.Performance evaluation of multipoint routing algorithms［A］.Proceedings of the INFOCOM’93 Conference［C］.USA，CA，San Francisco，1993.980 -986.

章剛男，1981年5月出生，江西撫州人.2007年畢業(yè)于北京大學(xué)軟件與微電子學(xué)院，2011年為上海理工大學(xué)博士研究生，從事物聯(lián)網(wǎng)、網(wǎng)絡(luò)計(jì)算等方面的有關(guān)研究.

E-mail: zhanggang198158@163.com

陳慶奎(通信作者)男，1966年1月出生，哈爾濱人.教授、博士、博士生導(dǎo)師.1987年和1996年分別在吉林大學(xué)、哈爾濱工業(yè)大學(xué)獲學(xué)士和碩士學(xué)位.從事網(wǎng)絡(luò)計(jì)算、并行計(jì)算等方面的研究工作.E-mail: chenqingkui@ gmail.com

GCTMHA: Group Command Transmission Model Based on Heuristic Algorithm

作者簡(jiǎn)介

基金項(xiàng)目:國(guó)家自然科學(xué)基金(No.60970012);高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研博導(dǎo)基金(No.20113120110008);上海重點(diǎn)科技攻關(guān)項(xiàng)目(No.14511107902);上海市工程中心建設(shè)項(xiàng)目(No.GCZX14014);上海智能家居大規(guī)模物聯(lián)共性技術(shù)工程中心項(xiàng)目(No.GCZX14014);上海市一流學(xué)科建設(shè)項(xiàng)目(No.XTKX2012);滬江基金研究基地專項(xiàng)(No.C14001)

收稿日期:2014-07-25;修回日期: 2015-03-11;責(zé)任編輯:李勇鋒

DOI:電子學(xué)報(bào)URL：http: / /www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.01.035

中圖分類號(hào)：TP393

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：0372-2112(2016)01-0233-03