一种应急通信网加权广播算法＊

秦 娜，刘宴涛

(1.嘉应学院计算机学院，广东 梅州 514015；2.蒙古研究大学)

0 引言

无线自组织网络，简称无线自组网（Ad hoc Network），又称移动自组网（MANET-Mobile Ad hoc Network），是一种特殊的无线网络形式。这种网络为某种特殊应用或特殊目的而构建，由一组带有无线收发信机的移动终端组成，网络节点同时充当终端主机和路由器的角色，结合了计算机网络和无线通信的优势，具有无中心、自组织、多跳路由、动态拓扑、快速布设、不依赖基础设施、体积小、能耗低、分布式、合作通信、高抗毁、可移动、可重组等特点。无线自组网与传感器网络、物联网等无线网络技术具有密切的联系，其主要应用场合有抢险救灾、战场通信、野外救援、会议庆典、水库、矿山、公安、消防、森林防火和公共交通等。

应急通信网络是无线自组网在民用领域的一种典型应用，这种网络主要应用于地震、洪水、泥石流等灾难之后临时创建应急通信保障。以地震为例，灾害过后由于电力、通信等基础设施损毁殆尽，灾难现场的情况无法及时为外界获知，给快速有效的施救造成了极大的困难。地震过后抢救生命意味着与时间赛跑，如果震后超过了72 小时，人员生还的希望就很渺茫，所以快速准确地采集到震区的实时情况（比如人体红外、声音、图像、视频、生命体征等）是灾难救助的首要任务。这就把不依赖于基础设施、快速、自动的通信保障的重要性提到了前所未有的高度，而无线自组网正好符合了这一要求。

应急通信网络的研究重点包括宽带无线接入、单/组/广播路由算法、网络的覆盖性和连通性、移动性管理、功率控制等等。康守信[1]针对矿井下多点应急救援研究了基于无线Mesh网络的应急通信基站，提出了应急通信基站无线中继与无线覆盖的方案，并对应急通信基站的最大传输距离进行了模拟仿真。王鲁宁[2]提出了系统化、扁平化、智能化的感知网络全覆盖的现代应急管理体系的建设思路。贺灿辉[3]结合消防应急通信构建Mesh 网络以提高消防应急的质量和安全性。肖强[4]对应急通信技术的发展、特点和趋势进行综述。周雄伟[5]通过对应急通信和公共通信的特点比较，提出了应急通信的服务保障模式，并对应急通信标准规范给出建议。姜海涵[6]针对信道吞吐量低、阻塞率高等问题，提出了应急通信异构网络的信道选择方法。张昊晔[7]基于认知无线电技术，提出了不同任务策略下的优化目标和约束条件，实现网络效能最大化。

可靠性和有效性是应急通信网的两项重要指标，前者表示信源发出的数据包能准确可靠地为所有信宿接收，后者表示网络的传输速率快、资源消耗少。然而在实际应用中这两者往往是一对矛盾，为了提高可靠性，需要增加节点转发概率，减少丢包率，而这又不可避免地加剧信号冲突和信道资源占用，降低有效性。为了调和这两者的矛盾，本文提出了一种加权的概率广播算法，通过引入加权系数和目标函数取得有效性和可靠性的折中。

本文的后续如下：第1 节通过仿真实验测算节点度和网络连通度的关系，为概率广播实验的节点密度提供定量依据；第2 节介绍概率广播的基本原理并解释相变现象；第3节提出了加权的概率广播算法，通过引入加权系数和目标函数在有效性和可靠性之间进行折中，通过大量仿真实验测算最优广播概率，并通过仿真实验来对比加权概率广播和普通广播；第4 节给出本文的结论。

1 应急通信网络的连通性

连通性是应急通信网络的重要指标，所有路由算法的有效性都是以网络连通为前提的。影响网络连通性的因素有很多，如网络的拓扑和覆盖范围，节点的数目和通信半径，对于移动网络还包括节点的移动性。因此，很难对网络连通性做出精确的理论分析。本节应用Ad hoc 网络仿真工具箱ANSim，对网络连通性做仿真研究。

网络连通概率与网络平均度有关。节点u的度是指与u直接相连的节点数目，全部节点度的平均值称为网络的平均度。假设网络覆盖面积为S，节点的通信半径为R，节点数目为n，则网络平均度由式⑴决定。

仿真实验1：n个节点均匀分布在1000m×1000m的矩形范围内，节点通信半径为250m，节点采取随机点移动模型。通过调整n的值并通过公式⑴计算得到一组平均度k的值，应用ANSim 的统计功能可以得到网络连通概率（即网络最大连通组中节点数占全部节点数的比例）和平均度k的关系曲线，如图1 所示。由此可见，网络连通概率随着节点度的增加而提高，当节点度达到6 时，网络连通概率已超过95%，表现出很健壮的连通性。

图1 网络连通概率和节点平均度的关系

2 概率广播算法

泛洪广播，简称泛洪，是一种广播路由技术，是指数据包从源节点发出后，所有收到该数据包的中间节点对其进行中继转发，一级一级地向后传递，像洪水泛滥一样，直到所有节点都收到该数据包为止。泛洪可以单独作为路由算法使用，也可以辅助其他路由算法，比如动态源路由DSR(Dynamic Source Routing)、按需组播路由协议ODMRP(OnDemand Multicast Routing Proto-col)，用于这些路由的建立与更新。

普通的泛洪广播算法中，中间节点以概率1 转发数据包，网络中会出现大量的数据包，造成剧烈的信号冲突和信道浪费。概率广播[8]可以缓解这一问题，所谓概率广播是指中间节点收到上游节点发来的数据包后以概率p转发该数据包。下面基于OPNET 设计一组仿真实验验证泛洪概率p对于广播算法的影响。

仿真实验2：如图2 所示，50 个节点随机分布在1000m×1000m的矩形范围内，节点通信半径为250m，节点采取随机点移动模型，移动速度15m/s。“包递交率”定义为网络中收到数据包的节点数占全部节点数的比率。改变广播概率p并统计包递交率，结果如图3 所示，可见当广播概率达到0.6 时，包递交率已经超过90%，这被称为相变现象[9]，说明当广播概率达到某个门限值之后进一步增加概率已经没有太大增益，反而无谓地消耗网络资源。

图2 应急通信网

图3 应急通信网的概率泛洪

3 针对应急通信网的加权概率广播

应急通信网的包递交率反映了网络可靠性，高的包递交率意味着网络中大部分节点都收到了数据包。然而，高的包递交率需要高的广播概率支撑，后者会产生大量的中继转发和数据包副本，造成大量的信号冲突和信道浪费，因此降低了网络有效性。可见，网络的可靠性和有效性是一对矛盾，为了实现二者的折中，对于不同的应用需求提供个性化服务，本文提出一种加权概率广播算法，具体参照下面的目标函数。

其中，α，β，γ取值均介于(0,1)之间。β等于转发数据包的节点数与收到数据包的节点数的比值，称之为包传输的归一化代价函数。在收到数据包节点数相同的条件下，参与转发数据包的节点数越少，信道资源消耗就越少，有效性就越高，因此β描述了网络的有效性，β越小则有效性越高。γ代表包丢失率（即1-γ代表包递交率），1-γ定义为收到数据包的节点数占总节点数的比值，可见1-γ描述了网络的可靠性，1-γ越大则网络越可靠。α表示在有效性和可靠性之间折中的加权系数，高的α代表高有效性和低可靠性，低的α代表低有效性和高可靠性。最后，T是目标函数，代表综合考虑可靠性和有效性之后的总的资源消耗，对于具体应用场景，总是希望β和γ尽可能地小，因此对于一定的节点度k，应该确定广播概率p以使得T尽可能小，称这个概率p为对应于该应用场景的最优广播概率。

基于实验2 的仿真设置，采用5 个加权系数α，得到广播概率p和目标函数T的关系，如图4所示。每条曲线对应于一个加权系数，每条曲线的最低点是所寻找的最优广播概率。

图4 目标函数T（n=50,k=8.817）

类似于实验2 的仿真设置，通过改变节点数n（对应于改变节点度k），通过一系列实验可以得到不同的网络配置下最优广播概率的取值，如表1所示。

表1 不同网络配置下广播概率最优解

实际应用中，对于表1 中没有列出的网络参数配置，可以采用平均估值的方法得到最优概率。比如对于k=12，α=0.2，可以估计出p=0.66。进一步，基于这组参数通过仿真实验可以对概率广播和普通广播（相当于p=1 的概率广播）进行性能比较。实验结果如图5 和图6 所示。可见，通过使用加权系数α，概率广播的归一化代价函数减少了大约40%，而损失的包递交率仅仅不到10%。

图5 两种广播算法包递交率的比较

图6 两种广播算法归一化代价函数的比较

4 结论

针对应急通信网络，在分析网络连通性和节点度之间关系的基础上，本文提出了一种加权的概率广播算法，该算法通过设置加权因子α和目标函数T，在网络通信的有效性和可靠性之间进行折中，以满足不同网络规模和应用场景的具体需求。应用该加权概率广播算法，根据网络规模和节点平均度，通过仿真实验可以得到最优广播概率p，然后以该最优广播概率进行概率广播。仿真实验表明，通过使用该算法确定的最优广播概率可以以很小的包递交率损失换取很大的网络广播归一化代价的增益，从而获得极大的有效性提升。