军事信息系统中基于无线Mesh网络的内容分发方法

， ，

(中国电子科学研究院，北京 100041)

0 引 言

无线Mesh网络(Wireless Mesh Network, WMN)最初是美军为满足军事信息系统中宽带数据传输以及支持端到端IP、语音和视频信息、不采用GPS实现精确定位要求而建立的[1]。近年来，因其具有易部署、高带宽、结构灵活和抗毁性强等特点而成为国内外研究热点，特别是在军事领域，其特性能够满足高带宽、高机动性、超视距的保障能力要求。因此，如何将军事信息系统的通信要求与无线Mesh网络的特点进行结合，寻求最优的应用配置，是值得深入研究的问题。

无线Mesh网络是一种多跳的分布式网络，如图1所示，典型的无线Mesh网络通常包含两类节点: Mesh路由器(Mesh Router, MR)和Mesh客户端(Mesh Client, MC)。在大部分的WMN应用中，Mesh路由器因其固定性而构成网络骨干[2]。将WMN技术应用于军事信息系统，可以解决极端环境下的无线组网问题。然而在军事信息系统中，尤其是在战场环境下，往往存在无线网络资源受限问题，进而导致使用WMN进行信息分发将面临网络瓶颈问题[3]。在无线Mesh网络中，Mesh路由器相对于Mesh客户端具有相对固定性和大容量的特性，因此可以引入内容分发(Content Delivery)技术[4]，将Mesh路由器作为镜像服务器，以提升无线网络资源受限条件下军事信息系统中信息分发的服务质量。

图1 无线Mesh网络架构

通过将内容分发技术引入到无线Mesh网络中，内容对象的镜像被分发至靠近相关MC的MR中，MC发出的数据信息请求可以被就近服务。从MC发出的数据信息请求被重定向至最近的拥有相应镜像的MR，MR将所需的数据信息通过响应消息回传给MC。由此可见，内容镜像的分发直接决定了无线Mesh网络的服务质量。以往对于内容分发技术的研究聚焦于如何通过镜像分发机制降低网络中的数据获取延迟，设计的方法更适用于便于集中控制和计算的有线网络环境，未考虑无线Mesh网络的分布式特点，如此建立的问题模型并不能真正反映无线Mesh网络中内容分发的实际情况。因此对于无线Mesh网络中的内容分发方法的研究，对于构建基于无线Mesh网络的军事信息系统具有重要意义。

本文研究了军事信息系统中基于无线Mesh网络的内容分发方法，旨在提升无线网络资源受限条件下军事信息系统中信息分发的服务质量。首先，基于无线Mesh网络，设计了立体化的军事情报信息中心-战术通信卫星-小型分布式地面站-作战单元网络结构模型。在该网络模型的基础上，我们对军事信息系统中的基于无线Mesh网络的内容分发问题进行了形式化地描述。针对该问题，本文设计了分布式四阶段启发式算法。该方法根据军事信息系统中各类型内容被订阅的热度，采用分布式的算法，将军事情报信息中心的内容镜像分发至相应的分布式地面站，以提高基于无线Mesh网络的军事信息系统的服务质量。

1 相关研究

无线Mesh网络最初是美军为满足军事通信中无线带宽数据传输等要求建立的，因其组网快速灵活、抗毁性强等特点，在军事信息系统组网中得到广泛的应用。文献[5]提出了基于802.16 d的无线Mesh网络的集团军战役指挥所通信系统。系统具有保密、易于开设使用和建网费用低廉等特点。文献[6]提出了一种海战场环境下基于Mesh结构的无线网络应用方案，满足舰艇编队通信网络高速率、大容量、非视距传输的要求，对无线Mesh网络在军事通信领域的深入研究具有一定的参考价值。

然而，无论实在军事应用领域，还是学术领域，将内容分发技术引入到无线Mesh网络用于解决网络瓶颈的研究都很少。就我们的了解而言，对无线Mesh网络中内容分发技术的相关研究，主要有以下文献。在文献[7]中，作者证明了最优的内容镜像分发策略是每个内容对象的副本数量正比于pr0.667，其中pr是内容对象的热度。文献[8]中，作者对无线覆盖网络中的内容分发模型做了较为完备的理论分析，但是并没有提出具体的内容分发方法。

2 模型与定义

2.1 网络模型

军事信息系统通信网络在战时要覆盖整个作战区域，而且作战单元快速移动，要求一定要采用无线通信的方式;通信系统要具备较强的抗毁性，不能因为个别节点的毁坏而导致整个通信系统的瘫痪，要求一种无中心、分布式的方式进行组网。因此，我们设计了如图2所示的基于无线Mesh网络的军事信息系统。军事信息情报中心通过战术通信卫星与广泛分布小型分布式地面战进行通信，而地理分布邻接的小型分布式地面站之间可使用长距离无线通信技术(例如LoRa等)进行通信。另外，小型分布式地面站采用无线的方式与周围一定范围内的作战单元通信，距离较近的作战单元可直接与小型分布式地面站进行通信，距离较远的作战单元通过短距离无线通信技术(例如D2D等)组成多跳的无线Mesh网络与小型分布式地面站进行通信。在这样的网络结构中，小型分布式地面站充当了无线Mesh网络中的MR，构成网络骨干;各作战单元充当了MC，通过自组网的方式与小型分布式地面站建立通信。

图2 基于无线Mesh网络的军事信息系统

由于内容分发技术的引入，可以将小型分布式地面站作为镜像服务器，情报信息中心根据各作战单元对于各项内容的订阅情况，统计各项内容的热度信息，将内容镜像分发至相应的分布式地面站，以便各作战单元可以就近获取所需的内容。对于军事信息系统中的内容和节点，我们给出如下形式的定义。

定义1 内容对象集合。军事信息系统中的内容被划分为若干个内容对象，所有内容对象组成内容对象全集O，该集合可表示为O={Obj1,Obj2,...,Objk,...}，其中内容对象Objk的热度为prk，容量大小为sk。

定义2 通信节点集合。所有的作战单元组成了CU集合，即M={CU1,CU2,...,CUm,...};所有的小型分布式地面站组成了GS集合N，即N={GS1,GS2,...,GSn,...}。

在合理的内容分发策略下，情报信息中心根据各内容对象的订阅情况，将内容对象的镜像分发至小型分布式地面站，由于各地面站的存储能力有限，每个地面站只能存储部分的内容镜像。为了简化网络模型，可以假设所有的小型分布式地面站拥有共同的存储容量SC。在我们设计的多跳无线Mesh网络中，不同节点之间的通信延迟存在较大的差异，假设作战单元CUm与地面站GSn之间传输内容对象Objk的通信延迟为dmn(k)(∀m∈M,n∈N,k∈O)。由于内容订阅情况的细微变化不会对信息系统的整体传输时延产生太大的影响，因此可以设置内容分发周期，在每个周期开始时重新对各地面战的内容分发策略进行更新。在周期内，当某个内容对象发生更新时，情报信息中心将更新的内容镜像分发至相应的地面站，然后各地面站根据就近服务原则将内容更新推送至订阅了该内容的作战单元。

定义3 内容更新模型。已有的研究表明[9]，内容对象Objk的更新频次符合参数为λk的泊松分布。

在如上述的网络模型下，最终到各分布的作战单元的内容分发由地面站和作战单元之间协同完成，缓解了无线网络资源限制引发的网络瓶颈问题。另外，由于分布式地面站缓存了情报信息中心的内容，各作战单元的主动内容请求可以在最近的缓存有该内容的地面站得到服务，降低了网络的平均请求时延，提升了军事信息系统的服务质量。由此可见，设计合理的内容分发方法，以决定将哪些内容镜像分发至哪些分布式地面站，对基于无线Mesh网络的军事信息系统的网络性能具有关键性的作用。

2.2 问题定义

为了便于描述本文提出的基于无线Mesh网络的内容分发问题，我们引入两个决策变量x=[xmnk]和y=[ynk]。其中，ynk=1当且仅当将内容对象Objk的镜像分发至地面站GSn;xmnk=1当且仅当从地面站GSn将内容对象Objk推送给作战单元CUm。根据统计得出的各内容对象的热度信息prk(τ)，可以得到单位时间内容更新造成的网络中的总传输时延的期望值如下:

(1)

该期望值反映了网络中的内容分发延迟，因此可以将其作为内容分发问题的优化目标。

由于地面站的存储容量有限，故决策变量y=[ynk]需满足约束条件：

(2)

另外，为了确保网络模型中的就近服务原则，两个决策变量必须满足如下的约束条件:

(3)

其中Δ是一个很大的正数(如Δ=max{dmn})。当ynk=0时，由于Δ很大，故该约束无效;当ynk=1时，作战单元CUm必须从最近的拥有相应镜像的地面战获取内容，否则违反该约束条件。根据以上分析，可以对军事信息系统中基于无线Mesh网络的内容分发问题进行如下定义。

定义4 内容分发问题。在分布式地面站容量(2)和就近服务原则(3)的约束下，将情报信息中心各内容对象的镜像分发至地面站，对T最小化，以降低无线Mesh网络中传输时延的期望值。

已有的研究表明内容分发问题是NP困难问题，因此定义4中所描述的无线Mesh网络中的内容分发问题也是NP困难问题。在后续的章节中，将给出该问题的解决方法并进行验证。

3 无线Mesh网络中的内容分发方法

由于该问题的NP困难性，我们无法求解出该问题的最优解。本节将给出基于贪心策略的分布式四阶段启发式算法(Four Phase Based Heuristics, FPBH)，用于计算内容分发策略。根据各内容对象的订阅信息，统计各个内容对象的热度，并据此计算每个内容对象所需的镜像数目。对于所需镜像数目为p的内容对象，将地面站组成的网络骨干进行p划分，在每个划分中选择一个镜像分发位置。由于该方法的分布式特性，不过度依赖于情报信息中心的计算能力，适用于军事信息系统中无线Mesh网络的内容分发应用场景。

3.1 热度信息收集阶段

该阶段运行于内容分发周期τ，主要目的是收集内容对象的订阅信息，并根据该信息计算各内容对象在下一周期τ+1的热度，这一阶段可分为两步进行。

(1)周期τ期间:每个地面战维持一张表，该表用于存储〈GSn,Objk,subnk〉形式的元组，其中subnk表示地面站GSn处收到的对于内容对象Objk的订阅数。每次有新的订阅/取消消息到达GSn时，该表被更新一次，相应的subnk值进行+1/-1操作。

(2)周期τ结束:各地面站将收集到的订阅信息发送至情报信息中心，情报信息中心据此统计各内容对象的热度，并计算各内容对象所需的镜像数目，广播至所有的地面站。具体的步骤如下:

(a)各地面站将含有订阅信息的表发送至情报信息中心，然后情报信息中心整合所有收到的信息。对于每个内容对象Objk，根据公式(4)计算其热度:

张家明对我挺不错的，有吃的喝的第一个想到我。只是他家里人不大喜欢我。我理解，他们穷是穷了些，但好歹也是本地人，他父母认为我是外地来的，所以对我不冷不热。而张家明一直维护我，说我聪明，懂事，而且漂亮。

(4)

(b)由于在文献[8]中已经证明，最优的内容分发策略是每个内容对象Objk的镜像数目正比于。因此，在分布式地面站容量SC的约束下，情报信息中心可以根据公式(5)计算Objk在周期τ+1所需的数目pk。

(5)

(c)情报信息中心创建一张包含有〈Objk,|Objk|,pk〉形式元组的镜像列表(Replica List, RL)，并广播至所有的地面站。该表按pk值进行分组，并降序排列。在每组内部，元组按内容对象容量大小|Objk|进行升序排列，最大化地利用各小型地面站的存储容量。

3.2 网络拓扑划分阶段

为了充分利用无线Mesh网络的分布式特性，我们对分布式地面站构成的网络骨干进行拓扑划分，作为本节中分布式的内容分发方法的基础。因此引入图划分算法，对地面站构成的网络拓扑分别进行p划分，其中p的取值包括所有pk的可能值。图划分算法即是将一个图划分为两个或者两个以上大小基本一致的不相交子集，以使得各个划分之间的割边最少。在每一次图划分后，要从该划分内选取一个领导节点(Leader Node, LN)，用于运行该划分的内容分发策略生成算法。由于一个节点可被选取为多个划分的LN节点，因此选择LN节点的原则是挑选该划分内被选取为LN节点次数最少的节点。

假设所有地面站构成网络拓扑图G,G(u,v)表示将图G进行u划分得到的第v个划分子图。对于划分G(u,v)，被选取的LN节点记为LN(u,v)，该LN节点在划分G(u,v)内为所需镜像数量为u的内容对象选取一个镜像分发位置。结合以上数学符号，拓扑划分阶段的算法描述见算法1。

算法1. 网络拓扑划分算法。

输入:图G,pk。

输出:包含拓扑划分信息的Map-List。

1.foru=1→max{pk}do;

3.forv=1→udo

4.if|G(u,v)|=1then

5.LN(u,v)←G(u,v);

6.else

7.LN(u,v)←划分G(u,v)中被选取次数最少的点;

8.endif

9.endfor

10. 将Map(LN(u,v),G(u,v))添加到Map-List的第u项;

12.endfor

图3 网络拓扑划分算法示例

在算法1中，第2行表示对图G进行u划分。由于目前对于图划分算法的研究较为成熟，故其实现可参考文献[10]中的快速算法。图3以地面站数量为10的网络骨干为例，展示了对拓扑分别进行1划分至4划分及相应的LN节点选取详情。由于该算法的运行需要了解全局的地面战分布拓扑信息，因此该算法的执行过程是在情报信息中心进行。在该算法执行完毕后，情报信息中心将得到的Map-List广播给所有的地面站。由于各分布式地面站组成的骨干网络相对固定，该算法在网络部署阶段执行一次便可。

3.3 分发策略生成阶段

在定义4中我们提到内容分发问题的总体优化目标是传输时延的期望值T，当对问题进行分布式处理时，必须将优化目标分布化。对于需要镜像数目为u的内容对象Objk，定义在某个划分G(u,v)中，地面站集合为N′，与其关联的作战单元集合为M'。对于M'和N'构成的子网络，可以得到单位时间内容对象Objk更新造成该子网络中的总传输时延的期望值如下:

(5)

结合该优化目标，分发策略生成算法在划分G(u,v)内选择内容对象Objk的一个镜像位置，使得该内容对象的更新在相关子网络里造成的T′(k)最小。

算法2. 分发策略生成算法。

输入:集合M,N,O,变量λk,SC,Map-List,RL。

输出:决策变量y=[ynk]。

1.forevery group in RLdo

2. multicast a message containing the group of object

3. replicas to the corresponding list of LNs in Map-List;

4. upon receiving the message,LN(u,v) will do:

5. lookup the Map-List for theuth item;

6.if|G(u,v)|=1then

8.ynk←1; // n is id of GS

9.endfor

10.else

12.forallObjkin the received groupdo

13. select theGSn0that minimizesT′(k);

14.yn0k←1;

15.endfor

16.endif

17.endfor

策略生成算法的详细描述如算法2所示，该算法在热度信息收集阶段结束后立刻执行，以确定下一个周期的内容分发策略。在该阶段，领导节点LN(u,v)为需要镜像数量是u的内容对象在本划分内选择一个最佳的镜像缓存位置。通过逐个镜像位置的选择，最终生成合理的分发策略。

3.4 内容镜像分发阶段

在上一阶段分发策略生成后，各分布式地面站立即根据得到的决策变量y获取相应的内容镜像。该阶段的内容镜像分发，既可采用基于字典服务[11]的协作式内容分发，也可采用非协作式内容分发。以非协作式内容分发为例，当某个地面站在该周期内需要存储Objk的镜像时，若Objk的镜像已在其缓存中，则不必再向情报信息中心获取;否则，从情报信息中心获取Objk的镜像。

纵观该算法的四个阶段，只有网络拓扑划分阶段算法的执行依赖于情报信息中心，而该算法只有在网络部署时执行一次，不影响整体的分布式特点。由于四阶段内容分发算法的分布式特性，克服了集中式算法大量的运算依赖于中心服务器的缺陷;同时，在算法运行过程中，各节点之间不存在大量的通信消息交互，避免了引入大量的额外通信开销。

4 仿真实验

本节通过仿真实验的形式，将我们提出的算法与现有文献中的内容分发方法进行比较，并对实验结果进行分析，以验证我们提出的FPBH的性能。

4.1 实验环境

我们使用OMNeT++[12]仿真工具验证测试本文提出的FPBH算法，生成Mesh拓扑结构来仿真固定的WMN网络。随机生成的网络拓扑共包含200个节点，其中包括25个地面站和175个作战单元。无线通信协议设置为IEEE 802.11 g，通信带宽为18 Mbps。无线通信的最大有效距离为140 m，相邻两个节点之间的平均距离为100 m。

一般来说，内容对象的热度一般服从Zipf分布，即长尾分布。在仿真实验中，地面站依据参数为v=0.85的Zipf分布发出订阅消息。内容对象的大小符合[0.5→4]MB的均匀分布，而每个小型地面站的存储容量为256 MB。虽然实际中，地面站的存储容量和内容对象的大小要远大于我们实验中所使用的值，但是增大这些数值的时候我们的FPBH算法依然有效。在本次实验中，我们将FPBH算法与已有的Random和 Lat-CDN[13]进行比较。每组实验中，通过独立10次重复实验来得到平均结果。我们进行了三组实验来比较三种不同的性能参数，即平均请求时延，网络负载和负载分布。

4.2 实验结果及分析

在第一组实验中，我们改变网络中内容更新频率，对网络中的平均时延进行观察，实验结果如图4所示。这里所说的平均时延指的是地面站处理完成所有作战单元相关更新内容推送所消耗的平均时间，服务所有的作战单元消耗总时间除以数量。显而易见，在各组实验中平均请求时延都随着内容更新频率而增长。我们所提出的FPBH算法的平均时延增长速度要慢于其他的方法，也就是说FPBH算法时延性能优于其他算法。这是由于FPBH根据内容热度来分发内容镜像，这使得它们要优于Random和Lat-CDN。

图4 平均时延对比图

在接下来的这组实验中，我们改变内容更新频率，对总的网络负载进行统计，网络负载的对比结果如图5所示。实验结果显示网络负载均随着内容更新频率而增长， 本文提出的FPBH明显慢于另外两种方法。这是因为FPBH根据内容热度来分发内容镜像，使得大多数请求不需要经过太多跳的传播便能得到服务，这样大大减少了网络负载，因此FPBH的网络负载性能优于Random和Lat-CDN。

图5 网络负载对比图

在最后这组实验中，我们将内容更新频率设置为12，来观察网络中各地面站的负载分布情况，结果如图6中的箱线图所示。箱线图有五个特征点，分别是上边缘，上四分位数，中位数，下四分位数和下边缘。从图中我们可以看出，三种算法中网络负载分布最差的是Random;由于Lat-CDN根据传输延迟分配副本，因此其负载分布优于Random;考虑到内容热度的FPBH负载分布明显优于其他方案。另外，由于FPBH通过拓扑划分进行内容镜像分发，避免了镜像过于集中，进一步优化了负载分布。

图6 负载分布对比图

综合上述实验结果，本文提出的无线Mesh网络中的四阶段内容镜像分发方法FPBH在平均时延、网络负载和负载分布性能上优于现有的Mesh网络中的其他分配方案。因此，FPBH方案可大大提高无线Mesh网络的性能，满足军事信息网络的内容分发需求。

5 结 语

本文针对军事信息系统中基于无线Mesh网络的内容分发问题，设计了立体化的军事情报信息中心-战术通信卫星-小型分布式地面站-作战单元网络结构模型。在此基础上，提出了全新的分布式四阶段启发式算法。该方案根据各内容对象的订阅信息，统计各个内容对象的热度，并据此计算每个内容对象所需的镜像数目。对于所需镜像数目为p的内容对象，将地面站组成的网络骨干进行p划分，在每个划分中选择一个镜像分发位置。仿真实验证明，我们所提出的算法在平均时延，网络负载和负载分布等方面上均有良好的性能，能够极大地提高军事信息系统中网络资源受限场景下的服务质量。

[1] 刘觅,彭木根,王文博. 基于IEEE802.16—2004标准的Mesh机制 [J]. 中国电子科学研究院学报, 2006, 1(1): 75-80.

[2] Akyildiz I F, Wang X, Wang W. Wireless mesh networks: a survey [J]. Computer networks, 2005, 47(4): 445-487.

[3] Das S M, Pucha H, Hu Y C. Mitigating the gateway bottleneck via transparent cooperative caching in wireless mesh networks [J]. Ad Hoc Networks, 2007, 5(6): 680-703.

[4] Vakali A, Pallis G. Content delivery networks: Status and trends. Internet Computing, IEEE, 2003, 7(6):68-74.

[5] 马晓亭.基于802.16d无线Mesh网络的集团军战役指挥所通信系统[J].电信快报,2008, 10(10): 8-11.

[6] 刘显静,吴学智,何如龙等. 基于无线Mesh网络的舰艇编队通信网运用研究[J]. 舰船电子工程, 2012, 32(6): 92-94.

[7] Jin S, Wang L. Content and service replication strategies in multi-hop wireless mesh networks [C]. Proceedings of the 8th ACM international symposium on Modeling, analysis and simulation of wireless and mobile systems, 2005: 79-86.

[8] Wang K, Chen Z, Liu H. Push-Based Wireless Converged Networks for Massive Multimedia Content Delivery [J]. IEEE Transactions on Wireless Communications, 2014, 13(5): 2894-2905.

[9] Johnston M, Lee H W, Modiano E. Robust network design for stochastic traffic demands [J]. Journal of Lightwave Technology, 2013, 31(18): 3104-3116.

[10] Kernighan B W, Lin S. An efficient heuristic procedure for partitioning graphs [J]. Bell system technical journal, 1970, 49(2): 291-307.

[11] Stoica I, Morris R, Liben-Nowell D, et al. Chord: A Scalabel Peer-to-Peer Lookup Protocol for Internet Applications [J]. IEEE/ACM Transactions on Networking, 2003, 11(1): 17-32.

[12] 吴剑锋,郭英,范海宁. OMNeT++网络仿真器的设计原理分析[J].微计算机应用, 2008, 29(5): 34-37.

[13] Pallis G, Vakali A, Stamos K, et al. A latency-based object placement approach in content distribution networks[C]. IEEE Third Latin American Web Congress (LA-WEB), 2005: 1-8.