基于接入请求时空分布的延迟容忍上传接入控制方法

陈 丽 邓 琨 蒋 涛 乐光学 李攀攀 杨 俊 徐旭宝

(嘉兴学院数理与信息工程学院 浙江嘉兴 314001)

海洋观测数据蕴含着巨大的价值,为人类深入地认知、管理和利用海洋提供了前所未有的丰富信息[1].负责收集海洋信息的观测节点一般配备一种或多种传感器收集观测数据,并且具有上传数据的无线通信能力.一般按是否移动将观测节点分为2类：1)随机部署的固定观测节点如浮标、潜标等;2)机载、艇载或船载各种传感器的无人艇[2]、无人机、调查监测船甚至渔船、货船等移动观测节点.与固定观测节点相比,移动观测节点的计算和存储等能力一般都较强,能量不受限制而且观测区域也不受位置局限.在人类对海洋开发需求的不断增长以及移动互联网等技术的快速发展的共同驱动下,高计算和存储能力的移动观测节点呈爆发式增长.海洋观测数据的获取是海洋环境保护、防灾减灾、资源开发以及科学研究等[3-4]的依托与保障.尽管目前已有大量相关研究,但主要集中在固定观测台以及随机布撒的固定观测节点的研究,如无线组网、端到端以及端到汇聚节点传输调度、数据聚集等.但是现有技术却很难适应于观测节点快速移动的数据收集的需要.移动接入上传观测数据面临许多亟待解决的新问题与挑战.

在海洋观测过程中,机载、艇载或船载移动观测节点连续地收集并存储所观测的数据.在经过无线接入点(access point, AP)的通信覆盖区域时,这些移动观测节点才有机会接入Internet上传数据.然而,移动观测节点的速度一般都比较快,行经AP通信覆盖区域的时间会比较短,这就限制了可能接入Internet的时长.而且在海洋观测系统中AP的部署一般都较为稀疏,那么相对于移动观测节点以及所需上传观测数据的数量,其通信资源成为竞争激烈的稀缺资源.移动接入请求对AP通信资源的争用,使得移动接入调度问题成为提升海洋观测信息获取效率的重要研究内容.

现有接入调度机制通常将网络吞吐量、数据传输的实时性等作为研究目标[5],为简化研究将多性能指标泛化为“收益”.据网上公开的文献调研发现,现有移动接入调度机制在处理没被调度的接入请求时,其收益被忽略或作为0来处理.即当接入请求不被调度时,则没有收益.然而,考虑到现实应用各观测节点的移动轨迹不同,显而易见在截止时间内是否途径AP以及被调度可能性也存在很大差异.如有些接入请求被调度是大概率事件;而有些被调度的概率则非常小.

本文研究保证观测数据延迟容忍[6-8]前提下的时空动态移动接入请求的最优化调度方法.在实际海洋观测系统中,延迟容忍限制内(如截止时间)获得的观测数据才具有实际应用价值.

本文的主要贡献有4个方面:

1) 对移动接入请求的动态特征通过构建时空数据模型(“流”请求详见定义1)进行描述;

2) 对截止时间内各移动接入请求被调度的随机性进行分析,并通过量化其“未来收益”并引入到目标函数;

3) 在观测数据截止时间约束的条件下,提出基于接入请求时空特征量化分析的收益最大化的移动接入控制方法;

4) 应用不同移动接入请求数据集的实验结果表明,提出的移动接入控制算法可以有效提升其性能.

1 相关工作

无线通信资源传输调度是海洋观测系统的一个重要研究内容.被调度对象一般为AP的信道或时隙等,并且通常以网络吞吐量、数据传输的实时性或公平等指标作为调度目标,如文献[6-9]分别基于传输延迟[6]、公平性[7]以及截止时间[8-9]作为指标来研究提高网络通信性能的调度方法.综合已有文献可以看出,不同应用其需求也各不相同,从而对各个性能指标的偏好程度及侧重点也各不相同.本文将多个主要性能指标泛化为“收益”,将其作为衡量性能优劣的指标,其计算公式详见3.2节的描述.

在无线传感网中,观测节点被随机布撒在观测区域,节点间通过自组织方式进行组网.Ramanathan等人[9-10]采用集中启发式方法进行传输调度;Sen等人[11]以最大化网络吞吐量为目标优化单个时间槽内最大传输集,并以令牌深度优先搜索方法实现集中的启发式广播传输调度;而孙利民等人[12]采用分布式方法基于TDMA进行传输调度以提高网络通信性能.

保证观测数据的延迟容忍的有效接入调度机制是一个非常关键的研究问题.文献[13-14]归纳了时延受限的移动式数据收集的各类方法的特点,分析了这些方法的优缺点和适用范围,总结了存在的主要问题.Lin等人[15]在TRITON项目中,探索使用基于WiMAX技术进行具有延迟容忍网络功能的超视距移动观测节点间的通信,并且比较分析了不同路由方案的性能.

综上所述,现有研究在观测节点位置不发生变化的场景中的网络吞吐量、实时性或公平性等某个指标上表现出良好的性能.但应用于观测节点快速移动的数据上传的应用场景时,无法满足性能需求.

2 系统模型与假设

本节我们将简要介绍系统的模型和相关假设.在海洋观测系统中,我们假设无线接入节点AP之间相互连接并有线接入Internet,可以为其通信范围内的移动观测节点提供无线Internet的接入.在其通信覆盖区域的观测节点可通过AP接入Internet进行数据上传,而在其他区域内无法接入.

众所周知，GPS导航系统越来越受欢迎,并且越来越多的人依赖于它.现在大部分移动观测节点都安装了基于GPS的导航系统.假设移动观测节点都配置了GPS与无线通信模块,其接入请求以及自身的移动轨迹信息往往都是短文本,适合长距离通信;而其采集到的观测数据与之相比就要大得多,更适合传输速率快、通信质量高的无线局域网进行上传,如WiFi连接方式.假设移动观测节点的通信半径及传输速率都相同,并且周期性地通过长距离通信方式向AP报告当前的状态,如位置及轨迹信息等.

本文观察发现海洋观测节点的无线接入请求的产生、存续以及终结会随时空动态变化,并对其动态特征进行量化分析,模型化为“流”请求.基于“流”模型的移动接入调度模型如图1所示.该系统模型简要展示了其调度过程的4个步骤：

① 获取当前待调度移动接入请求位置、轨迹等信息，并输入系统;

② 基于“流”请求模型对移动接入请求进行量化处理;

③ 基于本文提出的移动接入优化调度方法P-RSA进行计算;

④ 基于计算结果对移动观测节点的接入请求实施调度操作.

Fig. 1 The mobile access scheduling system model based on ‘Flow’ 图1 基于“流”请求的移动接入调度系统模型

3 问题的形式化

本节我们将上传接入请求未来轨迹信息对当前调度性能影响，通过构建抽象模型进行量化分析并引入到移动接入调度的优化模型.

我们主要对保证观测数据延迟容忍前提下总收益最大化的接入控制问题进行形式化描述.首先,对相关定义及符号进行描述;然后,讨论如何基于轨迹信息构建描述移动接入请求动态特征的抽象模型;最后,对时空动态变化的无线通信请求的接入控制问题进行描述.

3.1 相关定义及符号

在海洋观测的应用场景中,观测节点在移动过程中找机会将收集到的观测数据上传到数据中心.当穿过某个AP的无线通信覆盖区域时,通过AP的调度,有机会接入Internet上传观测数据.

相对于观测节点,本文更关注其移动接入请求.随着观测节点的快速移动，其接入请求的空间位置在不断变化.在观测数据延迟容忍时间内,若观测节点在移动过程中,途径多个AP的通信覆盖区域,那么该节点的接入请求就有多次被调度的机会.

本文构建描述移动接入请求时空动态特征的抽象模型,即流请求,详见定义1.流请求是关于AP的一个随机时间序列.

定义1.流请求.在观测数据的生存时间内(time to live, TTL),设移动观测节点ni途径k个AP的通信覆盖区域ai1ai2…ai k,若k≥1,将其上传接入请求用AP的时间序列表示,并称fi=(ai1,pi1),(ai2,pi2),…,(ai j,pi j),…,(ai k,pi k)为流请求,其中ni∈N,ai j∈A,集合A和N分别为AP节点集以及移动观测节点集,pi j为节点ni经过AP节点ai j的概率.

3.2 问题的形式化描述

本节从优化的角度分析,在接入请求TTL时间内如何进行控制接入,才能够使得有限信道资源的收益最大化.问题的形式化描述,详见定义2和定义3.

定义2.AP接入控制优化问题(access requests scheduling by AP, RSA).给定AP信道容量为V、其通信范围内带生存时间TTL的接入请求集合R.求使得待调度接入请求当前收益总和最大化的优化调度,其目标函数：

(1)

(2)

由于评价接入请求调度各性能属性的量纲不同(如吞吐量、延迟等),对原始性能属性值进行归一化处理,其转换为界于某一特定范围的数据,以消除量纲和数量级的影响.

设xi表示AP对接入请求ri的控制决策,xi∈{0,1},ri∈R.当xi=1时,表示接入请求ri被AP调度，可以接入Internet上传数据;当xi=0时,表示ri被AP拒绝,不可以接入Internet.那么,RSA问题可以归结为寻找一个满足上述约束方程,并且使得目标函数达到最大值的解向量X=(x1,x2,…,xn).

在现实中,随着观测节点的快速移动其位置在动态变化,从而途经AP通信覆盖的时间也存在很大的不确定性.通过已有基于观测节点的GPS、当前速度以及加速度等信息进行轨迹预测研究方法,可以获得其轨迹相关信息，进而可以预测各个接入请求未来被AP调度的概率.

定义3.AP基于预测轨迹的接入控制优化问题(access requests scheduling by AP based on predicted trajectory, P-RSA).给定AP信道容量为V、其通信范围内带生存时间TTL的接入请求集合R.基于流请求模型(详见定义1)fi=(ai1,pi1),(ai2,pi2),…,(ai j,pi j),…,求使得在TTL时间内待调度接入请求集总收益最大化的优化调度,其目标函数：

(3)

其中，xi表示AP对接入请求fi的控制决策,xi∈{0,1},fi∈R.

当xi=1时,表示当前AP节点接收接入请求fi,其收益为xi×wi;

当xi=0时,表示当前AP节点拒绝该请求,其收益的计算为

(4)

其中,α为接入请求fi在其TTL时间内被调度的影响因子,表示时间延迟对收益wi带来增益(若α>1)或折扣(若α<1).

与RSA问题类似,P-RSA问题归结为寻找一个满足上述约束方程,并使目标函数值(式(3))达到最大的解向量X.

4 问题分析

本节首先对RSA与P-RSA问题的难度进行分析，定理证明过程如定理1所示.

定理1.RSA与P-RSA这2个问题都是NP-难问题.

同理可证,P-RSA问题的实例也可归约为一个0-1背包问题,所以该问题也是NP-难的.综上所述,定理1得证.

证毕.

定理1的证明说明RSA和P-RSA这2个问题的难度都是NP的,因此无法在多项式时间内求得最优解.本文拟基于动态规划思想给出求解该问题的近似算法,下面将通过定理2的证明,验证这2个问题具有最优子结构.

定理2.RSA和P-RSA问题都具有最优子结构.

证明. 假设(z1,z2,…,zk)是问题fk(weight)的最优解,那么:

1) 对于任意1≤j≤k,有zj=1,则有(z1,z2,…,zj-1,zj+1,…,zk)是问题fk-1(weight-w[j])+value[j]的最优解;

2) 对于任意1≤j≤k,有zj=0,则有(z1,z2,…,zj-1,zj+1,…,zk)是问题fk-1(weight)的最优解.

同理可证P-RSA问题也具有最优子结构.因此,定理2得证.

证毕.

定理2已经证明了RSA问题具有最优子结构,下面递归定义RSA问题的最优解的值.每个观测节点只有一个接入请求,可以接受该接入请求也可以拒绝.用子问题定义状态：即f[n][v]表示n个请求接入一个信道资源为V的AP可以获得的最大收益,则其状态转移方程为

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

(5)

其中,f[i][j]表示前i个请求接入可用信道资源为j的收益总和,f[i][0]=f[0][j]=0.其中第i个接入请求所占信道资源为c[i],收益为w[i];若只考虑第i个接入请求的策略(接入或不接入),那么就可以转化为一个剩余n-1个接入请求的接入调度问题.如果拒绝第i个请求接入,即x[i]=0,那么问题转化为n-1个接入请求接入容量为V的AP的问题,价值为f[n-1][v];若第i个请求被AP接受而接入,即x[i]=1,那么问题就转化为其余i-1个接入请求接入剩下的信道资源为v-c[i]的AP中,此时能获得的最大价值就是f[n-1][v-c[i]]再加上通过放入第i个接入请求获得的收益w[i].

5 P-RSA算法

NP难问题RSA与P-RSA无法在多项式时间内得到精确优化解,并且通过定理2的证明验证了这2个问题具有最优子结构等性质.本节基于动态规划思想给出求解RSA和P-RSA优化问题的近似算法.自下而上进行计算,最后由计算结果构造一个最优解.

本节在算法1中给出了求解接入控制优化问题的RSA近似算法,如算法1所示.算法1的输出结果为接入请求延迟容忍时间内收益最大的解向量X.

算法1.RSA算法.

输入：n个请求接入、AP可用信道资源为V、每个接入请求需要占用的信道资源为C={c[1],c[2],…,c[n]}，其收益为W={w[1],w[2],…,w[n]}；

输出：X=(x[1],x[2],…,x[n])*最优接入请求集合,即使目标函数达到最大的解向量*

① for (i=1;i≤n;i=i+1)*第1个阶段*

②f[i][0]=0;*f[i][j]表示前i个请求接入AP的收益总和*

③x[i]=0;*x[i]∈{0,1}表示AP对接入请求r[i]的控制决策.x[i]=1表示r[i]被AP调度;而x[i]=0表示不被调度*

④ end for

⑤ for (intj=0;j≤V;j++)*其他n-1个阶段*

⑥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基于预测轨迹的接入控制优化问题的P-RSA近似算法,如算法2所示.在给定通信资源V、接入请求集合R以及流请求信息ri=(ai1,pi1),(ai2,pi2),…,(ai j,pi j),…条件下,求使得在TTL时间内待调度接入请求集总收益最大化的解向量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),…*观测节点ni经过AP节点ai j的概率为pi j的流请求ri∈R*

输出：X=(x[1],x[2],…,x[n])*最优接入请求集合,即使目标函数达到最大的解向量*

① for (i=1;i≤n;i=i+1)*第1个阶段*

②f[i][0]=0;*f[i][j]表示前i个请求接入AP的收益总和*

③x[i]=0;*x[i]∈{0,1}表示AP对接入请求r[i]的控制决策.x[i]=1表示r[i]被AP调度;而x[i]=0表示不被调度*

④ 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节点通信覆盖范围内,若待调度移动接入请求的未来轨迹信息已知(或通过预测可以获得),即观测节点在其接入请求的TTL时间内将经过的AP节点的序列.本文提出基于预测轨迹的时空穿越控制方法P-RSA.首先,构建移动接入请求轨迹的预测模型.移动接入请求ri的轨迹表示为,其中为ri轨迹经过的AP节点,为经过的概率.观测节点的轨迹信息可以通过AIS、GPS等记录的位置、速度、加速度及导航等信息的计算来进行预测获得[16],P-RSA算法的如算法2所示.

当然,若所有移动接入请求的未来轨迹信息都未知且无法获得,则退化为第1种情况,基于RSA算法来进行求解.

6 模拟实验与性能分析

本文采用MATLAB搭建仿真环境,使用LINGO求解优化模型.我们将RSA和P-RSA算法与其他经典算法运行在相同的仿真环境下进行模拟实验;基于得到的模拟实验结果，对各个算法性能进行评价与分析.

6.1 模拟实验

我们知道观测节点在移动过程中，需要将观测到的数据上传到数据中心.其移动接入请求的位置及其数量在时间和空间上动态变化.在实验中，设接入请求产生的数量服从泊松分布,其复杂度是线性的,返回值为k,平均值为λ.在海洋观测中,海量观测节点的接入请求均值也相对较大,接入请求量的均值λ相对较大,可能导致e-λ数值稳定性问题,因此本文采用泊松分布的高斯近似.实验中涉及的参数如表1所示:

Table 1 The Experimental Parameter Table表1 实验参数

基于观测节点接入请求的当前与历史数据,如观测节点接入请求的快照、利用已有预测方法[15]可以获得移动接入请求TTL时间内各时间槽的轨迹信息以及经过某个AP节点的概率等.

在本模拟实验中,假设接入请求的生存时间(TTL)的时长为3个时间槽,分别为t1，t2，t3,如图2所示.给定区域当前第1个时间槽的观测接入请求的快照，如图2(a)所示.基于该区域当前与历史数据获得的未来t2～t3时间槽内接入请求时空分布的预测结果,如图2(b)～(c)所示:

Fig. 2 Spatial-temporal distribution of upload access requests图2 上传接入请求的时空分布

6.2 实验结果与分析

Fig. 3 Time series analysis of upload access requests图3 上传接入请求数量的时间序列稳定性分析图

在模拟实验中，我们将多性能指标泛化为“收益”作为实验结果的衡量指标，并基于实验结果对P-RSA,RSA与其他经典接入调度算法,如随机接入控制Rand算法以及先进先出FIFO算法的上传接入调度的性能进行分析.

基于观测接入请求的历史数据,我们使用BP神经网络对接入请求的数量进行时间序列分析.接入请求数量时间序列自相关分析,如图3(a)所示.图3中柱形表示相关性,虚线为置信界限.从实验结果可以看出，数据到后面还有增大的情况,没有明显的收敛趋势.由此可知,自相关图有拖尾的情况.接入请求的时间序列偏自相关的分析结果,如图3(b)所示.数据到后面接近于0,有明显的截尾现象.由此可判断,此接入请求的时间序列是稳定的.该实验结果印证了接入请求在时间线上的可预测性,为本文基于接入请求的移动轨迹分析未来收益预测分析的P-RSA方法提供有力支撑.

Fig. 4 Current revenue vs the number of upload access requests图4 当前收益vs接入请求数量

在实验中我们使用了10个数据集.所有上传接入请求随机分布在AP通信覆盖区,随着接入请求数量的递增,AP通信负载从空载、轻载、全载到超载,如图4～6所示.

Fig. 5 Future revenue vs the number of upload access requests图5 未来收益vs接入请求数量

P-RSA算法以最大化从当前到截止时间的整个时间段内总收益为优化目标,即最大化当前与未来收益的总和.而RSA算法以当前接入调度收益最大化为优化目标.随着上传接入请求数量的递增，P-RSA,RSA与其他调度算法当前收益也发生变化,如图4所示.

图4～图6的横坐标为上传接入请求的数量,即在AP通信覆盖区域待调度的接入请求个数.随上传接入请求的数量递增,各接入调度算法的当前收益呈现一个线性增长,且增长趋势近乎一致.当接入请求递增到300左右时，这个线性曲线出现了一个拐点,如图4所示.

在图4中,从图4中拐点开始,各个算法的当前收益值随着接入请求个数增加出现分叉.Rand与FIFO算法的当前收益上下波动基本平稳常数,即AP满载的当前收益的期望值.随接入请求数量的递增,P-RSA与RSA算法的当前收益基本呈现一个增速率递减的平稳增长趋势.

Fig. 6 Comparison of the total revenue of each algorithm under different loads within the deadline图6 截止时间内不同负载下各算法总收益对比图

图5的横坐标为接入请求数量,纵坐标为各调度算法在不同接入请求数量,即不同AP载荷下未来收益的值.当接入请求数由0增加到300的过程中,各算法的未来收益近似为0；而由300递增到1 000的过程中,各个算法的未来收益随接入请求数量的增加而增大,近似地趋近于以不同斜率线性增长.

在TTL时间段内,各个算法在不同AP负载条件下的总收益值的实验结果,如图6所示.明显可以看出,在AP未达到通信满载前,各个算法总收益几乎相同且未来收益为0；当AP过载时,P-RSA的总收益在所有算法最高,接入请求数量从400递增到1 000时,其总收益比传统Rand与FIFO算法总收益高16%～30%.

7 总 结

针对大规模海洋观测系统中移动接入请求争用稀缺通信资源问题,本文旨在从优化的角度分析,研究解决保证观测数据延迟容忍且收益最大的上传接入调度机制.首先解决了无线接入请求时空动态变化的抽象描述与量化问题,考虑其时空变化的相关性并通过计算获得预测结果;其次,形式化描述了保证观测数据的延迟容忍前提下收益最大化的优化接入调度问题,并通过定理证明了该问题的难度,是一个NP难问题;再次,具有最优子结构等性质在文中得到证实,说明该问题可以使用动态规划的方法求解,因此基于动态规划思想给出了求解该问题的P-RSA近似算法;最后,通过模拟实验不但分析了接入请求时空特征,而且基于不同接入请求数据集进行了多组实验,并通过实验结果的对比分析验证了P-RSA算法的有效性.