一种多机会确认的无线可靠广播机制

李建强，张大龙，宋 杨，侯维岩*

(1. 郑州大学 信息工程学院，河南 郑州 450001；2. 上海大学 机械自动化学院，上海 200072)

在分布式无线网络低时延、高可靠的应用场景中，传统的路由协议很难在传输时延和开销均最小时，保证网络控制命令的发送[1].采用可靠单播方式发送控制命令，可保证传输可靠性，但传输时延和开销难以满足业务需求.采用广播方式发送控制命令，传输时延和开销较小，但传输可靠性难以保证.现有控制命令，由于其分组长度通常较小，多采用广播方式传输.在低时延、高可靠场景中，如无人机群组控制命令的发送，其发送速度快、节点密度高、拓扑结构变化快，广播冲突严重，业务成功率较低，传输可靠性难以保证.如果加入确认机制，由于广播业务的开放性，广播确认开销随节点数增加呈指数增长[2].目前，除了常见的基于载波侦听的洪泛广播方式外，还没有一种专门针对低时延、高可靠应用场景的高效广播机制.全网广播协议可分为洪泛、概率转发、骨干转发3类[3].洪泛广播冗余转发次数多，易致广播风暴，其效率低、时延长[4].概率转发为每个节点分配参与转发的概率，能有效减少广播转发次数，但难以通过选择合适的转发概率来保证全网覆盖[5-6].有研究人员提出利用部分节点信息寻找最优骨干转发节点，减少广播冗余，由于缺少有效的确认机制，导致广播业务大量重传[7-8].有研究人员提出基于全网可靠广播协议在单跳间采用编码重传技术降低广播重传开销，但广播的实时性难以保证，同时广播业务的确认开销仍然较大[9-11].

针对可靠广播业务中的上述问题，笔者提出一种基于多机会确认的可靠广播(multi-opportunities broadcast acknowledgement，简称MOAP)机制，利用无线信道的开放特性和两跳邻节点路由信息，通过转发节点选择、监听转发、转发捎带及邻节点辅助确认4种方式，提高广播业务确认效率，减少可靠广播传输时延和开销，从而在较小代价下，保证无线网络中广播业务传输的可靠性.

1 多机会确认机制的核心思想

基于广播信道的开放性，对广播业务进行确认时，会同时启动多个确认分组的发送，进而造成确认分组间的相互冲突，延长了确认时延，降低了确认效率[12-13].然而，利用其开放性，当一个广播业务在网络中传输时，对于某一接收节点来说，可能多次接收到同一广播业务分组.对特定广播业务的确认分组，其可能被多个节点接收.广播业务传输时，利用广播分组的上述重复接收特性，可降低分组的重传概率.利用邻节点对确认分组的接收，帮助源节点完成确认.基于转发节点的转发，进行捎带确认.若不对广播业务在网络中的传输加以约束，往往会在网络中形成广播风暴，因此在进行多机会确认时，还需对转发节点进行选择，以降低传输开销和冲突概率.

图1为多种确认方式示意图.源节点的一跳邻节点分为转发节点和非转发节点.非转发节点采用直接确认方式向源节点回复确认(acknowledge,简称ACK)(图1(a))；转发节点转发广播业务分组，源节点利用对转发广播业务分组的监听实现捎带确认(图1(b))；非转发节点回复的ACK同样被转发节点监听，转发节点转发广播业务分组时捎带其确认信息，可协助源节点完成对确认分组的接收，降低由于确认分组传输失败造成的重发(图1(c))；当非转发节点未能正确接收广播业务分组时，可再次利用转发节点的转发完成分组接收，此时该节点启动确认机制，完成源节点的确认(图1(d)).最后，针对未收到确认分组信息的邻节点，源节点需采用单播方式再次发送该广播.

图1 多种确认方式示意图

2 多机会确认机制的关键技术

多机会确认机制基于广播信道的开放性，旨在提高可靠广播业务确认效率、降低广播业务传输冲突和减少业务传输时延.在多机会确认时，还应考虑可靠转发节点集合的选择和多机会确认时机等问题.

2.1 可靠转发节点集合的选择

借鉴虚拟骨干网的设计思想，选择骨干节点进行广播转发，可明显降低广播开销.在该文机制中，转发节点的选择，需考虑分组确认问题.源节点在发起广播分组时，启动转发节点选择机制.

定义1源节点S所有两跳范围内邻节点集合为PS，所有一跳邻节点集合为GS，则源节点两跳邻节点集合US=PS-GS.如果集合G中节点g1与集合U中节点u1间存在双向传输路径，则称g1与u1间存在一条无向边，简称g1与u1间存在一条边.

定义2属于集合GS且未收到该次广播业务确认分组的节点集合为一跳待确认集合QS.

定义3集合RS为转发节点集合，DS为非转发集合，RS⊆GS且满足下列条件：

(1) 集合U中所有节点均与集合R中至少一个节点间存在边.

(2) 集合D=G-R.当D不为空集时，D中所有节点均与集合R中至少一个节点间存在边.

(3) 在满足上述条件的情况下，集合R的基数最小.

图2 转发节点的选择

2.2 多机会确认时机的选择

2.2.1 广播的3种确认机制

在广播过程中，源节点通过3种机制来确认周围邻节点是否收到了正确的广播分组.3种机制分别为：直接收到广播分组；源节点监听到邻节点转发广播；源节点监听到转发节点转发广播.

2.2.2 可靠广播的确认过程

多机会确认过程如下：

(1) 对源节点S进行广播分组，一跳范围内邻节点集合G收到广播分组，查看非广播转发中是否有自己的ID标识，判断自己是否需要回复广播ACK.如果有自己的ID，依照ID顺序在N+d(d为冗余间隔)个帧间隔内回复广播ACK.帧间隔时长为

t=WT，

(1)

(3) 转发节点转发时，源节点一跳范围内邻节点第1次收到来自自己邻节点S的广播时，立即向源节点回复ACK.源节点S的待确认集合Q中的节点，有多次确认广播分组业务可靠性的机会.多机会确认机制的核心是源节点必须直接或间接确认一跳范围内邻节点是否正确收到广播分组.

(4) 若一个确认周期后，仍然有未确认的邻节点，为保证广播业务的可靠性，可利用单播对未确认节点进行补充确认.源节点S没有监听到转发节点L或E的转发广播时，立即对转发节点L或E进行单播.若源节点在转发结束后，既没有收到邻节点A的确认分组，也没有监听到转发节点L转发此广播，源节点S应立即对邻节点A和L进行单播，并选择它们作为转发节点.

3 仿真验证

在Ubuntu平台上采用NS2仿真工具，对MOAP机制性能进行仿真，仿真参数如表1所示.

表1 仿真参数设置

仿真过程中，重点研究广播业务的发送成功率和传输开销.广播递交率(packet delivery ratio, 简称PDR)为

(2)

其中：m为接收到的有效消息数，n为应接收的消息数.

广播开销(broadcast overhead)为

(3)

其中：f为每个节点要发送的平均消息数，n为节点数.

图3是多机会确认机制与基于IEEE 802.11的泛洪(flood)协议的广播递交率比较.从图3可知，当节点数增加，广播递交率也随之增加[14].多机会广播确认机制的递交率明显优于泛洪协议的，其平均递交率比泛洪协议的高20%左右.在节点数较高时，多机会确认机制的广播递交率可达100%.

MOAP机制采用端到端的确认机制，可保证节点通信范围内所有节点广播的可靠性.在节点较少的网络场景中，网络可能是间歇连通甚至非连通的，存在孤立节点，网络的广播递交率比较低，MOAP机制可保证广播的可靠性，而flood协议没有有效的确认机制，不能保证通信范围内广播的可靠性[15].

随着节点数增多，洪泛协议基于广播信道的开放性，使接收节点能多次接收相同广播分组，可提高广播业务发送的可靠性.但是，随着节点数增多，洪泛协议会产生大量的重复广播业务，信道冲突加剧，降低了单次业务发送的成功概率.同时，由于未采用确认机制，广播业务传输中，对其可靠性的保证只能是“尽最大努力”完成，并不能保证每个广播业务端到端发送的可靠性.MOAP机制引入了确认机制和有限转发机制，在减少网络传输业务量、降低无线信道冲突的同时，保证了广播业务端到端发送的可靠性.

图4为多机会确认机制与泛洪(flood)协议的广播开销比较.由图4可知，当节点数少时，两者开销几乎一样；随着节点数增多，多机会确认机制的广播开销远小于泛洪协议的广播开销.

图3 广播递交率比较 图4 广播开销比较

当节点数少时，存在孤立的节点，多机会确认机制要保证广播的可靠性，需进行多次广播业务，因此广播开销和泛洪协议的一样大.在泛洪协议广播中，随着节点数增多，每个节点第1次收到广播分组均会转发此广播分组，导致广播开销迅速增加、信道占用时间长、广播冲突增大.MOAP机制选择有效的邻节点为转发节点，在减少广播开销的同时，也使信道的利用率得以提高.

由仿真结果可知，无论节点数多少，多机会确认机制的广播递交率明显优于泛洪协议，其广播开销也明显优于泛洪协议.

4 结束语

笔者提出了一种多机会确认的无线网络广播机制，采用多机会确认方法，选择邻节点转发广播，减少了广播冗余，提高了广播业务的可靠性.仿真结果表明，多机会广播确认机制在降低广播开销的同时，能提高广播确认的效率及广播业务的可靠性，适用于广播发布可靠性要求高的场景.