面向用戶需求的空天地一體化車載網(wǎng)絡(luò)任務(wù)分配策略

譚詩(shī)翰, 金鳳林, 頓聰穎

(陸軍工程大學(xué)指揮控制工程學(xué)院, 江蘇 南京 210007)

0 引 言

隨著汽車技術(shù)的發(fā)展,人們對(duì)汽車的期望不再僅僅是更舒適、更環(huán)保、更有趣,對(duì)汽車信息化、智能化服務(wù)的需求正在不斷增強(qiáng)。車載網(wǎng)絡(luò)能夠?qū)崿F(xiàn)車輛、其他終端和公共網(wǎng)絡(luò)之間的信息交換,可以在交通管理、車輛移動(dòng)數(shù)據(jù)服務(wù)和自動(dòng)駕駛等方面發(fā)揮關(guān)鍵作用,是未來(lái)汽車發(fā)展的重要方向之一。第三代合作伙伴計(jì)劃(the 3rd generation partnership project,3GPP)一直在尋求支持長(zhǎng)期演進(jìn)(long-term evolution,LTE)和5G蜂窩網(wǎng)絡(luò)的車載網(wǎng)絡(luò)服務(wù)。由電信和汽車行業(yè)聯(lián)合成立的5G汽車協(xié)會(huì)(the 5G automotive association,5GAA)也在致力于推動(dòng)車載網(wǎng)絡(luò)技術(shù)的開發(fā)、測(cè)試和部署。

然而,當(dāng)前車載網(wǎng)絡(luò)系統(tǒng)仍然存在一些重大問(wèn)題。一是隨著城市的快速發(fā)展,車載網(wǎng)絡(luò)用戶量激增,網(wǎng)絡(luò)擁塞問(wèn)題愈發(fā)嚴(yán)重;二是,用戶對(duì)車載網(wǎng)絡(luò)服務(wù)的需求趨于多樣化,單一的網(wǎng)絡(luò)服務(wù)難以滿足用戶需求;三是在一些偏遠(yuǎn)地區(qū)用戶難以獲得可靠的網(wǎng)絡(luò)服務(wù)。

傳統(tǒng)地面網(wǎng)絡(luò)對(duì)網(wǎng)絡(luò)系統(tǒng)性能的提升能力有限:一方面,由于地面無(wú)線接入網(wǎng)頻譜資源有限,過(guò)密的基站部署將導(dǎo)致更多的網(wǎng)絡(luò)資源競(jìng)爭(zhēng)和網(wǎng)絡(luò)間相互干擾;另一方面,地面網(wǎng)絡(luò)本身有限的覆蓋范圍,無(wú)法滿足覆蓋區(qū)域邊緣以及偏遠(yuǎn)地區(qū)用戶的需求。

空天地一體化車載網(wǎng)絡(luò)(space-air-ground integrated vehicular networks,SAGVN)利用現(xiàn)代信息網(wǎng)絡(luò)技術(shù)將空間、空中和地面網(wǎng)絡(luò)部分連接起來(lái),具有覆蓋范圍大、吞吐量高和恢復(fù)能力強(qiáng)等固有優(yōu)勢(shì),有望解決上述車載網(wǎng)絡(luò)發(fā)展過(guò)程中遇到的瓶頸問(wèn)題。

近些年來(lái),大量的研究涌入SAGVN。其中,文獻(xiàn)[11]介紹了一種可以用于SAGVN的實(shí)驗(yàn)仿真平臺(tái)。文獻(xiàn)[8]提出了一種基于軟件定義的SAGVN架構(gòu)。文獻(xiàn)[12]在此基礎(chǔ)上,提出了一個(gè)基于人工智能(artificial intelligence, AI)的SAGVN管理和控制架構(gòu)。文獻(xiàn)[13]也在文獻(xiàn)[8]的基礎(chǔ)上,提出了一種基于AI的SAGVN資源分配方式。文獻(xiàn)[14]將虛擬網(wǎng)絡(luò)功能(virtual network functions,VNFs)和業(yè)務(wù)功能鏈(service function chaining, SFC)融入SAGVN架構(gòu),用于增強(qiáng)SAGVN管理性能。此外,SAGVN建設(shè)在工業(yè)界也在快速推進(jìn),包括GIG、TSAT和O3b在內(nèi)的多個(gè)項(xiàng)目已經(jīng)開始了SAGVN相關(guān)的研究和實(shí)驗(yàn)。

但是,針對(duì)SAGVN的網(wǎng)絡(luò)管理仍然存在以下幾個(gè)難點(diǎn):

(1) 地面、空中和空間網(wǎng)絡(luò)在帶寬、網(wǎng)絡(luò)覆蓋面積、時(shí)延和網(wǎng)絡(luò)費(fèi)用等差異巨大,需要統(tǒng)籌考慮,使不同網(wǎng)絡(luò)發(fā)揮各自優(yōu)勢(shì),互補(bǔ)短板。

(2) 車載用戶需求向著多元化發(fā)展,對(duì)網(wǎng)絡(luò)進(jìn)行管理需要針對(duì)不同需求用戶提供不同服務(wù)。

(3) 網(wǎng)絡(luò)狀態(tài)更為復(fù)雜,對(duì)網(wǎng)絡(luò)管理的計(jì)算難度增加。

基于以上分析,本文提出了面向用戶需求的SAGVN任務(wù)分配策略,通過(guò)為SAGVN內(nèi)不同網(wǎng)絡(luò)合理分配不同的網(wǎng)絡(luò)任務(wù),提升網(wǎng)絡(luò)對(duì)用戶的服務(wù)質(zhì)量(quality of ser-vice,QoS),主要做了以下工作:

(1) 構(gòu)建車載用戶需求和用戶滿意度描述框架。相同的網(wǎng)絡(luò)服務(wù)對(duì)于不同需求的用戶,對(duì)網(wǎng)絡(luò)QoS的體驗(yàn)可能截然不同,想要為用戶合理分配網(wǎng)絡(luò),準(zhǔn)確地描述用戶需求就顯得尤為重要。本文基于多準(zhǔn)則效用理論,結(jié)合信號(hào)強(qiáng)度、網(wǎng)絡(luò)費(fèi)用、時(shí)延和帶寬多種影響因素建立適當(dāng)?shù)男в煤瘮?shù),獲得用戶對(duì)不同影響因素的需求,然后利用層次分析法(analytic hierarchy process,AHP)獲得各影響因素權(quán)重,權(quán)重的大小反映了用戶對(duì)不同網(wǎng)絡(luò)性能的偏好。根據(jù)用戶當(dāng)前接入網(wǎng)絡(luò)的網(wǎng)絡(luò)性能、用戶滿意度影響因素和影響因素權(quán)重,獲得用戶對(duì)當(dāng)前網(wǎng)絡(luò)服務(wù)的滿意度。例如,通過(guò)車載網(wǎng)絡(luò)將圖片、視頻和車輛信息快速上傳到數(shù)據(jù)中心,用戶希望獲得高帶寬的網(wǎng)絡(luò)傳輸服務(wù),所以用戶對(duì)網(wǎng)絡(luò)帶寬需求較高,網(wǎng)絡(luò)帶寬具有更大的權(quán)重;當(dāng)發(fā)生交通事故時(shí),實(shí)時(shí)地向智能交通平臺(tái)報(bào)告事故地點(diǎn)有助于挽救生命,避免交通擁堵,此時(shí)用戶傾向于高時(shí)延高可靠度的網(wǎng)絡(luò)服務(wù),當(dāng)前網(wǎng)絡(luò)服務(wù)的時(shí)延以及可靠度對(duì)用戶滿意度影響較大。

(2) 提出整體用戶滿意度最大的網(wǎng)絡(luò)任務(wù)分配策略。對(duì)于不同用戶,SAGVN所能提供的網(wǎng)絡(luò)服務(wù)也不同。本文將SAGVN任務(wù)分配過(guò)程抽象為半馬爾可夫決策過(guò)程(semi Markov decision process,SMDP),通過(guò)控制不同網(wǎng)絡(luò)為不同的用戶提供服務(wù),使長(zhǎng)期整體用戶滿意度最大。利用價(jià)值迭代算法獲得最優(yōu)網(wǎng)絡(luò)任務(wù)分配策略?？紤]實(shí)際操作中網(wǎng)絡(luò)狀態(tài)復(fù)雜多變,利用Q-learning算法與網(wǎng)絡(luò)進(jìn)行交互學(xué)習(xí),獲得近似最優(yōu)的網(wǎng)絡(luò)任務(wù)分配策略。本文中最優(yōu)網(wǎng)絡(luò)任務(wù)分配策略具體來(lái)講就是通過(guò)有計(jì)劃性的安排,減少一些位于地面網(wǎng)絡(luò)密集區(qū)域的用戶對(duì)衛(wèi)星網(wǎng)絡(luò)資源的占用,為一些偏遠(yuǎn)地區(qū)用戶預(yù)留衛(wèi)星網(wǎng)絡(luò)資源;將一些對(duì)網(wǎng)絡(luò)帶寬需求不高的用戶帶寬減少,從而為未來(lái)需要更高網(wǎng)絡(luò)帶寬的用戶預(yù)留網(wǎng)絡(luò)資源等方法,實(shí)現(xiàn)長(zhǎng)期整體用戶滿意度最大。

本文的主要貢獻(xiàn)有:

(1) 基于多種影響因素構(gòu)建效用函數(shù),并給出了這些效用函數(shù)詳細(xì)證明。利用AHP,獲得各影響因素權(quán)重。通過(guò)影響因素效用函數(shù)和權(quán)重來(lái)描述用戶的網(wǎng)絡(luò)需求和偏好。根據(jù)當(dāng)前網(wǎng)絡(luò)對(duì)用戶服務(wù)影響因素效用函數(shù)值加權(quán)乘積,將網(wǎng)絡(luò)對(duì)用戶的QoS抽象為用戶對(duì)網(wǎng)絡(luò)服務(wù)的滿意度。

(2) 基于對(duì)用戶需求和滿意度的描述,提出了一種面向用戶需求的網(wǎng)絡(luò)任務(wù)分配策略。將對(duì)不同網(wǎng)絡(luò)的任務(wù)分配過(guò)程抽象為SMDP,利用價(jià)值迭代算法,獲得最優(yōu)的網(wǎng)絡(luò)任務(wù)分配策略,并利用Q-learning算法獲得近似最優(yōu)策略。

(3) 在網(wǎng)絡(luò)資源充足和網(wǎng)絡(luò)擁塞兩種網(wǎng)絡(luò)環(huán)境下進(jìn)行仿真實(shí)驗(yàn)。仿真結(jié)果表明,相較于傳統(tǒng)網(wǎng)絡(luò)任務(wù)分配策略,本文所提策略在網(wǎng)絡(luò)資源充足環(huán)境下,整體用戶滿意度上升超過(guò)30%;在網(wǎng)絡(luò)擁塞環(huán)境下,對(duì)用戶服務(wù)請(qǐng)求的拒絕率下降超過(guò)40%。在網(wǎng)絡(luò)擁塞環(huán)境下,對(duì)網(wǎng)絡(luò)服務(wù)分配策略中用戶滿意度的影響因素進(jìn)行分析,仿真結(jié)果表明,所提方法可以有效降低網(wǎng)絡(luò)對(duì)網(wǎng)絡(luò)服務(wù)需求迫切用戶服務(wù)請(qǐng)求的拒絕率。

1 場(chǎng)景描述

1.1 系統(tǒng)架構(gòu)

本文主要討論局部區(qū)域內(nèi)SAGVN的任務(wù)分配策略。由衛(wèi)星劃分一定范圍的網(wǎng)絡(luò)區(qū)域,將區(qū)域內(nèi)的網(wǎng)絡(luò)作為一個(gè)整體,對(duì)區(qū)域內(nèi)的網(wǎng)絡(luò)分配網(wǎng)絡(luò)任務(wù)。如圖1所示,SAGVN由3層組成:基礎(chǔ)設(shè)施層、控制層和管理層?；A(chǔ)設(shè)施層包括空間段、空中段和地面段內(nèi)所有的無(wú)線通信節(jié)點(diǎn),比如低軌衛(wèi)星(low earth orbit,LEO)、無(wú)人機(jī)(unmanned aerial vehicle,UAV)、地面基站等?？刂茖佑刹煌W(wǎng)絡(luò)的網(wǎng)絡(luò)控制器組成,比如軟件定義網(wǎng)絡(luò)(software defined network,SDN)控制器,網(wǎng)絡(luò)控制器通過(guò)南向接口(southbound interfaces,SBIs)控制各自的底層物理資源,比如衛(wèi)星波束轉(zhuǎn)向、UAV運(yùn)動(dòng)控制、網(wǎng)絡(luò)資源分配等。管理層包括后臺(tái)數(shù)據(jù)中心,功能是協(xié)調(diào)不同網(wǎng)絡(luò)動(dòng)作?？刂茖油ㄟ^(guò)北向接口(northbound interfaces,NBIs)實(shí)現(xiàn)網(wǎng)絡(luò)管理,如移動(dòng)管理、網(wǎng)絡(luò)監(jiān)督、網(wǎng)絡(luò)任務(wù)分配等功能。不同網(wǎng)段的網(wǎng)絡(luò)控制器由上層管理層通過(guò)東西接口進(jìn)行協(xié)調(diào)。

圖1 SAGVN模型Fig.1 SAGVN model

本文基于網(wǎng)絡(luò)管理層功能,根據(jù)由基礎(chǔ)設(shè)施層和控制層收集上傳的用戶信息和網(wǎng)絡(luò)狀態(tài)信息數(shù)據(jù),制定網(wǎng)絡(luò)任務(wù)分配策略。網(wǎng)絡(luò)管理層根據(jù)網(wǎng)絡(luò)任務(wù)分配策略,通過(guò)各網(wǎng)段控制器控制無(wú)線通信節(jié)點(diǎn)對(duì)不同用戶的網(wǎng)絡(luò)服務(wù)請(qǐng)求做出響應(yīng),使用戶接入不同的無(wú)線通信節(jié)點(diǎn),實(shí)現(xiàn)對(duì)不同網(wǎng)絡(luò)的任務(wù)分配。

1.2 場(chǎng)景模型

根據(jù)上文所述,設(shè)區(qū)域內(nèi)SAGVN用戶集合為,用戶∈,設(shè)區(qū)域內(nèi)用戶總量為,設(shè)∈{0,1},=1表示網(wǎng)絡(luò)正在對(duì)用戶服務(wù),=0表示用戶未接入網(wǎng)絡(luò),用戶所接入網(wǎng)絡(luò)的信號(hào)強(qiáng)度、費(fèi)用、時(shí)延和帶寬分別表示為、、和。

設(shè)區(qū)域內(nèi)基礎(chǔ)設(shè)施層通信節(jié)點(diǎn)的集合為,通信節(jié)點(diǎn)∈,通信節(jié)點(diǎn)總數(shù)為,通信節(jié)點(diǎn)的總功率、總帶寬和最大用戶量為、和,通信節(jié)點(diǎn)剩余帶寬、剩余功率和剩余用戶量為、和,覆蓋用戶的通信節(jié)點(diǎn)的集合表示為,通信節(jié)點(diǎn)服務(wù)覆蓋范圍內(nèi)用戶的集合表示為,設(shè), ∈{0,1},, =1表示用戶接入網(wǎng)絡(luò)(∈),, =0表示用戶未接入網(wǎng)絡(luò)。

2 用戶需求和滿意度描述

對(duì)用戶需求和滿意度的描述是一個(gè)復(fù)雜的過(guò)程,需要多種模塊協(xié)調(diào)進(jìn)行。如圖2所示,用戶網(wǎng)絡(luò)需求和滿意度描述框架包括數(shù)據(jù)采集、網(wǎng)絡(luò)篩選、擬合值生成和滿意度計(jì)算等模塊。首先,數(shù)據(jù)采集模塊收集并提供用戶需求描述所需的所有參數(shù),包括用戶配置、流量需求、QoS需求和運(yùn)營(yíng)商網(wǎng)絡(luò)配置。在此框架中,車載終端收集和上傳用戶需求相關(guān)參數(shù)?；谶@些參數(shù),可以計(jì)算出信號(hào)強(qiáng)度、時(shí)延和網(wǎng)絡(luò)費(fèi)用等影響因素指標(biāo)。網(wǎng)絡(luò)篩選模塊選擇滿足給定約束條件的網(wǎng)絡(luò),建立不同用戶的可用網(wǎng)絡(luò)集合。擬合值生成模塊使用AHP為每個(gè)指標(biāo)生成文獻(xiàn)[20]中討論的期望權(quán)重。最后,根據(jù)當(dāng)前網(wǎng)絡(luò)服務(wù)性能,獲得用戶對(duì)網(wǎng)絡(luò)服務(wù)的滿意度。

圖2 用戶需求和滿意度描述框架Fig.2 User requirements and satisfaction description framework

2.1 AHP

利用AHP為每個(gè)影響因素分配適當(dāng)?shù)臋?quán)重,利用權(quán)重來(lái)表征用戶偏好。AHP如算法1所示。

算法 1 AHP輸入 用戶需求:最大和最小帶寬bmax和bmin,最大網(wǎng)絡(luò)費(fèi)用cmax,最大網(wǎng)絡(luò)時(shí)延τmax,最大和最小信號(hào)強(qiáng)度需求smax和smin;輸出 用戶i對(duì)于不同影響因素權(quán)重:網(wǎng)絡(luò)費(fèi)用權(quán)重αic、信號(hào)強(qiáng)度權(quán)重αis、網(wǎng)絡(luò)時(shí)延權(quán)重αiτ、帶寬權(quán)重αib;過(guò)程1. 根據(jù)用戶需求,構(gòu)建層次結(jié)構(gòu)L=l1,l2,…,lm,令k=1;2. 循環(huán)1:構(gòu)建決策矩陣;3. 循環(huán)2:計(jì)算層次k權(quán)重;4. 獲得網(wǎng)絡(luò)費(fèi)用權(quán)重αi,kc、信號(hào)強(qiáng)度權(quán)重αi,ks、網(wǎng)絡(luò)時(shí)延權(quán)重αi,kτ、帶寬權(quán)重αi,kb;5. 判斷層次k權(quán)重是否一致,如果不是,返回循環(huán)1;6. 如果k

2.2 效用函數(shù)

根據(jù)效用理論,效用函數(shù)要滿足二次可微性、單調(diào)性和凹凸性,本文采用了文獻(xiàn)[21]中效用函數(shù)設(shè)計(jì)方案,為每個(gè)影響因素設(shè)計(jì)了效用函數(shù)。

221 信號(hào)強(qiáng)度效用函數(shù)

一般情況下,當(dāng)接收到的信號(hào)強(qiáng)度低于某一閾值時(shí),可以認(rèn)為不能保證網(wǎng)絡(luò)正常運(yùn)行。在這種情況下,信號(hào)強(qiáng)度的效用值為0。此外,用戶所接收的信號(hào)強(qiáng)度具有上限。

設(shè)用戶信號(hào)強(qiáng)度效用函數(shù)如下:

(1)

(2)

以下給出其他的二次可微性、單調(diào)性和凹凸性證明。

證明二次可微性,只需證明式(1)中的第2個(gè)和第3個(gè)方程是可微的。由式(1)可得

(3)

所以:

(4)

因此,式(1)中的效用函數(shù)是二次可微的。同時(shí),容易發(fā)現(xiàn)式(1)也是單調(diào)的、凹凸的。

證畢

式(1)的現(xiàn)實(shí)意義是信號(hào)強(qiáng)度越高,效用函數(shù)值越大,網(wǎng)絡(luò)信號(hào)強(qiáng)度越好。說(shuō)明所定義的效用函數(shù)()可以有效地用于網(wǎng)絡(luò)任務(wù)分配。

222 網(wǎng)絡(luò)費(fèi)用效用函數(shù)

對(duì)于用戶來(lái)說(shuō),網(wǎng)絡(luò)費(fèi)用是一個(gè)更直觀的度量。不同網(wǎng)絡(luò)的費(fèi)用可以相互直接比較。本文用線性函數(shù)表示網(wǎng)絡(luò)費(fèi)用的效用函數(shù)。因此,用戶的網(wǎng)絡(luò)費(fèi)用效用函數(shù)可以表示為

(5)

式(5)的現(xiàn)實(shí)意義是網(wǎng)絡(luò)費(fèi)用越小,效用函數(shù)值越大,網(wǎng)絡(luò)越好。這說(shuō)明所定義的效用函數(shù)()可以有效地用于網(wǎng)絡(luò)任務(wù)分配。

223 網(wǎng)絡(luò)時(shí)延效用函數(shù)

一般來(lái)說(shuō),網(wǎng)絡(luò)時(shí)延應(yīng)該有一個(gè)最大值。在設(shè)計(jì)效用函數(shù)時(shí),網(wǎng)絡(luò)時(shí)延越大,對(duì)應(yīng)的效用值越低。因此,定義用戶的網(wǎng)絡(luò)時(shí)延的效用函數(shù)為

(6)

(7)

網(wǎng)絡(luò)時(shí)延效用函數(shù)與信號(hào)強(qiáng)度效用函數(shù)相似,都是二次可微的、單調(diào)的和凹凸的。由于篇幅限制,沒(méi)有給出詳細(xì)的證明過(guò)程。式(6)的現(xiàn)實(shí)意義是時(shí)延越小,效用函數(shù)()值越大,網(wǎng)絡(luò)越好。這說(shuō)明所定義的效用函數(shù)()可以有效地用于網(wǎng)絡(luò)任務(wù)分配。

224 網(wǎng)絡(luò)帶寬效用函數(shù)

當(dāng)網(wǎng)絡(luò)帶寬低于用戶流量的最低需求時(shí),將導(dǎo)致用戶服務(wù)請(qǐng)求丟失。當(dāng)網(wǎng)絡(luò)帶寬大于用戶流量最大需求時(shí),用戶的滿意度不會(huì)進(jìn)一步提高。因此,用戶的網(wǎng)絡(luò)帶寬效用函數(shù)定義如下:

(8)

(9)

2.3 用戶滿意度

用戶滿意度是用戶對(duì)網(wǎng)絡(luò)QoS體驗(yàn)的抽象,滿意度越高,用戶體驗(yàn)越好。

將網(wǎng)絡(luò)對(duì)用戶的服務(wù)性能參數(shù)代入用戶效應(yīng)函數(shù)中,信號(hào)強(qiáng)度可由用戶終端確定,其他指標(biāo)需通過(guò)網(wǎng)絡(luò)信息采集獲得。將效用函數(shù)值加權(quán)相乘,獲得用戶對(duì)網(wǎng)絡(luò)服務(wù)的滿意度。用戶對(duì)網(wǎng)絡(luò)服務(wù)的滿意度表示為

(10)

區(qū)域內(nèi)整體用戶滿意度表示為

(11)

3 網(wǎng)絡(luò)任務(wù)分配策略

3.1 問(wèn)題描述

本文考慮有限的單一網(wǎng)絡(luò)服務(wù)區(qū)域網(wǎng)絡(luò)任務(wù)分配。假設(shè)同一網(wǎng)絡(luò)任務(wù)在任務(wù)結(jié)束前不主動(dòng)切換網(wǎng)絡(luò),如果用戶移動(dòng)到了網(wǎng)絡(luò)服務(wù)范圍外,用戶結(jié)束已經(jīng)完成的任務(wù)部分,重新申請(qǐng)網(wǎng)絡(luò)服務(wù)。為了簡(jiǎn)化模型,假設(shè)一個(gè)用戶同一時(shí)刻最多只有一個(gè)網(wǎng)絡(luò)任務(wù)。則問(wèn)題描述為

(12)

(13)

(14)

(15)

(16)

(17)

其中,式(12)～式(14)表示網(wǎng)絡(luò)通信節(jié)點(diǎn)功率、總帶寬和最大用戶量的約束;式(15)表示單個(gè)用戶同一時(shí)刻最多只能接入一個(gè)網(wǎng)絡(luò);式(16)表示單個(gè)用戶同一時(shí)刻最多有一個(gè)網(wǎng)絡(luò)任務(wù);式(17)為用戶對(duì)可接入網(wǎng)絡(luò)服務(wù)性能約束。

3.2 SMDP

馬爾可夫決策過(guò)程(Markov decision process,MDP)通過(guò)探索和優(yōu)化,估計(jì)不同狀態(tài)下采取不同的動(dòng)作所能帶來(lái)的長(zhǎng)期收益,由此可以根據(jù)當(dāng)前狀態(tài)選擇最優(yōu)的動(dòng)作,從而獲得長(zhǎng)期最優(yōu)的動(dòng)作策略。SMDP在MDP的基礎(chǔ)上,拓展到在無(wú)限時(shí)間內(nèi)的可數(shù)時(shí)刻上選擇最優(yōu)動(dòng)作。本文中,SAGVN狀態(tài)是不斷變化的,單個(gè)時(shí)刻內(nèi)網(wǎng)絡(luò)整體用戶滿意度最大,無(wú)法保證長(zhǎng)時(shí)間整體用戶滿意度最大,所以采取SMDP的方法來(lái)獲得長(zhǎng)期整體用戶滿意度最大的網(wǎng)絡(luò)任務(wù)分配策略。

盡管本文中決策時(shí)刻發(fā)生在[0,+∞)上任意時(shí)刻,但實(shí)際上只有在有新的用戶請(qǐng)求網(wǎng)絡(luò)服務(wù)和網(wǎng)絡(luò)任務(wù)結(jié)束時(shí)刻需要進(jìn)行網(wǎng)絡(luò)任務(wù)分配的決策。由于網(wǎng)絡(luò)狀態(tài)取決于網(wǎng)絡(luò)任務(wù)分配策略,所以網(wǎng)絡(luò)狀態(tài)變化是一個(gè)馬氏過(guò)程?；谝陨戏治?可以將網(wǎng)絡(luò)服務(wù)分配抽象為SMDP,從而獲得在不同的網(wǎng)絡(luò)狀態(tài)下,對(duì)于不同需求的用戶網(wǎng)絡(luò)服務(wù)請(qǐng)求分配不同網(wǎng)絡(luò)所能獲得的整體用戶滿意度長(zhǎng)期收益,并選擇收益最大的網(wǎng)絡(luò)為用戶提供服務(wù)。

本節(jié)首先定義網(wǎng)絡(luò)狀態(tài)、行動(dòng)、狀態(tài)轉(zhuǎn)移概率和獎(jiǎng)勵(lì)函數(shù),然后介紹價(jià)值迭代算法。

3.2.1 網(wǎng)絡(luò)狀態(tài)空間

定義網(wǎng)絡(luò)狀態(tài):

=(,,…,,|,,…,∈)

(18)

式中：,,…,表示SAGVN內(nèi)無(wú)線通信節(jié)點(diǎn)的狀態(tài)；用來(lái)描述最近一個(gè)服務(wù)數(shù)據(jù)。表示通信節(jié)點(diǎn)的狀態(tài)量,由通信節(jié)點(diǎn)剩余帶寬、剩余功率和剩余用戶量組成:

=(,,|∈)

(19)

定義集合描述網(wǎng)絡(luò)系統(tǒng)所有可能狀態(tài):

(20)

用描述網(wǎng)絡(luò)系統(tǒng)中網(wǎng)絡(luò)任務(wù)結(jié)束時(shí)所有可能的狀態(tài),其中表示為,由結(jié)束任務(wù)所接入的通信節(jié)點(diǎn)和占用的通信節(jié)點(diǎn)功率和帶寬組成:

={(,,…,,)}∈

(21)

假設(shè)通信節(jié)點(diǎn)結(jié)束對(duì)用戶的服務(wù),則表示為

=(,,|∈)

(22)

用描述有新的用戶服務(wù)請(qǐng)求時(shí)所有可能的狀態(tài),其中表示為,由用戶的服務(wù)需求描述和用戶可接入通信節(jié)點(diǎn)組成:

={(,,…,,)}

(23)

(24)

注意，這里沒(méi)有討論用戶對(duì)網(wǎng)絡(luò)最小帶寬、最小信號(hào)強(qiáng)度、最大時(shí)延和最大網(wǎng)絡(luò)費(fèi)用的約束,但實(shí)際操作中,當(dāng)用戶滿意度=0時(shí),網(wǎng)絡(luò)拒絕對(duì)用戶提供服務(wù)。

顯然,,包含了網(wǎng)絡(luò)系統(tǒng)中所有可能狀態(tài),即:=∪。

322 決策時(shí)刻與行動(dòng)集

(25)

當(dāng)=0時(shí)表示網(wǎng)絡(luò)拒絕用戶的服務(wù)請(qǐng)求。本文中,網(wǎng)絡(luò)可以通過(guò)主動(dòng)拒絕現(xiàn)有的用戶服務(wù)請(qǐng)求,為未來(lái)可能的服務(wù)請(qǐng)求預(yù)留網(wǎng)絡(luò)資源。

323 狀態(tài)轉(zhuǎn)移概率

由上文所述,網(wǎng)絡(luò)系統(tǒng)狀態(tài)之間的轉(zhuǎn)換是馬氏過(guò)程,所以轉(zhuǎn)移概率可以直接利用馬氏過(guò)程的狀態(tài)轉(zhuǎn)移速率得到。本文中,狀態(tài)轉(zhuǎn)移速率分為下面幾種情況:

對(duì)于狀態(tài)∈,只可能發(fā)生兩種轉(zhuǎn)移,任務(wù)結(jié)束′∈和一個(gè)服務(wù)請(qǐng)求到來(lái)′∈,其轉(zhuǎn)移速率為

(26)

式中:, 表示網(wǎng)絡(luò)內(nèi)用戶服務(wù)結(jié)束的概率;表示區(qū)域內(nèi)用戶服務(wù)請(qǐng)求概率。

對(duì)于狀態(tài)∈,假設(shè)將用戶′接入通信節(jié)點(diǎn)′,即=′,其轉(zhuǎn)移速率為

(27)

對(duì)于狀態(tài)∈,假設(shè)網(wǎng)絡(luò)拒絕用戶服務(wù)請(qǐng)求,即=0,其轉(zhuǎn)移速率為

(28)

狀態(tài)動(dòng)態(tài)性可以等價(jià)地用嵌入式鏈的狀態(tài)轉(zhuǎn)移概率(′|,)來(lái)表示:

(′|,)=(′|,)·(,)

(29)

式中:(,)表示每個(gè)狀態(tài)的期望逗留時(shí)間。

324 網(wǎng)絡(luò)獎(jiǎng)勵(lì)

為制定優(yōu)化目標(biāo),設(shè)(,)表示當(dāng)采取行動(dòng)時(shí),狀態(tài)下所獲得的永久獎(jiǎng)勵(lì),它是以單位時(shí)間為基礎(chǔ)定義的。本文中,用(,)表示狀態(tài)下采取動(dòng)作后網(wǎng)絡(luò)的整體用戶滿意度,將(,)表示為

(,)=(,)+(,)

(30)

懲罰項(xiàng)(,)反映拒絕用戶服務(wù)請(qǐng)求所帶來(lái)的長(zhǎng)期懲罰,表示為

(,)=-·(′|,=0,∈)

(31)

式中:是網(wǎng)絡(luò)在拒絕用戶服務(wù)請(qǐng)求的單位時(shí)間成本,即拒絕服務(wù)懲罰參數(shù)。

325 離散化時(shí)間

本文利用價(jià)值迭代算法來(lái)解決SMDP問(wèn)題,以確定網(wǎng)絡(luò)在每個(gè)狀態(tài)下所采取的最優(yōu)動(dòng)作。因此,需要一個(gè)單值化階段,將連續(xù)時(shí)間馬氏鏈轉(zhuǎn)換為離散馬氏鏈。

首先,將時(shí)間離散為持續(xù)時(shí)間的區(qū)間,為恒定值,且小于任意狀態(tài)下的期望逗留時(shí)間:

0<<(,),?∈

(32)

然后,對(duì)轉(zhuǎn)移概率進(jìn)行如下修改:

(33)

(34)

326 價(jià)值迭代算法

定義網(wǎng)絡(luò)任務(wù)分配策略(,)是狀態(tài)到動(dòng)作的映射,表示狀態(tài)要采取的動(dòng)作。當(dāng)策略被采用時(shí),

()=,,,…,,…

(35)

(36)

利用價(jià)值迭代算法獲得最優(yōu)策略,具體如算法2所示。

算法 2 價(jià)值迭代算法輸入 折現(xiàn)因子,任意網(wǎng)絡(luò)狀態(tài)量x,迭代精度參數(shù)δ;輸出 最優(yōu)網(wǎng)絡(luò)任務(wù)分配策略π*;過(guò)程1. 初始化V(x);2. 循環(huán)1:最優(yōu)網(wǎng)絡(luò)任務(wù)分配策略π*;3. 初始化前后兩個(gè)策略最大優(yōu)化差值:Δ=0;4. 循環(huán)2:計(jì)算每個(gè)狀態(tài)x∈X的最大預(yù)期長(zhǎng)期折現(xiàn)回報(bào):V(x)←maxa∑x'p(x'|x,a)[R-(x,a)+V(x')]根據(jù)當(dāng)前狀態(tài)下前后兩個(gè)策略差值ν',更新Δ:Δ=max(ν',Δ);5. 如果Δ>δ,返回循環(huán)1;6. 輸出一個(gè)確定的π≈π*,使得:π(x)=arg maxa∑x'p(x'|x,a)[R-(x,a),V(x')]7. 結(jié)束。

3.3 Q-learning算法

雖然SMDP可以得到理論最優(yōu)策略,但是在實(shí)際操作過(guò)程中用戶的服務(wù)結(jié)束概率和服務(wù)請(qǐng)求概率很難獲得,網(wǎng)絡(luò)系統(tǒng)狀態(tài)轉(zhuǎn)移概率難以確定。此外,利用價(jià)值迭代算法計(jì)算SMDP最優(yōu)策略也存在計(jì)算復(fù)雜度高的問(wèn)題,很難應(yīng)用于實(shí)際操作中。Q-learning算法可以通過(guò)不斷與網(wǎng)絡(luò)交互學(xué)習(xí),遞歸獲得近似最優(yōu)策略,是解決MDP實(shí)際操作困難問(wèn)題的常用方法。Q-learning算法雖然最初用于求解MDP,但稍加修改即可應(yīng)用于SMDP。

3.3.1 算法描述

定義狀態(tài)-動(dòng)作對(duì)(,())的價(jià)值函數(shù)(,())。(,())表示網(wǎng)絡(luò)狀態(tài),使用策略的期望長(zhǎng)期折現(xiàn)獎(jiǎng)勵(lì)。目標(biāo)是找到一個(gè)策略,使每個(gè)狀態(tài)的值最大化:

(37)

式中:表示學(xué)習(xí)率(0<<1),決定學(xué)習(xí)到的值會(huì)多大程度上覆蓋舊的值;(,Δ)表示相對(duì)于單個(gè)時(shí)間區(qū)間,用戶在持續(xù)時(shí)間Δ內(nèi)的累計(jì)獎(jiǎng)勵(lì)值:

(38)

式中：是Δ與單位時(shí)間的整數(shù)比值。

332 探索與開發(fā)

在決策過(guò)程中,網(wǎng)絡(luò)會(huì)隨機(jī)或基于以前學(xué)習(xí)的值進(jìn)行決策。為獲得高回報(bào),網(wǎng)絡(luò)可能更傾向于它過(guò)去嘗試過(guò)并發(fā)現(xiàn)有效的行為,即開發(fā)模式。然而,為發(fā)現(xiàn)最為有效的動(dòng)作,網(wǎng)絡(luò)需要嘗試之前沒(méi)有選擇過(guò)的動(dòng)作,即探索模式。Q-learning算法是一種在線迭代學(xué)習(xí)的算法,探索和開發(fā)同時(shí)進(jìn)行。網(wǎng)絡(luò)必須探索各種各樣的行動(dòng),并逐步趨向于最為有效的行動(dòng)。并且,為獲得可靠的值,需要進(jìn)行充分的探索。

本文采取一種-貪婪的探索-開發(fā)策略。在決策過(guò)程中,網(wǎng)絡(luò)以概率()進(jìn)行探索,并以概率1-()利用存儲(chǔ)的值,選擇值最大的動(dòng)作。為提高長(zhǎng)期的網(wǎng)絡(luò)性能,探索永遠(yuǎn)不會(huì)停止,而是會(huì)隨著時(shí)間的推移而減少。定義(,)為狀態(tài)-動(dòng)作對(duì)(,)到當(dāng)前時(shí)間的訪問(wèn)次數(shù)。()為

(39)

為使(,)收斂到最優(yōu)值,將設(shè)為

(40)

具體如算法3所示。

算法 3 Q-learning算法輸入 網(wǎng)絡(luò)系統(tǒng)當(dāng)前狀態(tài)x;輸出 網(wǎng)絡(luò)動(dòng)作a;過(guò)程1. 初始化Q(x,a),狀態(tài)參數(shù)對(duì)出現(xiàn)次數(shù)c(x,a)=0;2. 循環(huán):對(duì)每個(gè)時(shí)間區(qū)間更新Q(x,a);3. 計(jì)算ε(x);如果是探索模式,隨機(jī)選擇動(dòng)作a;如果是開發(fā)模式,選擇動(dòng)作a:Q(x,a)>Q(x,a'), ?a∈A(w)4. 更新c(x,a)=c(x,a)+1;5. 更新Q(x,a):Q(x,a)←Q(x,a)+ρ(R(x,Δt)+κmaxa(Q(x',a')-Q(x,a)))6. 結(jié)束。

4 仿真實(shí)驗(yàn)

4.1 仿真環(huán)境

本文使用python和ns2平臺(tái)搭建了一個(gè)系統(tǒng)級(jí)網(wǎng)絡(luò)仿真環(huán)境。實(shí)驗(yàn)環(huán)境布置LTE基站、虛擬UAV節(jié)點(diǎn)和虛擬衛(wèi)星節(jié)點(diǎn)作為無(wú)線通信節(jié)點(diǎn),為每一個(gè)通信節(jié)點(diǎn)設(shè)置網(wǎng)絡(luò)覆蓋區(qū)域、網(wǎng)絡(luò)資源量和接入用戶上限。假設(shè)不同網(wǎng)絡(luò)使用專用頻段,不存在信道資源競(jìng)爭(zhēng)。網(wǎng)絡(luò)資源由不同網(wǎng)段根據(jù)自身配置自主分配給接入用戶。

為簡(jiǎn)化實(shí)驗(yàn),根據(jù)SAGVN用戶特性,假設(shè)車載網(wǎng)絡(luò)中存在3種用戶網(wǎng)絡(luò)服務(wù)需求,分別為非實(shí)時(shí)服務(wù)(non-real time, NRT)、實(shí)時(shí)服務(wù)(real time, RT)和時(shí)延敏感服務(wù)(delay sensibility, DS)。其中,NRT由傳統(tǒng)的數(shù)據(jù)流生成,比如車內(nèi)用戶進(jìn)行郵件下載、網(wǎng)上沖浪等,對(duì)帶寬需求較高;RT由視頻流或語(yǔ)言流生成,比如道路實(shí)時(shí)監(jiān)控或者車內(nèi)通話等,對(duì)帶寬和時(shí)延要求較高;DS是由汽車自動(dòng)駕駛,事故應(yīng)急響應(yīng)等需要低時(shí)延的應(yīng)用生成。網(wǎng)絡(luò)系統(tǒng)內(nèi)類用戶(∈{NRT,RT,DS})服務(wù)請(qǐng)求速率服從參數(shù)為的泊松分布,服務(wù)時(shí)長(zhǎng)服從參數(shù)為的指數(shù)分布。實(shí)驗(yàn)拓?fù)湓斎鐖D3所示,參數(shù)設(shè)置如表1和表2所示。

圖3 實(shí)驗(yàn)拓?fù)銯ig.3 Experimental topology

表1 用戶參數(shù)

表2 SAGVN參數(shù)

4.2 實(shí)驗(yàn)結(jié)果分析

在網(wǎng)絡(luò)相對(duì)穩(wěn)定后,選取隨機(jī)時(shí)間作為初始時(shí)刻,間隔固定時(shí)長(zhǎng)=0.12 s收集網(wǎng)絡(luò)數(shù)據(jù)。為了驗(yàn)證本文算法的有效性,將其與文獻(xiàn)[29]所提出的基于自適應(yīng)閾值移動(dòng)負(fù)載均衡(mobility load balancing, MLB)策略對(duì)比。區(qū)分網(wǎng)絡(luò)資源充足和網(wǎng)絡(luò)擁塞兩種網(wǎng)絡(luò)環(huán)境,主要從整體用戶滿意度和服務(wù)拒絕率兩個(gè)方面指標(biāo)來(lái)討論不同服務(wù)分配策略性能。

其中,類服務(wù)拒絕率計(jì)算公式如下:

(41)

網(wǎng)絡(luò)系統(tǒng)對(duì)用戶服務(wù)請(qǐng)求的拒絕率反映了網(wǎng)絡(luò)系統(tǒng)擁塞程度,計(jì)算公式如下:

(42)

式中：為類服務(wù)被網(wǎng)絡(luò)拒絕的次數(shù)；為網(wǎng)絡(luò)持續(xù)時(shí)間。

4.2.1 網(wǎng)絡(luò)資源充足環(huán)境

圖4給出網(wǎng)絡(luò)資源充足環(huán)境下不同服務(wù)分配策略的整體用戶滿意度。從圖4可以看出,SMDP可以得到最優(yōu)的網(wǎng)絡(luò)系統(tǒng)整體用戶滿意度。將每一時(shí)間區(qū)間作為一個(gè)時(shí)步,Q-learning算法進(jìn)行20 000步(持續(xù)時(shí)間=2 400 s),整體用戶滿意度接近于SMDP,同時(shí)相較于自適應(yīng)MLB策略,整體用戶滿意度提升了超過(guò)30%。

不同于MLB策略,基于學(xué)習(xí)的方法可以通過(guò)增加學(xué)習(xí)周期,不斷趨近于最優(yōu)解。從圖4可以看出,Q-learning算法進(jìn)行5 000步(持續(xù)時(shí)間=600 s)相較于2 000步(=2 400 s),由于學(xué)習(xí)不充分,整體用戶滿意度下降超過(guò)20%。

圖4 網(wǎng)絡(luò)資源充足環(huán)境中整體用戶滿意度對(duì)比Fig.4 Comparison of overall user satisfaction in the environment of adequate network resources

4.2.2 網(wǎng)絡(luò)擁塞環(huán)境

隨著網(wǎng)絡(luò)擁塞程度的上升,網(wǎng)絡(luò)系統(tǒng)對(duì)用戶服務(wù)請(qǐng)求的拒絕率對(duì)網(wǎng)絡(luò)整體用戶滿意度的影響不斷增加,本文對(duì)網(wǎng)絡(luò)擁塞環(huán)境做單獨(dú)討論。圖5和圖6分別給出了網(wǎng)絡(luò)擁塞環(huán)境下Q-learning算法和自適應(yīng)MLB策略網(wǎng)絡(luò)系統(tǒng)整體用戶滿意度和服務(wù)拒絕率。

圖5 網(wǎng)絡(luò)擁塞環(huán)境下不同服務(wù)分配策略整體用戶滿意度對(duì)比Fig.5 Comparison of overall user satisfaction with different service allocation strategies in the environment of network congestion

圖6 網(wǎng)絡(luò)擁塞環(huán)境中網(wǎng)絡(luò)服務(wù)拒絕率對(duì)比Fig.6 Comparison of network service rejection rate in the environment of network congestion

從圖5可以看出,在網(wǎng)絡(luò)擁塞環(huán)境下,Q-learning算法相較于自適應(yīng)MLB策略整體用戶滿意度上升大約5%。從圖6可以看出,使用Q-learning算法,網(wǎng)絡(luò)系統(tǒng)對(duì)用戶服務(wù)拒絕率相較于使用自適應(yīng)MLB策略下降超過(guò)40%。

考慮到實(shí)際操作中,不同服務(wù)對(duì)網(wǎng)絡(luò)需求的迫切程度不一樣,簡(jiǎn)單設(shè)置不同類別服務(wù)的拒絕懲罰參數(shù),無(wú)法有效反映不同用戶實(shí)際需求。比如車輛自動(dòng)駕駛,即使在網(wǎng)絡(luò)擁塞的環(huán)境下,也需要實(shí)時(shí)將車輛信息上傳到數(shù)據(jù)中心處理,所以網(wǎng)絡(luò)需要優(yōu)先保障此類服務(wù)請(qǐng)求。隨著車載網(wǎng)絡(luò)用戶量不斷增加,網(wǎng)絡(luò)擁塞將是一個(gè)難以避免的問(wèn)題,對(duì)一些對(duì)網(wǎng)絡(luò)服務(wù)需求迫切的信息優(yōu)先保障其網(wǎng)絡(luò)服務(wù)具有很強(qiáng)的現(xiàn)實(shí)意義。在本文實(shí)驗(yàn)環(huán)境中,假設(shè)存在網(wǎng)絡(luò)任務(wù)對(duì)網(wǎng)絡(luò)服務(wù)需求相較于其他類別任務(wù)更為迫切,因而網(wǎng)絡(luò)拒絕這個(gè)服務(wù)對(duì)用戶整體滿意度的影響更大,拒絕服務(wù)懲罰參數(shù)應(yīng)該設(shè)置更高。

圖7給出了基于Q-learning算法不同拒絕服務(wù)懲罰參數(shù)設(shè)置(見(jiàn)表3)的網(wǎng)絡(luò)服務(wù)拒絕率,圖8給出了對(duì)應(yīng)參數(shù)設(shè)置下,對(duì)網(wǎng)絡(luò)需求迫切服務(wù)的拒絕率。可以看出,通過(guò)合理調(diào)整拒絕服務(wù)懲罰參數(shù),可以在網(wǎng)絡(luò)系統(tǒng)整體服務(wù)拒絕率基本不變的情況下,使網(wǎng)絡(luò)需求迫切服務(wù)拒絕率有明顯下降。

圖7 不同服務(wù)懲罰參數(shù)網(wǎng)絡(luò)服務(wù)請(qǐng)求的拒絕率Fig.7 Rejection rate of service requests by networks with different service penalty parameters

表3 拒絕服務(wù)懲罰參數(shù)βl

圖8 不同服務(wù)懲罰參數(shù)設(shè)置下需求迫切網(wǎng)絡(luò)服務(wù)請(qǐng)求的拒絕率Fig.8 Rejection rate of urgent service requests with different service penalty parameters

通過(guò)調(diào)整拒絕服務(wù)懲罰參數(shù)來(lái)降低網(wǎng)絡(luò)對(duì)相應(yīng)服務(wù)請(qǐng)求的拒絕率,既可以有目的性地降低對(duì)網(wǎng)絡(luò)服務(wù)需求迫切用戶服務(wù)請(qǐng)求的拒絕率,又可以充分利用網(wǎng)絡(luò)資源,能夠有效解決當(dāng)前由于網(wǎng)絡(luò)數(shù)據(jù)量激增而導(dǎo)致的網(wǎng)絡(luò)擁塞問(wèn)題。下一步,如何調(diào)整拒絕服務(wù)懲罰參數(shù)以實(shí)現(xiàn)網(wǎng)絡(luò)對(duì)用戶服務(wù)請(qǐng)求拒絕率的有效控制,以及如何設(shè)定可以充分滿足用戶需求的最優(yōu)拒絕服務(wù)懲罰參數(shù)將會(huì)是研究的重點(diǎn)。

5 結(jié)束語(yǔ)

本文主要針對(duì)網(wǎng)絡(luò)中用戶整體滿意度最大的網(wǎng)絡(luò)任務(wù)分配策略進(jìn)行研究。基于多種影響因素,構(gòu)建了用戶需求和滿意度描述框架?；谟脩粜枨蠛陀脩魸M意度,提出了基于SMDP的網(wǎng)絡(luò)任務(wù)分配策略,通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了所提策略的優(yōu)勢(shì)。但是,現(xiàn)實(shí)情況往往比想象中更為復(fù)雜,仍有一些問(wèn)題有待進(jìn)一步研究:

(1) SAGVN的可拓展性。針對(duì)隨機(jī)接入的無(wú)線通信節(jié)點(diǎn)和車載用戶,需要構(gòu)建更為高效的網(wǎng)絡(luò)管理框架,更快將其納入網(wǎng)絡(luò)管理系統(tǒng)。

(2) SAGVN網(wǎng)絡(luò)的能量消耗。能量消耗是制約SAGVN發(fā)展的重要問(wèn)題,需要有效的能量管理策略。

(3) 網(wǎng)絡(luò)分片。結(jié)合網(wǎng)絡(luò)功能虛擬化技術(shù)對(duì)網(wǎng)絡(luò)分片,為特定用戶提供定制服務(wù)。