0引言
无线网络可以看作通过无线介质进行通信的一组节点的集合。在无线网络中，节点能正确接收到其它节点发送消息的最长距离称为节点的传输范围。在消息传输过程中，每个节点只能与其传输范围内的另一节点直接通信。广播是无线网络中的一种基本操作，它在各种网络协议中应用广泛。广播是从源节点发送消息到网络中的其它所有节点的过程。由于整个广播区域的范围要大于单个节点的发送范围，所以广播过程需要中继节点转发消息。因而，对于任何拓扑结构的网络，都必须在计算出节点的调度时间后，才能进行广播调度。在广播调度过程中，网络中所有节点接收到消息的时间被称作广播延迟，如何有效地降低广播延迟是无线网络研究中的重要工作。干扰是导致广播延迟增加的一个重要原因。节点发送的消息能够对其它节点接收消息产生影响的最长距离称为节点的干扰范围。通常情况下，节点的干扰范围都要大于节点的传输范围。当一个节点的多个邻居节点同时向它发送消息，该节点就会同时收到多个消息，导致该节点无法正确接收到所需要的消息，我们就称在此节点处发生了冲突。此外，节点在接收消息的过程中，如果其干扰范围内的节点也在同时发送消息，那么该消息就对节点的消息接收过程产生干扰，导致节点无法正确接收消息。这两种情况都影响了节点正确接收消息。因此，在广播过程中，减少节点在发送消息时对其它节点接收消息产生的干扰，避免冲突的产生，能有效地降低广播延迟。本文的其它部分安排如下：第一部分介绍了该领域研究的相关工作。第二部分介绍了本文使用的网络模型并对研究问题进行了描述。第三部分对算法进行了详细介绍，并对算法的结果进行了分析证明。第四部分通过仿真实验对算法的性能进行比较。第五部分为本文的结束语。
1相关工作
在广播过程中，最早使用的协议是洪泛协议[1-3]。在洪泛协议下，每个节点在接收到消息后就将消息发送给他的所有邻居，但是洪泛协议可能导致严重的信道竞争，消息冲突与重传等问题，也就是产生了广播风暴[4,5]。由于使用洪泛协议产生的广播风暴问题会严重增大广播延迟，因此需要研究新的广播调度方法，来降低广播延迟。迄今为止，已经有很多研究人员做了大量工作来解决无线网络中的广播延迟问题。Chlamatac和Kutten提出了一个根据广播树进行调度的碰撞感知广播算法[6]。他们证明了对于任意的图模型，其算法都能实现较低的广播延迟。Chen等人在圆盘图(DiskGraphs,DGs)模型下研究了广播调度的干扰感知问题[7]。他们考虑的干扰范围和传输范围是不同的，他们使用α来表示干扰范围与传输范围的比值，并且在通常情况下，α>1。他们构建了一个基于广度优先搜索(Breadth-First-Search,BFS)树的广播调度算法。为了最大限度地减少广播延迟，他们还允许在BFS树同一层中的节点可以使用多种方式发送消息。Gandhi等人证明了在无线网络中，减小广播调度延迟问题是一个NP完全问题[8]。他们提出了一个从单节点到多节点的广播算法[9]。与先前的算法不同，该算法令一个节点在广播过程中多次发送消息。他们证明了该算法能在较低的延迟内完成广播过程，并给出了消息发送数量的上界。Yu等人提出了一个多消息广播算法[10]。他们假设节点不知道网络初始的拓扑结构，不会执行载波监听，他们的算法能将存储在k(1≤k≤n)个节点中k条消息以较短的发送到整个网络中，从而有效地降低广播延迟。特别是，当k=1时，算法可以看作单节点的广播算法。Huang等人在UDG模型下提出广播调度算法[11]。算法首先在网络中建立了一个连通控制集，然后算法在每一层中按照控制集中的顺序对节点进行调度。然后，他们又提出了不知道节点位置分布的常数近似算法[12]。算法首先将网络区域划分为相等的六边形，然后算法对六边形区域进行染色，如果两个六边形之间的距离小于(α+1)r，就分配不相同的颜色，否则就分配相同的颜色，最终按照六边形区域的颜色和BFS生成树来确定节点的调度时间。他们通过使用这两种机制来保证节点能以较短的时间完成广播过程，降低广播延迟。Mahjourian等人研究了广播调度的冲突感知问题[13]。他们在单位圆盘图(UnitDiskGraph,UDG)模型下考虑了在节点干扰范围内的冲突问题，并提出一个基于树的常数近似算法CABS。算法通过给节点染色来构建BFS树，并且根据颜色不同的节点不能同时发送消息，不能同时接收消息的原则，对节点进行调度，以保证在广播过程中，不会发送冲突，从而降低广播延迟。RaviTiwari和ThangN.Dinh对于无线传感器网络中的广播调度问题，他们还分别提出了集中式和分布式两种算法[14]。他们算法首先通过正六边形覆盖平面区域，然后在区域中建立坐标轴，并计算出各个六边形区域的坐标，利用坐标信息计算出个区域中的节点染的颜色，再根据节点不同颜色，确定节点调度的时间，该算法能以较短的时间完成广播过程。Z.Jiang等人提出了一个贪心的启发式算法[15]。该算法通过染色机制，以解决在基于BFS树的广播调度算法中，位于BFS树中不同层的节点也不能同时调度问题，从而降低广播延迟。虽然上文所提到的这些工作，在降低无线网络广播延迟问题的研究中已经取得了不错的结果，但这些研究仍然存在一定的不足。除了文献[15]外，其他文献中的基于BFS树的广播调度算法都是按照BFS生成树中的层顺序来调度节点，只有在上层节点都调度完成后，下层节点才能调度，这种情况不利于广播延迟的降低，并且文献[15]也没有给出在最坏情况下，算法广播延迟的上限。为了解决以上问题，我们提出了新的广播调度算法CBS，该算法能够保证节点在广播过程中，相互之间不会产生干扰，从而避免冲突的产生，成功完成广播调度。该算法还允许树中多个层的节点同时调度进行传输，并以较低的延迟完成广播过程。
2模型定义及问题描述
我们假设网络中所有的节点都是静态随机分布的，有着相同的传输范围和干扰范围，因此，我们可以使用单位圆盘图(UDG)模型，G(V,E)表示整个网络。我们用r表示网络中节点的传输范围，用αr表示节点的干扰范围，其中α为干扰范围与传输范围的比值，如果两个节点之间的欧氏距离不大于传输范围d(u,v)＜r，那么这两个节点可以直接通信，并且认为它们之间存在一条边。我们假设时间是离散的，每一条消息的发送都占有一个单位时隙。因为传输介质是无线信道，所以当节点发送消息时，他的所有邻居节点都能收到消息。当一个节点在同一时刻收到多条消息，我们就称在此节点处发生冲突，节点接收消息失败；当一个节点在同一时刻只收到一条消息，我们就称在此节点处没有发生冲突，节点成功接收消息。给定网络节点分布图G(V,E)，源节点s，节点的传输范围r和干扰范围αr。节点s想要广播一条消息到网络中其他所有节点，由于整个广播区域的范围要大于单个节点的发送范围，所以在广播过程需要其他节点转发消息。但是在多个节点进行消息转发的过程中，可能会产生冲突，导致消息发送失败，产生网络延迟。因此，算法需要解决的问题就是如何生成一个节点调度时间表，通过该时间表对节点进行调度，使得源节点s能以较低的广播延迟完成从发送一条消息到网络中其他所有节点的广播过程。算法中使用的符号定义如下：G(V,E)表示网络中的节点分布图，其中V表示网络节点的集合，E表示网络节点之间边的集合；s表示中发送消息的源节点；R表示网络的深度；Li(i=1,2,3…R)表示在树结构中每一层的节点集合；P(v)表示节点v的父节点，C(v)表示节点v的子节点；M表示主要节点集合，S表示次要节点集合，集合内的节点分别称为控制节点和连接节点[12]；rcvTime(v)表示节点v接收消息的时间，trTime(v)表示节点v发送消息的时间。
3冲突感知广播调度算法（CBS）
3.1算法描述
给定网络节点分布图G(V,E)，源节点s，我们使用BROADCASTTREE算法[10]构造广播树。在得到广播树之后，我们将广播树中的节点排序，排序的主要思想是：在树的每一层中，按节点的干扰范围中节点数的量大小对节点进行排序。即将发送消息过程中优先调度对其它节点影响较大的节点，以降低节点发送消息过程中对其他节点的影响，保证消息在传输过程免受干扰。排序的具体过程如算法1所示。令Tr(v)和Ir(v)表示节点v传输范围与干扰范围内的节点的集合。算法1首先从M中选出子节点不为空的节点，加入VM’中，然后再从第1层开始，判断每层Mi’是否为空，如果Mi’不为空，对Mi’中的节点进行比较，按节点干扰范围中其它节点数的数量从大到小的顺序，从Mi’选出节点，存入集合VM中，然后将该节点从Mi删除，循环执行，直到Mi’为空，最终得到按从大到小的顺序排列的主要节点集合VM；如果Mi’为空，再对Si’进行判断，如果Si’不为空，对Si’中的节点进行比较，按节点的干扰范围内下层非该节点子节点数量从大到小的顺序，从Si’选出节点，存入集合VS中，然后将该节点从Si’删除，直到Si’为空。再对下一层中的节点进行运算，一直循环执行到第R层结束，完成排序过程，最终得到主要节点集合VM和次要节点集合VS，并且集合中的节点按从大到小的顺序排列。算法2给出了节点广播调度过程，不同于Gandhi等人的算法[9]，当节点满足一定的限制条件时，算法2允许多个层的节点同时进行调度。算法具体步骤如下：算法用rcvTime(v)表示节点v接收消息的时间，trTime(v)表示节点v发送消息的时间，并将rcvTime(v)和trTime(v)的初始值设为0，表示节点没有接收到消息和发送过消息。消息从发送节点发送到接收节点接收到的时间忽略不计，节点在成功接收到消息后经过1个单位时间后才能转发消息。算法2从BFS树的第1层开始执行，在每层对节点进行调度，循环执行到第R层结束。算法首先判断Mi是否为空，如果Mi不为空，就按节点在VM中的顺序进行调度，对Mi中的每一个发送节点，节点发送消息的时间必须满足以下三个条件：一，节点发送消息的时间必须大于节点接收消息的时间（保证节点必须接收到消息后才能发送消息）；二，发送节点在发送消息过程中，子节点在各自的干扰范围内，不会接收到其他节点发送消息，（保证子节点正确的接收消息）；三，发送节点在发送消息过程中，其干扰范围内不能有其他节点正在接收消息，（保证发送节点在发送消息过程中，不会影响其他节点正确接收消息）。满足这三个条件的最短时间就是发送节点发送消息的时间，同时也是发送节点的子节点接收消息的时间。下面的子层也以类似的方式调度，我们用(rcvTime(v),trTime(v))表示节点接收消息与发送消息的时间，通过执行算法2，可以得到所有节点的发送时间和接收时间。与先前根据层顺序进行调度传输的算法相比，CBS算法允许下层节点早于上层节点接收和发送消息，从而降低广播延迟。图1为网络节点分布图，其中，节点的发送范围设置为1，干扰范围设置为2。图2为通过运行CBS算法,得到节点调度时间表。从图2中我们可以看出，下层的节点在不影响上层节点发送消息的条件下，可以与上层节点同时发送消息。
3.2算法分析
定理1CBS算法可以保证节点在广播调度过程中能够避免冲突，成功调度。证明假设有三个节点u,v和w，其中节点w是节点v的父节点，节点u是节点v的干扰范围内的节点，节点w与节点u都计划在时间t发送消息，如果它们同时在t时间发送消息，那么在节点v处将发生冲突，导致消息无法被正确接收。为了避免这种情况的发生，算法分别从以下两个方面采取措施，保证冲突问题不会产生。首先，当节点u准备在时间t发送消息时，节点w的子节点v在节点u的冲突范围内并且监听到此消息，因此，节点w不会选择在时间t进行调度，所以节点u与节点w不会同时发送消息，因此不会发生冲突；其次，当节点w准备在时间t向节点v发送消息时，节点v位于节点u的干扰范围之内并且在时间t监听到消息，因此节点u不会选择在时间t进行调度，所以节点u与节点w不会同时发送消息，因此也不会发生冲突。通过这种冲突避免机制，CBS算法就能够保证节点在调度过程中不会影响其他节点接收消息或受到其他节点发送消息的影响，确保成功调度。定理2在相同条件下，CBS算法完成广播调度过程发所需发生消息的数量的上界低于GPM算法。证明算法首先构建了广播树，然后从极大独立集M中选出节点作为控制节点，控制节点的父节点作为连通节点，只有这两种节点组成的连通控制集被允许发送消息[12]。因为在树中，只有源节点s没有父节点，而其他的连接节点都是M中控制节点的父节点，所以连接节点发送的消息数量等同于M中不包括源节点s以外的控制节点的数量。已知控制节点的数量为|M|，所以我们可知控制节点和连接节点发送消息的总数至多为|M|+|M|-1=2|M|-1。由于GPM算法完成广播调度过程最多需要发生3|M|条消息，所以CBS算法完成广播调度过程发所需发生消息的数量的上界低于GPM算法。定理3CBS算法允许位于BFS树中多个层的节点同时进行调度，从而提高网络信道的利用率。证明假设有三个节点u,v和w，其中节点u与节点v位于BFS树的同一层中，节点w是节点u的子节点且节点u与节点w均位于节点v的冲突范围之外。因为在CBS算法中，节点是通过监听信道来确定在何时发送和接收消息，而节点最远只能监听到其冲突范围内的消息。因此，当两个节点的距离足够远时，他们相互之间不存在干扰，假定节点u计划在t时刻向节点w发送消息，节点v计划在t+1时刻向其子节点发送消息(n>1)，因为节点v在节点w的冲突范围之外，这样节点w在确定其发送时间的过程中就不会就受到节点v的发送时间的影响，因而位于下层的节点w就可能与上层节点v同时发送消息或者早于节点v发送消息，从而证明了该定理的正确性。证明对于主要发送节点集合M，任意节点u和v都不相邻，并且这两个节点之间的距离满足d(t1,t2)＞(α+1)r。我们假设存在一个半圆形区域中，节点v位于区域的底部，其所有邻居节点位于半径为2r与(α+1)r之间的半个环形区域。由于集合M是独立集，所以其中节点的距离都大于r。
4仿真实验
在本节中，我们使用MATLAB仿真平台，对CBS算法的进行仿真实验，验证算法的性能。我们在节点传输范围取不同值的两种情况下，对CBS算法于性能表现优异的CABS算法和GPM[9]算法进行了仿真，分别得到了节点传输范围取不同值时三种算法的广播延迟的比较，并将仿真结果在图3和图4中展示。在实验中，我们令所有节点静态的随机分布在面积为600m×600m的区域内，区域内节点数量的取值范围限定为0到200，我们从节点数目为30开始，依次30、60、90、120、150、180、210、240、270、300这10个点，作为自变量来计算广播延迟。实验中，我们只设定了节点数目一个变量，其他所有条件完全相同。我们将节点的干扰范围与传输范围的比值α设定2，将CABS算法中的β的值设为0。我们使用仿真软件生成不同的网络拓扑结构对不同的算法进行仿真测试。我们分别在节点的传输范围为50m与70m的情况下，对三种算法进行了仿真实验。对于节点数量的10种不同取值，我们都随机生成10种拓扑结构，并且在每种拓扑结构下都执行算法10次，并计算最终得到三种算法在不同节点的传输范围下广播延迟的平均值。图3和图4分别给出节点的传输范围为50m与70m的情况下，三种算法的广播延迟与节点数量之间的关系。从图中我们可以看出，在节点的传输范围取值不同情况下，CBS算法的广播延迟较CABS算法和GPM算法都有明显的降低，在其他条件都相同的情况下，CBS算法可以更早的完成广播调度，降低广播延迟。
5结束语
本文研究了无线网络广播延迟问题。为了解决该问题，我们在协议干扰模型下，提出了一个基于单位圆盘图的冲突感知广播调度算法(CBS)。我们证明了，CBS算法能够保证节点在广播调度过程中不会发生冲突，成功完成广播调度。CBS算法还可以同时调度树中多个层的节点进行传输，有效地提高了网络信道的利用率。
作者：安丰洋 李光顺 吴俊华 单位：曲阜师范大学信息科学与工程学院
