多目標(biāo)數(shù)學(xué)規(guī)劃下的監(jiān)控網(wǎng)絡(luò)測(cè)點(diǎn)數(shù)據(jù)傳輸仿真

楊自香

(蕪湖職業(yè)技術(shù)學(xué)院 信息與人工智能學(xué)院,安徽 蕪湖 241006)

當(dāng)今社會(huì),監(jiān)控網(wǎng)絡(luò)的布設(shè)和使用已成為城市建設(shè)和管理的重要一環(huán)。例如,在交通管理方面,通過(guò)監(jiān)控可隨時(shí)查看違規(guī)車輛以及事故追溯;在社會(huì)安全方面,通過(guò)監(jiān)控可以實(shí)時(shí)追蹤犯罪嫌疑人;在商場(chǎng)超市方面,通過(guò)監(jiān)控可以防止商品丟失,降低商品失竊率[1]。監(jiān)控網(wǎng)絡(luò)主要由監(jiān)控中心和監(jiān)測(cè)點(diǎn)兩部分組成,前者主要用于顯示監(jiān)控畫面以及遠(yuǎn)程控制監(jiān)測(cè)點(diǎn),后者主要布設(shè)在現(xiàn)場(chǎng),用于拍攝現(xiàn)場(chǎng)畫面,通過(guò)無(wú)線通信網(wǎng)絡(luò)將數(shù)據(jù)傳輸給監(jiān)控網(wǎng)絡(luò)。隨著監(jiān)控范圍的擴(kuò)大,監(jiān)控設(shè)備越來(lái)越多,在避免監(jiān)控漏洞的同時(shí),也給數(shù)據(jù)傳輸帶來(lái)巨大壓力,監(jiān)控網(wǎng)絡(luò)的測(cè)點(diǎn)數(shù)據(jù)傳輸性能逐漸無(wú)法滿足需求,經(jīng)常出現(xiàn)嚴(yán)重的數(shù)據(jù)丟包、延遲等問(wèn)題。面對(duì)上述情況,優(yōu)化監(jiān)控網(wǎng)絡(luò)數(shù)據(jù)傳輸可靠性和效率具有重要的現(xiàn)實(shí)意義。

目前,有許多關(guān)于數(shù)據(jù)傳輸性能的優(yōu)化研究,如田夏利[2]構(gòu)建了網(wǎng)絡(luò)數(shù)據(jù)采集模型,基于傳播網(wǎng)絡(luò)利用數(shù)據(jù)特征優(yōu)化參數(shù),實(shí)現(xiàn)網(wǎng)絡(luò)數(shù)據(jù)傳輸優(yōu)化;楊艷琦[3]設(shè)計(jì)了基于樹型 分簇型拓?fù)涞臄?shù)據(jù)高效傳輸優(yōu)化算法,考慮網(wǎng)絡(luò)節(jié)點(diǎn)的剩余能量、節(jié)點(diǎn)數(shù)量、節(jié)點(diǎn)間隔距離等因素,構(gòu)建傳輸簇和數(shù)據(jù)傳輸最優(yōu)路徑,降低了數(shù)據(jù)傳輸?shù)钠骄舆t。以上數(shù)據(jù)傳輸性能優(yōu)化方法取得了一定的成果,但是所構(gòu)建的目標(biāo)函數(shù)普遍是圍繞一個(gè)目標(biāo),導(dǎo)致求取的傳輸方案只能滿足一方面的傳輸性能優(yōu)化需求。

針對(duì)上述問(wèn)題,為了全面提升監(jiān)控網(wǎng)絡(luò)數(shù)據(jù)多目標(biāo)傳輸?shù)目煽啃浴鬏敃r(shí)延以及傳輸能耗,對(duì)多目標(biāo)數(shù)學(xué)規(guī)劃下的監(jiān)控網(wǎng)絡(luò)測(cè)點(diǎn)數(shù)據(jù)傳輸仿真進(jìn)行研究。考慮傳輸可靠性、傳輸時(shí)延以及傳輸能耗建立多目標(biāo)函數(shù),設(shè)置約束條件,并構(gòu)建數(shù)據(jù)傳輸多目標(biāo)規(guī)劃模型;利用改進(jìn)遺傳算法求取規(guī)劃模型最優(yōu)解,獲得監(jiān)控網(wǎng)絡(luò)測(cè)點(diǎn)數(shù)據(jù)最優(yōu)傳輸方案。通過(guò)該研究可提高數(shù)據(jù)傳輸綜合性能,為監(jiān)控網(wǎng)絡(luò)的升級(jí)和改造提供參考和借鑒。

1 監(jiān)控網(wǎng)絡(luò)測(cè)點(diǎn)數(shù)據(jù)傳輸多目標(biāo)數(shù)學(xué)規(guī)劃模型

測(cè)點(diǎn)在監(jiān)測(cè)到數(shù)據(jù)之后,通過(guò)監(jiān)控網(wǎng)絡(luò)將數(shù)據(jù)遠(yuǎn)程傳輸?shù)奖O(jiān)控中心。受帶寬以及信道資源的限制,多個(gè)測(cè)點(diǎn)數(shù)據(jù)會(huì)同時(shí)爭(zhēng)搶一份網(wǎng)絡(luò)資源,時(shí)常會(huì)導(dǎo)致數(shù)據(jù)損壞或數(shù)據(jù)丟失現(xiàn)象。面對(duì)這種情況,構(gòu)建一種監(jiān)控網(wǎng)絡(luò)測(cè)點(diǎn)數(shù)據(jù)傳輸多目標(biāo)數(shù)學(xué)規(guī)劃模型。該模型構(gòu)建主要分為3部分,即模型假設(shè)條件設(shè)定、多目標(biāo)數(shù)學(xué)規(guī)劃模型構(gòu)建以及模型約束條件設(shè)置。

1.1 模型假設(shè)條件設(shè)定

假設(shè)條件的作用是方便多目標(biāo)數(shù)學(xué)規(guī)劃模型的構(gòu)建,簡(jiǎn)化多目標(biāo)求解問(wèn)題[4]。針對(duì)監(jiān)控網(wǎng)絡(luò)測(cè)點(diǎn)數(shù)據(jù)傳輸多目標(biāo)數(shù)學(xué)規(guī)劃模型,設(shè)置6個(gè)模型假設(shè)條件為:①監(jiān)控網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)已知;②監(jiān)控網(wǎng)絡(luò)測(cè)點(diǎn)位置和數(shù)量已知;③監(jiān)控網(wǎng)絡(luò)中不存在冗余通信鏈路;④每個(gè)網(wǎng)絡(luò)測(cè)點(diǎn)的監(jiān)控?cái)?shù)據(jù)量相同[5];⑤監(jiān)控網(wǎng)絡(luò)覆蓋面積固定和已知;⑥測(cè)點(diǎn)發(fā)送一個(gè)數(shù)據(jù)包所消耗的能量是動(dòng)態(tài)的[6]。

1.2 多目標(biāo)數(shù)學(xué)規(guī)劃模型構(gòu)建

在上述假設(shè)條件下建立多目標(biāo)數(shù)學(xué)規(guī)劃模型,其由多個(gè)單目標(biāo)函數(shù)、若干個(gè)約束條件組建而成[7]。模型基本結(jié)構(gòu)如下:

式中:Y為n個(gè)目標(biāo)函數(shù)組成的目標(biāo)向量;yi(x)為第i個(gè)單目標(biāo)函數(shù);x為決策向量;n為目標(biāo)函數(shù)的數(shù)量;A(x)為等式約束條件;B(x)為不等式約束條件。

參考上述多目標(biāo)數(shù)學(xué)規(guī)劃模型基本形式,針對(duì)監(jiān)控網(wǎng)絡(luò)測(cè)點(diǎn)數(shù)據(jù)傳輸問(wèn)題,將傳輸可靠性、傳輸時(shí)延以及傳輸能耗等3個(gè)單目標(biāo)組合在一起,構(gòu)成多目標(biāo)函數(shù)[8]。該函數(shù)表達(dá)式如下:

式中:F為綜合目標(biāo)最優(yōu)值;minf1(x)為傳輸時(shí)延最小化目標(biāo);minf2(x)為傳輸能耗最小化目標(biāo);maxf3(x)為傳輸可靠性最大化目標(biāo);ω1為傳輸可靠性權(quán)重;ω2為傳輸時(shí)延權(quán)重;ω3為傳輸能耗權(quán)重。

(1) 傳輸時(shí)延最小化目標(biāo)

式中:ai為第i個(gè)測(cè)點(diǎn)數(shù)據(jù)傳輸量;bi為第i個(gè)測(cè)點(diǎn)數(shù)據(jù)傳輸路徑的信道帶寬;ci為第i個(gè)測(cè)點(diǎn)數(shù)據(jù)傳輸路徑丟包概率;di為第i個(gè)測(cè)點(diǎn)數(shù)據(jù)傳輸路徑的安全系數(shù);m為測(cè)點(diǎn)數(shù)據(jù)傳輸路徑的數(shù)量;ui為可選信道[10]。

1.3 模型約束條件設(shè)置

為便于求解規(guī)劃模型,設(shè)定求解范圍,為上述建立的多目標(biāo)函數(shù)設(shè)置約束條件[11]如下:

(1) 數(shù)據(jù)傳輸路徑長(zhǎng)度約束

式中:vmax為通信網(wǎng)絡(luò)所能提供的最大數(shù)據(jù)傳輸速率;v為通信網(wǎng)絡(luò)的實(shí)際數(shù)據(jù)傳輸速率;hi為接入的第i個(gè)監(jiān)測(cè)點(diǎn);N為監(jiān)測(cè)點(diǎn)個(gè)數(shù)。

(4) 網(wǎng)絡(luò)負(fù)載均衡性約束

(6) 非負(fù)約束。模型中出現(xiàn)的所有參量均為非負(fù)數(shù)。

2 求解監(jiān)控網(wǎng)絡(luò)測(cè)點(diǎn)數(shù)據(jù)傳輸方案

針對(duì)上述建立的監(jiān)控網(wǎng)絡(luò)測(cè)點(diǎn)數(shù)據(jù)傳輸多目標(biāo)數(shù)學(xué)規(guī)劃模型,利用一種尋優(yōu)算法求解滿足該模型的最優(yōu)解[13]。最優(yōu)解即監(jiān)控網(wǎng)絡(luò)測(cè)點(diǎn)數(shù)據(jù)的最優(yōu)傳輸方案。傳統(tǒng)遺傳算法用于多目標(biāo)函數(shù)的尋優(yōu)時(shí)全局搜索和局部?jī)?yōu)化容易產(chǎn)生矛盾,探索能力強(qiáng)則易造成群體分散,不易收斂,而收斂能力強(qiáng)則易陷入局部極小點(diǎn)。本文選擇的尋優(yōu)算法為改進(jìn)遺傳算法,采用雙群體同步尋優(yōu)對(duì)傳統(tǒng)遺傳算法存在的缺陷進(jìn)行改進(jìn)[14]。雙群體同步尋優(yōu)是用兩個(gè)群體分工協(xié)作,一個(gè)是全局群體操作,負(fù)責(zé)尋找存在最優(yōu)點(diǎn)的區(qū)域,另一個(gè)是局部群體操作,負(fù)責(zé)搜索全局群體劃定的區(qū)域,找到最優(yōu)點(diǎn)。其優(yōu)勢(shì)在于可實(shí)現(xiàn)局部?jī)?yōu)化和全局優(yōu)化的平衡,收斂能力更強(qiáng)。具體步驟如下:

步驟1 假設(shè)監(jiān)控網(wǎng)絡(luò)中監(jiān)測(cè)點(diǎn)數(shù)量為τ,通信網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量為n。

步驟2 種群初始化。在設(shè)置的6個(gè)約束條件范圍內(nèi)隨機(jī)生成初始種群,并通過(guò)二進(jìn)制編碼方式對(duì)每個(gè)個(gè)體進(jìn)行編碼[15]。編碼形式如下:

式中:Oi為第i個(gè)初始解。

步驟3 利用全局群體操作將初始種群劃分為不可行解和可行解兩個(gè)區(qū)域,由此形成兩個(gè)種群記為ξ和ζ,兩個(gè)種群的規(guī)模分別記為T1和T2。

步驟4 按照式(4)多目標(biāo)函數(shù)計(jì)算種群中個(gè)體的適應(yīng)度。

步驟5 判斷適應(yīng)度是否達(dá)到期望值。若達(dá)到則結(jié)束,輸出最優(yōu)解;否則,繼續(xù)下一步。

步驟6 對(duì)種群進(jìn)行變異和交叉操作,由此產(chǎn)生試驗(yàn)種群μ。在多目標(biāo)優(yōu)化過(guò)程中通常不存在同時(shí)最小化所有目標(biāo)函數(shù)的可行解,為了增加多目標(biāo)最小化效果,降低至少一個(gè)目標(biāo),使所有目標(biāo)得到改進(jìn)的不可行解,從而解決計(jì)算困境。因此,在變異操作中同時(shí)加入不可行解和可行解,實(shí)現(xiàn)全局和局部最優(yōu)。經(jīng)過(guò)變異操作產(chǎn)生的第i個(gè)試驗(yàn)個(gè)體表達(dá)式為

式中:ξi為不可行解種群中的第i個(gè)個(gè)體;ζi為可行解種群中的第i個(gè)個(gè)體;η為變異因子;α為搜索到的局部最優(yōu)可行解;β為目前為止搜索到的全局最優(yōu)可行解,即最優(yōu)點(diǎn)區(qū)域。

局部群體操作是利用交叉操作從最優(yōu)區(qū)域中找到最優(yōu)解。交叉操作是遺傳算法的核心環(huán)節(jié),其原理為:自然界生物的染色體通過(guò)基因重組形成新的染色體,父代染色體的優(yōu)良性狀最大程度上遺傳給下一代染色體,通過(guò)不斷交叉遺傳產(chǎn)生最優(yōu)個(gè)體。經(jīng)過(guò)交叉操作產(chǎn)生的第i個(gè)試驗(yàn)個(gè)體為

式中:γi為第i個(gè)變異試驗(yàn)個(gè)體的變異程度;γ′為設(shè)定的閾值;δ為交叉因子。

步驟7 從μ中篩選出不滿足約束條件的個(gè)體,進(jìn)行種群更新。

步驟8 按照式(5)～式(7)計(jì)算更新后種群中每個(gè)個(gè)體的單目標(biāo)函數(shù)值。

步驟9 計(jì)算每個(gè)個(gè)體的聚合度。計(jì)算公式如下:

式中:λi為第i個(gè)個(gè)體的聚合度;f1(i)為傳輸時(shí)延聚合度;f2(i)為傳輸能耗聚合度;f3(i)為傳輸可靠性聚合度;σ為更新后群體規(guī)模。

步驟10 篩選出聚合度函數(shù)值最小的個(gè)體,該個(gè)體為最優(yōu)解,是監(jiān)控網(wǎng)絡(luò)測(cè)點(diǎn)數(shù)據(jù)最優(yōu)傳輸方案[16]。

通過(guò)上述過(guò)程,完成多目標(biāo)數(shù)學(xué)規(guī)劃下的監(jiān)控網(wǎng)絡(luò)測(cè)點(diǎn)數(shù)據(jù)傳輸優(yōu)化研究。

3 仿真測(cè)試與分析

為測(cè)試研究方法的應(yīng)用性和有效性,進(jìn)行監(jiān)控網(wǎng)絡(luò)測(cè)點(diǎn)數(shù)據(jù)傳輸仿真實(shí)驗(yàn)。該實(shí)驗(yàn)以多目標(biāo)函數(shù)求解下的傳輸方案為測(cè)試組,以3個(gè)單目標(biāo)函數(shù)求解下的傳輸方案為對(duì)照組,即傳輸時(shí)延單目標(biāo)函數(shù)求解方案為對(duì)照1組,傳輸能耗單目標(biāo)函數(shù)求解方案為對(duì)照2組,傳輸可靠性單目標(biāo)函數(shù)求解方案為對(duì)照3組。

根據(jù)實(shí)際的某市監(jiān)控網(wǎng)絡(luò)布設(shè)情況,選擇在1 000 m(X軸)×1 000 m(Y軸)的范圍內(nèi)搭建仿真測(cè)試環(huán)境,如圖1所示。

圖1仿真測(cè)試環(huán)境相關(guān)參數(shù)如表1所示。仿真軟硬件配置如表2所示。

表1 仿真測(cè)試環(huán)境相關(guān)參數(shù)

表2 實(shí)驗(yàn)環(huán)境配置

圖1 仿真測(cè)試環(huán)境

結(jié)合均值自適應(yīng)法的思想原理,估計(jì)多目標(biāo)函數(shù)較為合適的權(quán)值分配方法:ω1為0.563 1,ω2為0.210 8,ω3為0.226 1。

利用改進(jìn)遺傳算法求解目標(biāo)函數(shù),設(shè)置相關(guān)參數(shù):種群規(guī)模為不可行解200,可行解200;最大迭代次數(shù)為200;適應(yīng)度期望值為10;交叉因子為0.2;變異因子為0.3。根據(jù)上述參數(shù),采用雙群體同步尋優(yōu),進(jìn)行變異和交叉操作,篩選出聚合度函數(shù)值最優(yōu)解,獲得監(jiān)控網(wǎng)絡(luò)測(cè)點(diǎn)數(shù)據(jù)最優(yōu)傳輸方案。

對(duì)比測(cè)試傳統(tǒng)遺傳算法、文獻(xiàn)[2]的改進(jìn)粒子群算法和本文改進(jìn)遺傳算法的收斂速度,結(jié)果如圖2所示。

圖2 算法收斂性測(cè)試結(jié)果

由圖2可知,本文設(shè)計(jì)的改進(jìn)遺傳算法收斂速度最快,在迭代87次左右達(dá)到聚合度最低值,低于0.1,而其他算法均在140次之后才達(dá)到最優(yōu)值且高于本文算法的聚合度。以上數(shù)據(jù)證明本文算法的尋優(yōu)效率最佳。

利用改進(jìn)遺傳算法求取的傳輸方案如圖3所示。對(duì)比每個(gè)傳輸方案的傳輸時(shí)延、傳輸能耗以及傳輸可靠性,判斷傳輸方案性能,結(jié)果如表3所示。

圖3 5個(gè)監(jiān)測(cè)點(diǎn)的數(shù)據(jù)傳輸方案

由表3可知,測(cè)試組傳輸方案的時(shí)延雖然不如對(duì)照1組,能耗不如對(duì)照2組,可靠性不如對(duì)照3組,但是由于綜合考慮了3個(gè)目標(biāo),綜合性要遠(yuǎn)遠(yuǎn)好于3個(gè)對(duì)照組。對(duì)照組只考慮一個(gè)方面,往往導(dǎo)致一個(gè)方面非常好,但是其他方面非常差的情況發(fā)生,這與現(xiàn)實(shí)傳輸要求不符。現(xiàn)實(shí)中監(jiān)控網(wǎng)絡(luò)在傳輸時(shí)不可能只要求一方面性能,而忽視其他性能要求。

表3 傳輸方案的傳輸時(shí)延、能耗以及可靠性數(shù)值

4 結(jié) 語(yǔ)

隨著監(jiān)控測(cè)點(diǎn)數(shù)量的不斷增加,監(jiān)控范圍擴(kuò)大的同時(shí),使得測(cè)點(diǎn)數(shù)據(jù)傳輸問(wèn)題越來(lái)越嚴(yán)重。面對(duì)這種情況,進(jìn)行多目標(biāo)數(shù)學(xué)規(guī)劃下的監(jiān)控網(wǎng)絡(luò)測(cè)點(diǎn)數(shù)據(jù)傳輸仿真研究。該研究將傳輸可靠性、傳輸時(shí)延以及傳輸能耗等3個(gè)單目標(biāo)組合在一起,構(gòu)成多目標(biāo)數(shù)學(xué)規(guī)劃模型,最后通過(guò)求解得出最優(yōu)數(shù)據(jù)傳輸方案。經(jīng)仿真測(cè)試,多目標(biāo)函數(shù)求解方案比單目標(biāo)求解方案的綜合性更強(qiáng),驗(yàn)證了本文研究方法的有效性。