元胞机制下机坪机会网络缓存控制策略

陈维兴，苏景芳，孟美含

(中国民航大学 电子信息与自动化学院，天津 300300)

机坪感知机会网络[1]发展自机会网络[2](opportunistic network，ON).在ON中，信息传输主要靠节点移动产生的相遇机会完成信息的交换,机坪感知机会网络具有静态感知节点分散，动态节点短时聚集的特征，而当相遇机会产生时，同时需要确保信息传输的有效性.节点能量和缓存限制消息传输，当相遇节点缓存空间不足时，节点因无法接收新的数据包或缓存中的数据包因缓存队列过长而导致传输延迟增加，发生拥塞现象，进一步使网络投递率下降.

解决网络拥塞提高投递成功率的方法在机会网络中一般有2种[3]：一种是路由策略关注转发机会以及关键节点选取；一种是缓存管理策略.缓存管理中需考虑合理利用和释放缓存[4-7].缓存管理策略主要是根据全局可用信息进行分类，定义消息优先级，但是并没有考虑节点性能，易造成待传输消息因节点数据拥塞无法传输[5].文献[6]中提出了一种基于接受阈值的拥塞控制机制，该机制使每个时延容忍网络(delay tolerant networks，DTN)节点动态调整到其接受阈值，并相应地调整为其拥塞状态，缺少在消息层面的拥塞控制策略.文献[7]在上述基础上增加基于时空考虑的消息丢弃策略，若消息副本符合时空丢弃策略，但是其仅有一个副本，此时的丢弃则会使该消息消失，造成消息投递率降低.经典的消息副本丢弃策略还有DL(drop last)、DY(drop youngest)[8].这些策略在节点拥塞时，采用队列管理思想按照消息进入节点缓存空间的先后顺序、时间长短等规则选择需要丢弃的消息副本，释放节点的缓存空间来接收新的消息.上述的算法都是基于副本在当前节点上的局部特性来判断，没有考虑消息副本在传输过程中实际存在的情况，尤其是基于相遇机会转发消息的机会网络中，缓存空间中存在时间久的消息并不一定已经被成功转发，欠缺全局性思维.

文中针对机坪网络中的缓存管理问题，研究一种基于元胞演化规则的机坪机会网络缓存控制策略(apron opportunity network cache under cellular evolution rule，ACER).首先建立基于节点拥塞情况的数据通信模型，发现拥塞度较低的节点，使得Prophet算法中拥塞度较低的节点拥有较高的转移概率，增大消息成功传递到目的节点的概率.然后针对拥塞度较高的节点，研究基于元胞自动机的消息副本丢弃策略，进一步降低节点能耗、减少拥塞.

1 基于节点拥塞度的机坪机会路由通信模型

机坪停机位与地面保障车辆具有严格的位置划分与运行规范，并且分布面积较广；在航班入场后，机坪各个保障车辆会出现同时大量传送的数据，引起无线信道数据流量的传输高峰，进而导致节点发生拥塞.由于机坪监控网络异构，包括加油车、清洁车、摆渡车等在内的地面保障车辆以及旅客流等因素使得数据传输端到端时延变长，中继节点需要携带大量数据副本存储较长时间，从而增大了对存储空间和能量的消耗.相比传统的无线自组织网络，基于机会网络的机坪网络传输对节点的缓存容量有着较高的要求.

通过对机坪感知网络的分析可知，在资源有限且受航班流驱动的机坪网络中节点由于短时聚集易出现数据拥塞.对机坪网络拥塞控制的工作目标是监视本地情况并采取适当的措施来管理节点缓存副本.在具有延时的机坪网络传输过程中，如图1所示，主要分为3个步骤进行拥塞控制：对节点缓存的拥塞情况进行判断；根据节点拥塞情况选取拥塞度较小的节点决定路由的传输概率；在相遇节点拥塞度较高时对缓存的副本进行处理，决策需要丢弃的副本对象，以增加总体传输率并降低端到端延迟.

图1 机坪感知网络拥塞度控制算法

2 机坪节点缓存拥塞度判断

机坪中每个节点i与周围所有相邻节点在每个时间间隔T的开始时刻进行交互时，首先进行自身缓存空间使用情况判断.机坪中所有节点缓存中消息副本主要包括节点自身产生的消息和节点移动过程中作为中继节点接收的消息两部分.消息副本MC(message copy)通常根据时间的先后顺序以队列的形式(TMC1,TMC2,…,TMCN)存放于节点缓存中.

定义1令节点i自身产生消息的大小为MTC.当节点产生一个副本时，获取该副本的数据大小情况，然后计算节点历史时间内产生的消息总和MTC：

(1)

式中：m(i)size为节点消息占用的缓存大小；n1为历史时间消息产生总数;Created[m(i)size]为节点历史时间产生一个消息副本的大小.

定义2令节点i接收消息大小为MTR.M-Agent移动过程中作为中继节点成功接收一个副本MC时，获取该副本的缓存空间大小，然后计算节点历史时间内接收的消息总和MTR：

(2)

式中：Received[m(i)size]为节点历史时间内接收一个副本的缓存大小；n2为历史时间内该节点接收并存储的副本总数.因此，节点缓存中所有消息副本的总和为

MTotal=MTC+MTR.

(3)

定义3令节点的缓存拥塞度为Con(i).设置网络中M-Agent节点的缓存容量初始值为buffersize，则节点Con(i)可以通过点缓存中所有消息副本的总和MTotal与初始缓存大小buffersize的比值来表示：

(4)

Con(i)反映了节点缓存空间的使用情况，若Con(i)较高的节点不断与中继节点进行交互，而不考虑此消息副本MC在当前网络的存在情况，则该节点可能接收网络中存在比例较大的副本，导致数据拥塞，此节点无法继续接收网络中存在比例较小的副本，从而使网络投递成功率降低.

3 基于概率路由的数据通信

确定网络中节点Con(i)后，针对Con(i)较小的节点，进行基于概率路由的数据通信.Prophet是基于两个节点历史相遇和转发概率的经典多副本概率路由算法，该算法通过将副本转发给与目的节点传输概率大的中继节点，改善了Epidemic中节点副本转发的盲目性，其节点传输概率为

P(i,j)=P(i,j)old+(1-P(i,j)old)·Pinit.

(5)

但在节点缓存空间有限、时延较大的机坪网络环境中，假设当前某个M-Agent与一个中继节点B相遇并且经Prophet算法计算，该节点与相遇节点将副本转发到目的节点的概率相同，但是当前节点Con(i)大于相遇节点，那么此时相遇的中继节点B将消息传输到目的节点的概率大于当前节点.

因此，将Con(i)作为接触概率值P(i,j)的影响因素之一，对式(5)进行改进，将节点的拥塞度大小以及相遇的2个节点拥塞度的比较考虑在内.

当与M-Agent相遇的中继节点B拥塞度小于

μ，并且Con(i)MeetingNode

P(i,j)=P(i,j)old+(1-P(i,j)old)·

(Pinit+η·Con(i)MNCon(i)MN)，

(6)

式中：Pinit∈[0,1]为初始化常数，在ONE中默认值为0.75，通过仿真表明Pinit=0.7、μ=0.7、η=0.2性能更好；Con(i)MN为相遇中继节点的拥塞度.由于Con(i)≤1，Pinit+η·Con(i)MNCon(i)MN<1，所以传输概率值P(i,j)<1.

因此在机坪上，当M-Agent与下一跳节点相遇时，根据不同范围的Con(i)使用不同的传输概率，根据相遇节点到目的节点的概率决定是否传输消息.消息转发算法的伪代码如下:

Initial:

while(When node M-Agent meets node B)

if(B is the destination node)

Directly Deliver message to B

else if(Con(i)≤0.7;Con(i)MeetingNode

calculate theP(M-Agent,des),P(B,des)

CompareP(M-Agent,des),P(B,des)

if (P(M-Agent,des)

Forward message to Node B

if (P(M-Agent,des)>P(B,des))

Waiting for the next node

end if

end while

两个节点相遇之后不满足上述拥塞度的判定条件时，则依然采用Prophet原本的转发概率，采用式(5)进行转发概率的计算.

4 基于元胞自动机的消息副本丢弃策略

计算节点转发消息到目的节点概率时加入了节点拥塞度对概率值的影响.当节点拥塞度大于0.7时，即使相遇节点的传输概率值较大，缓存空间仍然影响节点接收新的消息副本.此时节点需要对缓存内的消息副本进行处理.根据对机坪网络拥塞问题的分析引入元胞自动机模型，局部范围考虑消息副本的存在情况，设计合理的消息丢弃策略.

在经典CA模型基础上，结合学习自动机(learning automatic，LA)模型，文献[10]提出元胞学习自动机(cellular learning automata，CLA)，LA的加入可以让元胞节点从有限的动作集中选择一个自动执行.机坪环境中将移动智能体M-Agent架设于机坪保障车辆作为机会传输的相遇机会，文中将通过M-Agent作为LA执行动作来进行建模.为了避免规则网格在实际情况的局限性，进一步发展了更加通用的模型不规则元胞自动机(irregular cellular learning automata,ICLA)，其更加适用于WSN网络、图论等相关领域[11].

根据机坪环境不规则网格划分的思想，将网格对应为元胞空间，因此可以利用ICLA模型设置相应的演化规则对缓存内的消息副本进行丢弃策略的设计.机坪网络与ICLA模型的对应关系图见图2.

图2 机坪网络与元胞自动机模型的对比

由图2可见，机坪网络的局部缓存处理策略可根据ICLA模型执行.机坪传感器节点映射为元胞，节点、可通信的周围邻居节点对应为元胞空间；机坪不规则网格子域对应于ICLA不规则性；机坪上移动节点以及各节点之间无线连接的建立与断开，可以看作元胞邻居的动态变化；传感器节点的无线通信范围相当于元胞半径，而缓存策略的处理过程就可以看作元胞演化规则的设计.M-Agent对消息缓存的处理对应于LA的动作执行.通过节点自身缓存与邻居节点的副本传输情况，决定当前节点对每个副本缓存的保留或者丢弃.因此，采用ICLA模型在机坪上自动执行缓存的丢弃与保留具有可行性.

因此在机坪网络环境中设计了基于不规则元胞自动机的消息副本丢弃策略.

图3所示为机坪上配备LA的ICLA模型，在机坪不连通子域的元胞空间内配备LA，其中，α={α1,α2,…,αr}表示LA的动作集，β={β1,β2,…,βs}表示强化信号的输入集.

图3 基于ICLA的机坪网络模型

基于ICLA的机坪网络模型操作过程如下：

1)每个元胞空间的状态由LA的动作概率向量决定，初始状态的设定根据机坪上消息副本丢弃历史经验设定.

2)根据节点自身缓存副本和即将接收的缓存消息副本设定CA的演化规则，从而确定元胞空间内的强化信号β.

3)每个配备LA的节点根据环境实时反馈的强化信号对概率向量进行更新.

ACER策略计算节点消息副本并进行拥塞度的判断，当Con(i)>0.7时，节点基于ICLA模型，检测节点自身缓存的副本在邻居节点的持有情况以及新到副本在邻居节点的持有情况，若消息副本在邻居节点的存在数量大于某个值a，则进行消息副本的丢弃或者拒绝接收新到副本，从而释放节点缓存空间接收网络中存在比例小的消息副本.

机坪网络中，节点移动性使得网络的传输建立或者断开相当于ICLA中元胞的动态变化.通过配备LA的M-Agent节点执行动作e1和e2，分别表示对节点内每个缓存副本的保留或者丢弃，对应动作概率用Preceive和Pdiscard表示，节点进行消息交互的开始保留与丢弃的动作概率相等，分别为0.5.设置时间间隔为T，每经过T后更新一次节点状态，节点Ni在T开始与相邻节点进行交互时，需要进行以下3步操作：

1)获取节点中每个副本在周围邻居节点的持有情况；

2)给出节点Ni的LA命令信号τi(n)；

3)对每个副本的动作产生相应的命令信号，如下式所示：

(7)

式中：τi(r)为节点在第r轮时对相同副本的命令信号取值；sumi(r)为第r轮节点i的邻居数目；ej(r)为节点j在第r轮保留该副本的动作.

根据τi(r)取值的不同，对副本丢弃概率Pdiscard按照式(8)或(9)进行更新：

Pdiscard(r+1)=Pdiscard(r)+θ(r)·(1-Pdiscard(r))，

(8)

Pdiscard(r+1)=Pdiscard(r)·(1-φ(r))，

(9)

式中：θ(r)与φ(r)表示LA的激励和惩罚参数，0<θ(r)<1，0<φ(r)<1.

相应的节点对副本的保留概率为

Preceive(r+1)=1-Pdiscard(r+1).

(10)

(11)

(12)

在每一轮r开始时，都按照上述过程对节点上每个副本的丢弃概率进行更新.由于机坪节点的移动，以及前一轮的拥塞度检测与节点缓存的处理，持有相同副本的邻居节点也会随之发生变化.如果当前持有相同副本的邻居节点数量比前一轮少，则认为该副本在当前局部网络环境中对网络的拥塞度降低.由于丢弃的是局部范围内存在较多的相同副本，因此，会增大接收其他重要副本的机会，从而提高投递的成功率.其算法伪代码如下：

Input:List of MC in the cache of node A,the current neighbor set of node A

Output:Drop probability of each message.

for(each message m of node A)

for(Every neighbor node B){

if(Node B buffers message m)

Pdiscard(r+1)=Pdiscarde(r)+θ(r)·

(1-Pdiscard(r));

else

Pdiscard(r+1)=Pdiscard(r)·(1-φ(r)));

end if

end for

end for

图4给出了ACER算法的流程图.由图4可见，ACER算法步骤如下：

图4 ACER算法流程图

1)在初始化阶段，节点Ni通过和周围所有邻居节点Nj的交互，获知节点Ni和Nj的每个副本在周围邻居节点上的持有情况.

2)为了降低节点能耗，节点接收消息前，根据节点缓存内副本量与缓存的比值计算拥塞率.

3)当Con(i)>0.7时，则首先检测Nj的每个副本在周围邻居节点上的持有情况，选择需要丢弃的副本，否则检测新到节点Ni副本在邻居节点的持有情况.

4)依次检测Nj自身需要丢弃的副本在邻居节点的持有情况，若m节点在邻居节点的持有数量大于a(a>3)，则丢弃该副本，否则保留该消息副本.

5)最后选择下一时刻需要接受的副本在周围邻居节点的持有情况，选择接受或者拒绝接受.在每轮丢弃和接收之后，更新节点拥塞度的值，进行新一轮的检测.

5 仿真验证

使用ONE仿真平台进行试验验证，其中网络性能参数包括信息投递率、网络开销以及平均时延.采用天津滨海国际机场地图进行试验，图5为该机场卫星图.

图5 天津滨海机场卫星图

由图5可见，近机位包括T1和T2航站楼，远机位位于跑道左侧，其总面积是7.4万m2，跑道长3 600 m.利用OpenStreetMap导出机场地图，如图6所示.对近机位和远机位进行区域划分，其中蓝色线条代表M-Agent运动轨迹，近机位区域内节点采用ClusterMovement移动模型，不连通子域间则采用MapRouteMovement移动模型.

图6 天津机场OSM地图

选取基于改进的Prophet路由算法进行仿真，通过仿真可知参数取Pinit=0.7时性能较好.仿真范围根据机坪情况设置为3 600 m×4 500 m，相同配置文件下，分别选取基于缓存时间长短的DL与基于缓存节点存活时间的DY两种经典缓存管理算法进行比较.为了体现移动节点M-Agent交互过程中的缓存控制问题，设置固定的簇内节点数量50个，缓存30 MB，根据M-Agent节点的变化进行仿真，其中参数设置如表1所示.

表1 仿真环境参数配置

5.1 不同节点数量下算法性能分析

首先先将M-Agent数量的变化(从10到80)进行仿真，其他参数见表1.图7-9分别显示了不同M-Agent节点数量下的消息投递率、网络开销和消息平均时延.

图7 不同节点数量的消息投递率

从图7可见，3种缓存控制策略的消息传递率随着节点数目的增加而提高.随着节点数量增加，M-Agent节点移动过程中的相遇机会变大、消息副本量增多，使得消息与目的节点相遇的机会增大，因而在一定程度上增大了消息投递率.但ACER算法的投递率始终保持最高，因为该算法改善了DL、DY在缓存处理时的随机性，通过对邻居节点副本的持有情况对缓存进行控制，降低了节点缓存内存在时间久但未被成功传递消息副本的丢失率.与基于缓存时间长短和节点存活时间的DL、DY相比，ACER算法投递率提高约91%和97%.

从图8可见，DL与DY算法的网络开销较大.因为随着节点数量的增加，节点之间交互次数增加，消息副本的过多复制导致网络开销较大.而ACER算法在消息传递过程中，通过节点拥塞度改进了消息传输概率，避免了消息转发的盲目性，降低了消息传输至目的节点中的交互次数，因而相比DL与DY算法，ACER算法在网络开销方面分别降低约69%和70%.

图8 不同节点数量的网络开销

由图9可见，消息平均时延整体呈下降趋势.随着节点数量的增加，节点的相遇次数及副本量增加，因而消息从源节点到目的节点的时延降低.而ACER算法是下降幅度最大的，当节点数量小于70时ACER延时较大，但数量达到75之后，其消息平均时延低于DL与DY.这是因为文中设置的仿真场景为3 600 m×4 500 m，在仿真环境较大时，节点数量少使得中继转发节点较少，节点携带消息副本时间较长，故延迟较大；当节点数量持续增大时，节点无需携带消息时间过长就传输至下一跳节点，并且通过对缓存的设计增大了消息的传输概率.

图9 不同节点数量的消息平均传输时延

5.2 不同缓存空间下算法性能分析

图10-12为基于不同缓存空间的对比结果.

图10 不同缓存空间的消息投递率

从图10可见，消息投递率随着缓存空间的增大而呈现增长趋势.这是因为缓存空间的增大将增加节点携带副本的数量，使消息副本被传递到目标节点的机会变大，从而使投递率有所提高.由于ACER算法处理缓存时考虑了网络中的副本情况，使网络中副本数存在较少的消息更大概率传输到目的节点，因此投递率最高.相比DL与DY，ACER投递率分别提高约42%和39%.

从图11可见，随着缓存空间的增加网络开销呈现下降趋势.缓存空间的增大使得网络中增加的缓存副本有了更大的存储空间，节点在仿真环境较大的场景中成功投递的消息数增加，网络开销降低.ACER对缓存的处理更加增大了缓存的利用空间，因此相比DY和DL，其网络开销分别降低约8%和30%.

图11 不同缓存空间的网络开销

由图12可见，随着缓存的增加，消息平均时延呈现增长趋势.这是因为随着缓存空间的增大节点接收的副本数增加，在仿真面较大的场景中，消息传输过程的节点交互转发次数增加，从而增大了目标节点的消息平均时延.

图12 不同缓存空间的平均传输时延

由以上仿真结果可知，在M-Agent不同数量和缓存下，ACER无论是在投递率、网络开销还是消息平均时延方面都有所改善.

6 结 论

针对拥塞控制具有单一性及局限性的研究现状，以及机会网络中多个副本造成的网络拥塞的问题，文中研究了一种基于元胞演化规则的机坪缓存控制策略.根据机坪实际环境设置ONE仿真环境，与传统的基于缓存时间长短和节点存活时间的缓存管理策略DL、DY算法相比，新策略在消息投递率上最高可提高97%、同时网络开销最多可降低70%，通信时延也有一定程度的降低.在此基础上，未来将进一步研究智慧机坪网络全局最优化.