基于接入請(qǐng)求時(shí)空分布的延遲容忍上傳接入控制方法

陳 麗 鄧 琨 蔣 濤 樂光學(xué) 李攀攀 楊 俊 徐旭寶

(嘉興學(xué)院數(shù)理與信息工程學(xué)院 浙江嘉興 314001)

海洋觀測(cè)數(shù)據(jù)蘊(yùn)含著巨大的價(jià)值,為人類深入地認(rèn)知、管理和利用海洋提供了前所未有的豐富信息[1].負(fù)責(zé)收集海洋信息的觀測(cè)節(jié)點(diǎn)一般配備一種或多種傳感器收集觀測(cè)數(shù)據(jù),并且具有上傳數(shù)據(jù)的無線通信能力.一般按是否移動(dòng)將觀測(cè)節(jié)點(diǎn)分為2類：1)隨機(jī)部署的固定觀測(cè)節(jié)點(diǎn)如浮標(biāo)、潛標(biāo)等;2)機(jī)載、艇載或船載各種傳感器的無人艇[2]、無人機(jī)、調(diào)查監(jiān)測(cè)船甚至漁船、貨船等移動(dòng)觀測(cè)節(jié)點(diǎn).與固定觀測(cè)節(jié)點(diǎn)相比,移動(dòng)觀測(cè)節(jié)點(diǎn)的計(jì)算和存儲(chǔ)等能力一般都較強(qiáng),能量不受限制而且觀測(cè)區(qū)域也不受位置局限.在人類對(duì)海洋開發(fā)需求的不斷增長(zhǎng)以及移動(dòng)互聯(lián)網(wǎng)等技術(shù)的快速發(fā)展的共同驅(qū)動(dòng)下,高計(jì)算和存儲(chǔ)能力的移動(dòng)觀測(cè)節(jié)點(diǎn)呈爆發(fā)式增長(zhǎng).海洋觀測(cè)數(shù)據(jù)的獲取是海洋環(huán)境保護(hù)、防災(zāi)減災(zāi)、資源開發(fā)以及科學(xué)研究等[3-4]的依托與保障.盡管目前已有大量相關(guān)研究,但主要集中在固定觀測(cè)臺(tái)以及隨機(jī)布撒的固定觀測(cè)節(jié)點(diǎn)的研究,如無線組網(wǎng)、端到端以及端到匯聚節(jié)點(diǎn)傳輸調(diào)度、數(shù)據(jù)聚集等.但是現(xiàn)有技術(shù)卻很難適應(yīng)于觀測(cè)節(jié)點(diǎn)快速移動(dòng)的數(shù)據(jù)收集的需要.移動(dòng)接入上傳觀測(cè)數(shù)據(jù)面臨許多亟待解決的新問題與挑戰(zhàn).

在海洋觀測(cè)過程中,機(jī)載、艇載或船載移動(dòng)觀測(cè)節(jié)點(diǎn)連續(xù)地收集并存儲(chǔ)所觀測(cè)的數(shù)據(jù).在經(jīng)過無線接入點(diǎn)(access point, AP)的通信覆蓋區(qū)域時(shí),這些移動(dòng)觀測(cè)節(jié)點(diǎn)才有機(jī)會(huì)接入Internet上傳數(shù)據(jù).然而,移動(dòng)觀測(cè)節(jié)點(diǎn)的速度一般都比較快,行經(jīng)AP通信覆蓋區(qū)域的時(shí)間會(huì)比較短,這就限制了可能接入Internet的時(shí)長(zhǎng).而且在海洋觀測(cè)系統(tǒng)中AP的部署一般都較為稀疏,那么相對(duì)于移動(dòng)觀測(cè)節(jié)點(diǎn)以及所需上傳觀測(cè)數(shù)據(jù)的數(shù)量,其通信資源成為競(jìng)爭(zhēng)激烈的稀缺資源.移動(dòng)接入請(qǐng)求對(duì)AP通信資源的爭(zhēng)用,使得移動(dòng)接入調(diào)度問題成為提升海洋觀測(cè)信息獲取效率的重要研究?jī)?nèi)容.

現(xiàn)有接入調(diào)度機(jī)制通常將網(wǎng)絡(luò)吞吐量、數(shù)據(jù)傳輸?shù)膶?shí)時(shí)性等作為研究目標(biāo)[5],為簡(jiǎn)化研究將多性能指標(biāo)泛化為“收益”.據(jù)網(wǎng)上公開的文獻(xiàn)調(diào)研發(fā)現(xiàn),現(xiàn)有移動(dòng)接入調(diào)度機(jī)制在處理沒被調(diào)度的接入請(qǐng)求時(shí),其收益被忽略或作為0來處理.即當(dāng)接入請(qǐng)求不被調(diào)度時(shí),則沒有收益.然而,考慮到現(xiàn)實(shí)應(yīng)用各觀測(cè)節(jié)點(diǎn)的移動(dòng)軌跡不同,顯而易見在截止時(shí)間內(nèi)是否途徑AP以及被調(diào)度可能性也存在很大差異.如有些接入請(qǐng)求被調(diào)度是大概率事件;而有些被調(diào)度的概率則非常小.

本文研究保證觀測(cè)數(shù)據(jù)延遲容忍[6-8]前提下的時(shí)空動(dòng)態(tài)移動(dòng)接入請(qǐng)求的最優(yōu)化調(diào)度方法.在實(shí)際海洋觀測(cè)系統(tǒng)中,延遲容忍限制內(nèi)(如截止時(shí)間)獲得的觀測(cè)數(shù)據(jù)才具有實(shí)際應(yīng)用價(jià)值.

本文的主要貢獻(xiàn)有4個(gè)方面:

1) 對(duì)移動(dòng)接入請(qǐng)求的動(dòng)態(tài)特征通過構(gòu)建時(shí)空數(shù)據(jù)模型(“流”請(qǐng)求詳見定義1)進(jìn)行描述;

2) 對(duì)截止時(shí)間內(nèi)各移動(dòng)接入請(qǐng)求被調(diào)度的隨機(jī)性進(jìn)行分析,并通過量化其“未來收益”并引入到目標(biāo)函數(shù);

3) 在觀測(cè)數(shù)據(jù)截止時(shí)間約束的條件下,提出基于接入請(qǐng)求時(shí)空特征量化分析的收益最大化的移動(dòng)接入控制方法;

4) 應(yīng)用不同移動(dòng)接入請(qǐng)求數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明,提出的移動(dòng)接入控制算法可以有效提升其性能.

1 相關(guān)工作

無線通信資源傳輸調(diào)度是海洋觀測(cè)系統(tǒng)的一個(gè)重要研究?jī)?nèi)容.被調(diào)度對(duì)象一般為AP的信道或時(shí)隙等,并且通常以網(wǎng)絡(luò)吞吐量、數(shù)據(jù)傳輸?shù)膶?shí)時(shí)性或公平等指標(biāo)作為調(diào)度目標(biāo),如文獻(xiàn)[6-9]分別基于傳輸延遲[6]、公平性[7]以及截止時(shí)間[8-9]作為指標(biāo)來研究提高網(wǎng)絡(luò)通信性能的調(diào)度方法.綜合已有文獻(xiàn)可以看出,不同應(yīng)用其需求也各不相同,從而對(duì)各個(gè)性能指標(biāo)的偏好程度及側(cè)重點(diǎn)也各不相同.本文將多個(gè)主要性能指標(biāo)泛化為“收益”,將其作為衡量性能優(yōu)劣的指標(biāo),其計(jì)算公式詳見3.2節(jié)的描述.

在無線傳感網(wǎng)中,觀測(cè)節(jié)點(diǎn)被隨機(jī)布撒在觀測(cè)區(qū)域,節(jié)點(diǎn)間通過自組織方式進(jìn)行組網(wǎng).Ramanathan等人[9-10]采用集中啟發(fā)式方法進(jìn)行傳輸調(diào)度;Sen等人[11]以最大化網(wǎng)絡(luò)吞吐量為目標(biāo)優(yōu)化單個(gè)時(shí)間槽內(nèi)最大傳輸集,并以令牌深度優(yōu)先搜索方法實(shí)現(xiàn)集中的啟發(fā)式廣播傳輸調(diào)度;而孫利民等人[12]采用分布式方法基于TDMA進(jìn)行傳輸調(diào)度以提高網(wǎng)絡(luò)通信性能.

保證觀測(cè)數(shù)據(jù)的延遲容忍的有效接入調(diào)度機(jī)制是一個(gè)非常關(guān)鍵的研究問題.文獻(xiàn)[13-14]歸納了時(shí)延受限的移動(dòng)式數(shù)據(jù)收集的各類方法的特點(diǎn),分析了這些方法的優(yōu)缺點(diǎn)和適用范圍,總結(jié)了存在的主要問題.Lin等人[15]在TRITON項(xiàng)目中,探索使用基于WiMAX技術(shù)進(jìn)行具有延遲容忍網(wǎng)絡(luò)功能的超視距移動(dòng)觀測(cè)節(jié)點(diǎn)間的通信,并且比較分析了不同路由方案的性能.

綜上所述,現(xiàn)有研究在觀測(cè)節(jié)點(diǎn)位置不發(fā)生變化的場(chǎng)景中的網(wǎng)絡(luò)吞吐量、實(shí)時(shí)性或公平性等某個(gè)指標(biāo)上表現(xiàn)出良好的性能.但應(yīng)用于觀測(cè)節(jié)點(diǎn)快速移動(dòng)的數(shù)據(jù)上傳的應(yīng)用場(chǎng)景時(shí),無法滿足性能需求.

2 系統(tǒng)模型與假設(shè)

本節(jié)我們將簡(jiǎn)要介紹系統(tǒng)的模型和相關(guān)假設(shè).在海洋觀測(cè)系統(tǒng)中,我們假設(shè)無線接入節(jié)點(diǎn)AP之間相互連接并有線接入Internet,可以為其通信范圍內(nèi)的移動(dòng)觀測(cè)節(jié)點(diǎn)提供無線Internet的接入.在其通信覆蓋區(qū)域的觀測(cè)節(jié)點(diǎn)可通過AP接入Internet進(jìn)行數(shù)據(jù)上傳,而在其他區(qū)域內(nèi)無法接入.

眾所周知，GPS導(dǎo)航系統(tǒng)越來越受歡迎,并且越來越多的人依賴于它.現(xiàn)在大部分移動(dòng)觀測(cè)節(jié)點(diǎn)都安裝了基于GPS的導(dǎo)航系統(tǒng).假設(shè)移動(dòng)觀測(cè)節(jié)點(diǎn)都配置了GPS與無線通信模塊,其接入請(qǐng)求以及自身的移動(dòng)軌跡信息往往都是短文本,適合長(zhǎng)距離通信;而其采集到的觀測(cè)數(shù)據(jù)與之相比就要大得多,更適合傳輸速率快、通信質(zhì)量高的無線局域網(wǎng)進(jìn)行上傳,如WiFi連接方式.假設(shè)移動(dòng)觀測(cè)節(jié)點(diǎn)的通信半徑及傳輸速率都相同,并且周期性地通過長(zhǎng)距離通信方式向AP報(bào)告當(dāng)前的狀態(tài),如位置及軌跡信息等.

本文觀察發(fā)現(xiàn)海洋觀測(cè)節(jié)點(diǎn)的無線接入請(qǐng)求的產(chǎn)生、存續(xù)以及終結(jié)會(huì)隨時(shí)空動(dòng)態(tài)變化,并對(duì)其動(dòng)態(tài)特征進(jìn)行量化分析,模型化為“流”請(qǐng)求.基于“流”模型的移動(dòng)接入調(diào)度模型如圖1所示.該系統(tǒng)模型簡(jiǎn)要展示了其調(diào)度過程的4個(gè)步驟：

① 獲取當(dāng)前待調(diào)度移動(dòng)接入請(qǐng)求位置、軌跡等信息，并輸入系統(tǒng);

② 基于“流”請(qǐng)求模型對(duì)移動(dòng)接入請(qǐng)求進(jìn)行量化處理;

③ 基于本文提出的移動(dòng)接入優(yōu)化調(diào)度方法P-RSA進(jìn)行計(jì)算;

④ 基于計(jì)算結(jié)果對(duì)移動(dòng)觀測(cè)節(jié)點(diǎn)的接入請(qǐng)求實(shí)施調(diào)度操作.

Fig. 1 The mobile access scheduling system model based on ‘Flow’ 圖1 基于“流”請(qǐng)求的移動(dòng)接入調(diào)度系統(tǒng)模型

3 問題的形式化

本節(jié)我們將上傳接入請(qǐng)求未來軌跡信息對(duì)當(dāng)前調(diào)度性能影響，通過構(gòu)建抽象模型進(jìn)行量化分析并引入到移動(dòng)接入調(diào)度的優(yōu)化模型.

我們主要對(duì)保證觀測(cè)數(shù)據(jù)延遲容忍前提下總收益最大化的接入控制問題進(jìn)行形式化描述.首先,對(duì)相關(guān)定義及符號(hào)進(jìn)行描述;然后,討論如何基于軌跡信息構(gòu)建描述移動(dòng)接入請(qǐng)求動(dòng)態(tài)特征的抽象模型;最后,對(duì)時(shí)空動(dòng)態(tài)變化的無線通信請(qǐng)求的接入控制問題進(jìn)行描述.

3.1 相關(guān)定義及符號(hào)

在海洋觀測(cè)的應(yīng)用場(chǎng)景中,觀測(cè)節(jié)點(diǎn)在移動(dòng)過程中找機(jī)會(huì)將收集到的觀測(cè)數(shù)據(jù)上傳到數(shù)據(jù)中心.當(dāng)穿過某個(gè)AP的無線通信覆蓋區(qū)域時(shí),通過AP的調(diào)度,有機(jī)會(huì)接入Internet上傳觀測(cè)數(shù)據(jù).

相對(duì)于觀測(cè)節(jié)點(diǎn),本文更關(guān)注其移動(dòng)接入請(qǐng)求.隨著觀測(cè)節(jié)點(diǎn)的快速移動(dòng)，其接入請(qǐng)求的空間位置在不斷變化.在觀測(cè)數(shù)據(jù)延遲容忍時(shí)間內(nèi),若觀測(cè)節(jié)點(diǎn)在移動(dòng)過程中,途徑多個(gè)AP的通信覆蓋區(qū)域,那么該節(jié)點(diǎn)的接入請(qǐng)求就有多次被調(diào)度的機(jī)會(huì).

本文構(gòu)建描述移動(dòng)接入請(qǐng)求時(shí)空動(dòng)態(tài)特征的抽象模型,即流請(qǐng)求,詳見定義1.流請(qǐng)求是關(guān)于AP的一個(gè)隨機(jī)時(shí)間序列.

定義1.流請(qǐng)求.在觀測(cè)數(shù)據(jù)的生存時(shí)間內(nèi)(time to live, TTL),設(shè)移動(dòng)觀測(cè)節(jié)點(diǎn)ni途徑k個(gè)AP的通信覆蓋區(qū)域ai1ai2…ai k,若k≥1,將其上傳接入請(qǐng)求用AP的時(shí)間序列表示,并稱fi=(ai1,pi1),(ai2,pi2),…,(ai j,pi j),…,(ai k,pi k)為流請(qǐng)求,其中ni∈N,ai j∈A,集合A和N分別為AP節(jié)點(diǎn)集以及移動(dòng)觀測(cè)節(jié)點(diǎn)集,pi j為節(jié)點(diǎn)ni經(jīng)過AP節(jié)點(diǎn)ai j的概率.

3.2 問題的形式化描述

本節(jié)從優(yōu)化的角度分析,在接入請(qǐng)求TTL時(shí)間內(nèi)如何進(jìn)行控制接入,才能夠使得有限信道資源的收益最大化.問題的形式化描述,詳見定義2和定義3.

定義2.AP接入控制優(yōu)化問題(access requests scheduling by AP, RSA).給定AP信道容量為V、其通信范圍內(nèi)帶生存時(shí)間TTL的接入請(qǐng)求集合R.求使得待調(diào)度接入請(qǐng)求當(dāng)前收益總和最大化的優(yōu)化調(diào)度,其目標(biāo)函數(shù)：

(1)

(2)

由于評(píng)價(jià)接入請(qǐng)求調(diào)度各性能屬性的量綱不同(如吞吐量、延遲等),對(duì)原始性能屬性值進(jìn)行歸一化處理,其轉(zhuǎn)換為界于某一特定范圍的數(shù)據(jù),以消除量綱和數(shù)量級(jí)的影響.

設(shè)xi表示AP對(duì)接入請(qǐng)求ri的控制決策,xi∈{0,1},ri∈R.當(dāng)xi=1時(shí),表示接入請(qǐng)求ri被AP調(diào)度，可以接入Internet上傳數(shù)據(jù);當(dāng)xi=0時(shí),表示ri被AP拒絕,不可以接入Internet.那么,RSA問題可以歸結(jié)為尋找一個(gè)滿足上述約束方程,并且使得目標(biāo)函數(shù)達(dá)到最大值的解向量X=(x1,x2,…,xn).

在現(xiàn)實(shí)中,隨著觀測(cè)節(jié)點(diǎn)的快速移動(dòng)其位置在動(dòng)態(tài)變化,從而途經(jīng)AP通信覆蓋的時(shí)間也存在很大的不確定性.通過已有基于觀測(cè)節(jié)點(diǎn)的GPS、當(dāng)前速度以及加速度等信息進(jìn)行軌跡預(yù)測(cè)研究方法,可以獲得其軌跡相關(guān)信息，進(jìn)而可以預(yù)測(cè)各個(gè)接入請(qǐng)求未來被AP調(diào)度的概率.

定義3.AP基于預(yù)測(cè)軌跡的接入控制優(yōu)化問題(access requests scheduling by AP based on predicted trajectory, P-RSA).給定AP信道容量為V、其通信范圍內(nèi)帶生存時(shí)間TTL的接入請(qǐng)求集合R.基于流請(qǐng)求模型(詳見定義1)fi=(ai1,pi1),(ai2,pi2),…,(ai j,pi j),…,求使得在TTL時(shí)間內(nèi)待調(diào)度接入請(qǐng)求集總收益最大化的優(yōu)化調(diào)度,其目標(biāo)函數(shù)：

(3)

其中，xi表示AP對(duì)接入請(qǐng)求fi的控制決策,xi∈{0,1},fi∈R.

當(dāng)xi=1時(shí),表示當(dāng)前AP節(jié)點(diǎn)接收接入請(qǐng)求fi,其收益為xi×wi;

當(dāng)xi=0時(shí),表示當(dāng)前AP節(jié)點(diǎn)拒絕該請(qǐng)求,其收益的計(jì)算為

(4)

其中,α為接入請(qǐng)求fi在其TTL時(shí)間內(nèi)被調(diào)度的影響因子,表示時(shí)間延遲對(duì)收益wi帶來增益(若α>1)或折扣(若α<1).

與RSA問題類似,P-RSA問題歸結(jié)為尋找一個(gè)滿足上述約束方程,并使目標(biāo)函數(shù)值(式(3))達(dá)到最大的解向量X.

4 問題分析

本節(jié)首先對(duì)RSA與P-RSA問題的難度進(jìn)行分析，定理證明過程如定理1所示.

定理1.RSA與P-RSA這2個(gè)問題都是NP-難問題.

同理可證,P-RSA問題的實(shí)例也可歸約為一個(gè)0-1背包問題,所以該問題也是NP-難的.綜上所述,定理1得證.

證畢.

定理1的證明說明RSA和P-RSA這2個(gè)問題的難度都是NP的,因此無法在多項(xiàng)式時(shí)間內(nèi)求得最優(yōu)解.本文擬基于動(dòng)態(tài)規(guī)劃思想給出求解該問題的近似算法,下面將通過定理2的證明,驗(yàn)證這2個(gè)問題具有最優(yōu)子結(jié)構(gòu).

定理2.RSA和P-RSA問題都具有最優(yōu)子結(jié)構(gòu).

證明. 假設(shè)(z1,z2,…,zk)是問題fk(weight)的最優(yōu)解,那么:

1) 對(duì)于任意1≤j≤k,有zj=1,則有(z1,z2,…,zj-1,zj+1,…,zk)是問題fk-1(weight-w[j])+value[j]的最優(yōu)解;

2) 對(duì)于任意1≤j≤k,有zj=0,則有(z1,z2,…,zj-1,zj+1,…,zk)是問題fk-1(weight)的最優(yōu)解.

同理可證P-RSA問題也具有最優(yōu)子結(jié)構(gòu).因此,定理2得證.

證畢.

定理2已經(jīng)證明了RSA問題具有最優(yōu)子結(jié)構(gòu),下面遞歸定義RSA問題的最優(yōu)解的值.每個(gè)觀測(cè)節(jié)點(diǎn)只有一個(gè)接入請(qǐng)求,可以接受該接入請(qǐng)求也可以拒絕.用子問題定義狀態(tài)：即f[n][v]表示n個(gè)請(qǐng)求接入一個(gè)信道資源為V的AP可以獲得的最大收益,則其狀態(tài)轉(zhuǎn)移方程為

f[i][v]=max((f[i-1][v]),
(f[i-1][v-c[i]]+w[i])),

(5)

其中,f[i][j]表示前i個(gè)請(qǐng)求接入可用信道資源為j的收益總和,f[i][0]=f[0][j]=0.其中第i個(gè)接入請(qǐng)求所占信道資源為c[i],收益為w[i];若只考慮第i個(gè)接入請(qǐng)求的策略(接入或不接入),那么就可以轉(zhuǎn)化為一個(gè)剩余n-1個(gè)接入請(qǐng)求的接入調(diào)度問題.如果拒絕第i個(gè)請(qǐng)求接入,即x[i]=0,那么問題轉(zhuǎn)化為n-1個(gè)接入請(qǐng)求接入容量為V的AP的問題,價(jià)值為f[n-1][v];若第i個(gè)請(qǐng)求被AP接受而接入,即x[i]=1,那么問題就轉(zhuǎn)化為其余i-1個(gè)接入請(qǐng)求接入剩下的信道資源為v-c[i]的AP中,此時(shí)能獲得的最大價(jià)值就是f[n-1][v-c[i]]再加上通過放入第i個(gè)接入請(qǐng)求獲得的收益w[i].

5 P-RSA算法

NP難問題RSA與P-RSA無法在多項(xiàng)式時(shí)間內(nèi)得到精確優(yōu)化解,并且通過定理2的證明驗(yàn)證了這2個(gè)問題具有最優(yōu)子結(jié)構(gòu)等性質(zhì).本節(jié)基于動(dòng)態(tài)規(guī)劃思想給出求解RSA和P-RSA優(yōu)化問題的近似算法.自下而上進(jìn)行計(jì)算,最后由計(jì)算結(jié)果構(gòu)造一個(gè)最優(yōu)解.

本節(jié)在算法1中給出了求解接入控制優(yōu)化問題的RSA近似算法,如算法1所示.算法1的輸出結(jié)果為接入請(qǐng)求延遲容忍時(shí)間內(nèi)收益最大的解向量X.

算法1.RSA算法.

輸入：n個(gè)請(qǐng)求接入、AP可用信道資源為V、每個(gè)接入請(qǐng)求需要占用的信道資源為C={c[1],c[2],…,c[n]}，其收益為W={w[1],w[2],…,w[n]}；

輸出：X=(x[1],x[2],…,x[n])*最優(yōu)接入請(qǐng)求集合,即使目標(biāo)函數(shù)達(dá)到最大的解向量*

① for (i=1;i≤n;i=i+1)*第1個(gè)階段*

②f[i][0]=0;*f[i][j]表示前i個(gè)請(qǐng)求接入AP的收益總和*

③x[i]=0;*x[i]∈{0,1}表示AP對(duì)接入請(qǐng)求r[i]的控制決策.x[i]=1表示r[i]被AP調(diào)度;而x[i]=0表示不被調(diào)度*

④ end for

⑤ for (intj=0;j≤V;j++)*其他n-1個(gè)階段*

⑥f[0][j]=0;

⑦ for (inti=1;i≤n;i++)

⑧ for (intj=1;j≤V;j++)

⑨ if (j

⑩f[i][j]=f[i-1][j];

求解AP基于預(yù)測(cè)軌跡的接入控制優(yōu)化問題的P-RSA近似算法,如算法2所示.在給定通信資源V、接入請(qǐng)求集合R以及流請(qǐng)求信息ri=(ai1,pi1),(ai2,pi2),…,(ai j,pi j),…條件下,求使得在TTL時(shí)間內(nèi)待調(diào)度接入請(qǐng)求集總收益最大化的解向量X.

算法2.P-RSA算法.

輸入：V，C={c[1],c[2],…,c[n]}，W={w[1],w[2],…,w[n]},ri=(ai1,pi1),(ai2,pi2),…,(ai j,pi j),…*觀測(cè)節(jié)點(diǎn)ni經(jīng)過AP節(jié)點(diǎn)ai j的概率為pi j的流請(qǐng)求ri∈R*

輸出：X=(x[1],x[2],…,x[n])*最優(yōu)接入請(qǐng)求集合,即使目標(biāo)函數(shù)達(dá)到最大的解向量*

① for (i=1;i≤n;i=i+1)*第1個(gè)階段*

②f[i][0]=0;*f[i][j]表示前i個(gè)請(qǐng)求接入AP的收益總和*

③x[i]=0;*x[i]∈{0,1}表示AP對(duì)接入請(qǐng)求r[i]的控制決策.x[i]=1表示r[i]被AP調(diào)度;而x[i]=0表示不被調(diào)度*

④ end for

⑤ if (j

⑥f[i][j]=max(f[i-1][j]+(1-xi)×

⑦ else

⑧f[i][j]=max(f[i-1][j-c[i]]+w[i])

⑨ end if

在AP節(jié)點(diǎn)通信覆蓋范圍內(nèi),若待調(diào)度移動(dòng)接入請(qǐng)求的未來軌跡信息已知(或通過預(yù)測(cè)可以獲得),即觀測(cè)節(jié)點(diǎn)在其接入請(qǐng)求的TTL時(shí)間內(nèi)將經(jīng)過的AP節(jié)點(diǎn)的序列.本文提出基于預(yù)測(cè)軌跡的時(shí)空穿越控制方法P-RSA.首先,構(gòu)建移動(dòng)接入請(qǐng)求軌跡的預(yù)測(cè)模型.移動(dòng)接入請(qǐng)求ri的軌跡表示為,其中為ri軌跡經(jīng)過的AP節(jié)點(diǎn),為經(jīng)過的概率.觀測(cè)節(jié)點(diǎn)的軌跡信息可以通過AIS、GPS等記錄的位置、速度、加速度及導(dǎo)航等信息的計(jì)算來進(jìn)行預(yù)測(cè)獲得[16],P-RSA算法的如算法2所示.

當(dāng)然,若所有移動(dòng)接入請(qǐng)求的未來軌跡信息都未知且無法獲得,則退化為第1種情況,基于RSA算法來進(jìn)行求解.

6 模擬實(shí)驗(yàn)與性能分析

本文采用MATLAB搭建仿真環(huán)境,使用LINGO求解優(yōu)化模型.我們將RSA和P-RSA算法與其他經(jīng)典算法運(yùn)行在相同的仿真環(huán)境下進(jìn)行模擬實(shí)驗(yàn);基于得到的模擬實(shí)驗(yàn)結(jié)果，對(duì)各個(gè)算法性能進(jìn)行評(píng)價(jià)與分析.

6.1 模擬實(shí)驗(yàn)

我們知道觀測(cè)節(jié)點(diǎn)在移動(dòng)過程中，需要將觀測(cè)到的數(shù)據(jù)上傳到數(shù)據(jù)中心.其移動(dòng)接入請(qǐng)求的位置及其數(shù)量在時(shí)間和空間上動(dòng)態(tài)變化.在實(shí)驗(yàn)中，設(shè)接入請(qǐng)求產(chǎn)生的數(shù)量服從泊松分布,其復(fù)雜度是線性的,返回值為k,平均值為λ.在海洋觀測(cè)中,海量觀測(cè)節(jié)點(diǎn)的接入請(qǐng)求均值也相對(duì)較大,接入請(qǐng)求量的均值λ相對(duì)較大,可能導(dǎo)致e-λ數(shù)值穩(wěn)定性問題,因此本文采用泊松分布的高斯近似.實(shí)驗(yàn)中涉及的參數(shù)如表1所示:

Table 1 The Experimental Parameter Table表1 實(shí)驗(yàn)參數(shù)

基于觀測(cè)節(jié)點(diǎn)接入請(qǐng)求的當(dāng)前與歷史數(shù)據(jù),如觀測(cè)節(jié)點(diǎn)接入請(qǐng)求的快照、利用已有預(yù)測(cè)方法[15]可以獲得移動(dòng)接入請(qǐng)求TTL時(shí)間內(nèi)各時(shí)間槽的軌跡信息以及經(jīng)過某個(gè)AP節(jié)點(diǎn)的概率等.

在本模擬實(shí)驗(yàn)中,假設(shè)接入請(qǐng)求的生存時(shí)間(TTL)的時(shí)長(zhǎng)為3個(gè)時(shí)間槽,分別為t1，t2，t3,如圖2所示.給定區(qū)域當(dāng)前第1個(gè)時(shí)間槽的觀測(cè)接入請(qǐng)求的快照，如圖2(a)所示.基于該區(qū)域當(dāng)前與歷史數(shù)據(jù)獲得的未來t2～t3時(shí)間槽內(nèi)接入請(qǐng)求時(shí)空分布的預(yù)測(cè)結(jié)果,如圖2(b)～(c)所示:

Fig. 2 Spatial-temporal distribution of upload access requests圖2 上傳接入請(qǐng)求的時(shí)空分布

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

Fig. 3 Time series analysis of upload access requests圖3 上傳接入請(qǐng)求數(shù)量的時(shí)間序列穩(wěn)定性分析圖

在模擬實(shí)驗(yàn)中，我們將多性能指標(biāo)泛化為“收益”作為實(shí)驗(yàn)結(jié)果的衡量指標(biāo)，并基于實(shí)驗(yàn)結(jié)果對(duì)P-RSA,RSA與其他經(jīng)典接入調(diào)度算法,如隨機(jī)接入控制Rand算法以及先進(jìn)先出FIFO算法的上傳接入調(diào)度的性能進(jìn)行分析.

基于觀測(cè)接入請(qǐng)求的歷史數(shù)據(jù),我們使用BP神經(jīng)網(wǎng)絡(luò)對(duì)接入請(qǐng)求的數(shù)量進(jìn)行時(shí)間序列分析.接入請(qǐng)求數(shù)量時(shí)間序列自相關(guān)分析,如圖3(a)所示.圖3中柱形表示相關(guān)性,虛線為置信界限.從實(shí)驗(yàn)結(jié)果可以看出，數(shù)據(jù)到后面還有增大的情況,沒有明顯的收斂趨勢(shì).由此可知,自相關(guān)圖有拖尾的情況.接入請(qǐng)求的時(shí)間序列偏自相關(guān)的分析結(jié)果,如圖3(b)所示.數(shù)據(jù)到后面接近于0,有明顯的截尾現(xiàn)象.由此可判斷,此接入請(qǐng)求的時(shí)間序列是穩(wěn)定的.該實(shí)驗(yàn)結(jié)果印證了接入請(qǐng)求在時(shí)間線上的可預(yù)測(cè)性,為本文基于接入請(qǐng)求的移動(dòng)軌跡分析未來收益預(yù)測(cè)分析的P-RSA方法提供有力支撐.

Fig. 4 Current revenue vs the number of upload access requests圖4 當(dāng)前收益vs接入請(qǐng)求數(shù)量

在實(shí)驗(yàn)中我們使用了10個(gè)數(shù)據(jù)集.所有上傳接入請(qǐng)求隨機(jī)分布在AP通信覆蓋區(qū),隨著接入請(qǐng)求數(shù)量的遞增,AP通信負(fù)載從空載、輕載、全載到超載,如圖4～6所示.

Fig. 5 Future revenue vs the number of upload access requests圖5 未來收益vs接入請(qǐng)求數(shù)量

P-RSA算法以最大化從當(dāng)前到截止時(shí)間的整個(gè)時(shí)間段內(nèi)總收益為優(yōu)化目標(biāo),即最大化當(dāng)前與未來收益的總和.而RSA算法以當(dāng)前接入調(diào)度收益最大化為優(yōu)化目標(biāo).隨著上傳接入請(qǐng)求數(shù)量的遞增，P-RSA,RSA與其他調(diào)度算法當(dāng)前收益也發(fā)生變化,如圖4所示.

圖4～圖6的橫坐標(biāo)為上傳接入請(qǐng)求的數(shù)量,即在AP通信覆蓋區(qū)域待調(diào)度的接入請(qǐng)求個(gè)數(shù).隨上傳接入請(qǐng)求的數(shù)量遞增,各接入調(diào)度算法的當(dāng)前收益呈現(xiàn)一個(gè)線性增長(zhǎng),且增長(zhǎng)趨勢(shì)近乎一致.當(dāng)接入請(qǐng)求遞增到300左右時(shí)，這個(gè)線性曲線出現(xiàn)了一個(gè)拐點(diǎn),如圖4所示.

在圖4中,從圖4中拐點(diǎn)開始,各個(gè)算法的當(dāng)前收益值隨著接入請(qǐng)求個(gè)數(shù)增加出現(xiàn)分叉.Rand與FIFO算法的當(dāng)前收益上下波動(dòng)基本平穩(wěn)常數(shù),即AP滿載的當(dāng)前收益的期望值.隨接入請(qǐng)求數(shù)量的遞增,P-RSA與RSA算法的當(dāng)前收益基本呈現(xiàn)一個(gè)增速率遞減的平穩(wěn)增長(zhǎng)趨勢(shì).

Fig. 6 Comparison of the total revenue of each algorithm under different loads within the deadline圖6 截止時(shí)間內(nèi)不同負(fù)載下各算法總收益對(duì)比圖

圖5的橫坐標(biāo)為接入請(qǐng)求數(shù)量,縱坐標(biāo)為各調(diào)度算法在不同接入請(qǐng)求數(shù)量,即不同AP載荷下未來收益的值.當(dāng)接入請(qǐng)求數(shù)由0增加到300的過程中,各算法的未來收益近似為0；而由300遞增到1 000的過程中,各個(gè)算法的未來收益隨接入請(qǐng)求數(shù)量的增加而增大,近似地趨近于以不同斜率線性增長(zhǎng).

在TTL時(shí)間段內(nèi),各個(gè)算法在不同AP負(fù)載條件下的總收益值的實(shí)驗(yàn)結(jié)果,如圖6所示.明顯可以看出,在AP未達(dá)到通信滿載前,各個(gè)算法總收益幾乎相同且未來收益為0；當(dāng)AP過載時(shí),P-RSA的總收益在所有算法最高,接入請(qǐng)求數(shù)量從400遞增到1 000時(shí),其總收益比傳統(tǒng)Rand與FIFO算法總收益高16%～30%.

7 總 結(jié)

針對(duì)大規(guī)模海洋觀測(cè)系統(tǒng)中移動(dòng)接入請(qǐng)求爭(zhēng)用稀缺通信資源問題,本文旨在從優(yōu)化的角度分析,研究解決保證觀測(cè)數(shù)據(jù)延遲容忍且收益最大的上傳接入調(diào)度機(jī)制.首先解決了無線接入請(qǐng)求時(shí)空動(dòng)態(tài)變化的抽象描述與量化問題,考慮其時(shí)空變化的相關(guān)性并通過計(jì)算獲得預(yù)測(cè)結(jié)果;其次,形式化描述了保證觀測(cè)數(shù)據(jù)的延遲容忍前提下收益最大化的優(yōu)化接入調(diào)度問題,并通過定理證明了該問題的難度,是一個(gè)NP難問題;再次,具有最優(yōu)子結(jié)構(gòu)等性質(zhì)在文中得到證實(shí),說明該問題可以使用動(dòng)態(tài)規(guī)劃的方法求解,因此基于動(dòng)態(tài)規(guī)劃思想給出了求解該問題的P-RSA近似算法;最后,通過模擬實(shí)驗(yàn)不但分析了接入請(qǐng)求時(shí)空特征,而且基于不同接入請(qǐng)求數(shù)據(jù)集進(jìn)行了多組實(shí)驗(yàn),并通過實(shí)驗(yàn)結(jié)果的對(duì)比分析驗(yàn)證了P-RSA算法的有效性.