章　剛，陳慶奎，2

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

?

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

章剛1，陳慶奎1，2

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

摘要：Internet盡力而為的服務模式在支持群組命令傳輸過程中，容易產生命令之間路徑競爭.定義出有效路徑統(tǒng)計網絡，并進一步定義出基于有效路徑統(tǒng)計網絡的群組多約束多目標優(yōu)化問題.針對該問題，提出基于啟發(fā)式群組命令傳輸模型.實驗從群組命令傳輸成功率驗證該模型對支持群組命令傳輸的合理性.

關鍵詞：群組命令傳輸;群組多約束多目標優(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)網運營中心(中心)作為物聯(lián)網“可控”思想的核心技術已經受到各行各業(yè)的重視［1］.其主要功能是使得一組具有多約束的命令能夠通過Internet網絡全部傳輸到分散在不同大區(qū)域(跨省、市、區(qū))的終端設備.在傳輸過程中，任何單一命令傳輸丟失，都被視為群組命令傳輸失敗.中心本質是基于Internet網絡的群組命令傳輸(Group Command Transmission，GCT)過程.

然而，Internet盡力而為的服務模式并不支持GCT傳輸.主要原因是，Internet為GCT中每個命令提供路徑，容易產生多個命令競爭同一路徑，當該路徑無法同時滿足所有命令需求時，會造成網絡擁塞.

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

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

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

綜上，本文主要考慮的問題是，基于EPSN網絡的GMCMOOP問題.

2　問題描述

設G =(V，E)表示為EPSN網絡，其中V為CSA集合，E為CSA之間鏈路集合，每條鏈路e∈E上都擁有一組度量參數j(j = 1，2，…)，fj表示參數j所對應的子目標函數，現給定一組子目標函數fj(j = 1，2，…)的約束值Cj(j =1，2，…)，則:

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

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

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

其中F表示當前GMCMOOP問題總體目標函數，Fj表示第j個MCMOOP問題，GEPj表示MCMOOPj的非劣解集.

3　GCTMHA模型

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

3.1RAP問題描述

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

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

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

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

設引入0 -1變量xij，i，j =1，2，…

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

3.3GCTMHA模型實現

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

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

Step 3:從任務U(mf1)到任務U(mfn)，分別依次從所對應的匹配排序集合SWAP中分別提取出與當前最大匹配度Θ，并根據此產生一組解集s(EP)，解集s(EP)中每個元素為匹配度Θ對應的有效路徑，轉入Step 4;

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

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

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

Step 7:記錄當前有效解并退出.

4　實驗與分析

實驗環(huán)境:曙光集群20個服務器及利用Waxmam模型［5］隨機生成的網絡拓撲結構.其中，隨機網絡拓撲結構具有20個節(jié)點，28條鏈路，并在每條鏈路上隨機產生n，n≥2個度量參數.

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

測試性能:驗證EPSN網絡規(guī)模不斷變化下，不同算法之間的GCT傳輸成功率(Transmission Success，TS)性能比較: TS =傳輸成功數/傳輸總數.

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

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

5　結束語

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

參考文獻

［1］錢志鴻，王義君.物聯(lián)網技術與應用研究［J］.電子學報，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è)于北京大學軟件與微電子學院，2011年為上海理工大學博士研究生，從事物聯(lián)網、網絡計算等方面的有關研究.

E-mail: zhanggang198158@163.com

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

GCTMHA: Group Command Transmission Model Based on Heuristic Algorithm

作者簡介

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

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

DOI:電子學報URL：http: / /www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.01.035

中圖分類號：TP393

文獻標識碼：A

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