基于中继节点的多跳CR Ad Hoc网络广播算法

楼巧巧 赵知劲,2

1(杭州电子科技大学通信工程学院 浙江 杭州 310018) 2(中国电子科技集团第36研究所通信系统信息控制技术国家级重点实验室 浙江 嘉兴 314001)

0 引 言

广播[1-3]是移动自组织(Ad Hoc)网络[4]中的一个重要环节，控制节点之间的信息交换。与有基础设施的广播相比，移动Ad Hoc网络的广播更容易产生广播风暴[5]和不可靠广播，具体表现为信息冗余、信道争抢和信号冲突，严重影响网络性能。因此，众多学者针对移动Ad Hoc网络广播算法展开了研究。

在传统Ad Hoc网络中，广播在单个或多个公共信道上进行，网络中所有节点可共享公共信道。在广播过程中，相邻节点只要调频到公共信道就能实现成功广播。节点通过一个时隙就可以使其所有相邻节点接收到消息，即一个时隙就是确切的单跳广播时延。其最简单的广播方式是泛洪，简单易行且有高遍及率。但在节点密集网络中，每个节点都转发会产生大量信息冗余，甚至产生广播风暴。为了抑制这一现象，陆续提出了基于概率、区域、邻居信息的广播算法以及混合型广播算法。基于概率和区域的广播算法复杂度低，但是不能保证覆盖率。在基于邻居信息的广播算法中，典型代表有多点中继广播算法[6]，节点从邻居节点中选取能够完全覆盖该节点两跳邻居的节点作为中继节点进行转发，控制冗余效果明显且覆盖率高，但中继节点选取复杂度高。混合型广播算法有MANET中基于节点邻居度的动态广播抑制算法[7],用邻居度产生转发广播的概率和时延，并根据重复广播数动态调整，有效降低广播冗余和冲突。

认知无线电(CR)技术允许次用户(SU)在时变的环境下以机会的方式利用主用户(PU)未使用的频段，以提高频谱利用率。基于CR的概念，多个节点在多个可用信道上机会性地共享许可频谱，形成认知无线电自组织网络(CR Ad Hoc)[8]。在该网络中，不同的SU拥有不同的可用信道集，不存在固定用于广播的单个或多个公共信道。CR Ad Hoc网络广播算法研究才刚刚起步。由于信道可用性不均匀且非唯一，相邻节点成功接收消息时间未知，即单跳广播确切时延未知。与传统Ad Hoc网络相比，广播时延增大，且转发节点过多同样可能产生广播风暴，因此信号冲突问题也更为严峻。文献[9-10]假设全局网络拓扑和所有SU的可用信道信息已知，文献[10]中还采用了整个网络的公共信令信道。这些算法虽然能够保证广播的成功率，但是假设都过于理想化，不适用于实际场景。文献[11-13]提出了盲信息条件下基于QoS的广播协议。网络中所有节点在可用信道子集上广播以减少广播时延，具有较高的广播成功率，但是没有考虑广播冲突问题。文献[14-15]在基于QoS广播协议的基础上提出了BRACER广播协议，该协议中含有广播冲突避免方案。但是该方案在缓解广播冲突的同时降低了广播成功率。文献[16]提出基于选择性广播信道集的低延迟广播算法(MDSBA)，具有较高广播成功率，但是节点转发率和广播冲突概率较高，网络开销较大。对此，本文提出基于中继节点选择的多跳CR Ad Hoc网络广播算法，希望在保证一定广播成功率、广播时延和广播冲突率的前提下，降低节点转发率，减少网络中的冗余信息，通过建立综合评价函数进行定量分析，从而实现一个综合性能较好的广播算法。

1 系统模型与性能指标

假设CR Ad Hoc网络的覆盖区域为10×10 km2，其内均匀分布着N个SU，节点的传输半径为R，共有M个信道。本文使用“源节点”表示第一个发送该消息的SU，使用“发送(中继)节点”表示刚收到消息并将转发该消息的SU，使用“接收节点”表示尚未收到该消息的SU，使用“目的节点”表示该消息须要传达到的SU。算法设计中使用的符号如表1所示。

表1 算法设计中使用的符号

本文中评估CR Ad Hoc网络广播算法性能的四个主要指标是：广播成功率、广播时延、广播冲突和节点转发率。

1.1 广播成功率

广播成功代表源节点成功发现目的节点。然而，每个SU的传输范围有限，目的节点不一定在源节点的传输范围内。因此，需要进行多跳广播。

以单跳为例，说明广播成功条件。发送节点按一定顺序在其可用信道上跳跃并广播消息，接收节点也按一定顺序在其可用信道上跳跃并监听。如图1所示，发送节点的可用信道广播序列Tx为{1,3,7,10,13,15,16,17,18,19,20,22,25}，接收节点的可用信道广播序列Rx为{2,4,5,6,9,11,12,13,14,19,21,23,27}。在信道19上，发送节点向接收节点成功广播消息，即单跳广播成功。

图1 广播成功举例

当接收节点第一次接收到广播消息时，以概率1作为中继节点进行转发可以保证100%的广播成功率，但会造成大量的广播时延和广播冲突。因此，为了节约网络资源，中继节点的选择尤为关键。

1.2 广播时延

广播时延是源节点将消息成功发送到目的节点所消耗的最短时间。

同样以单跳广播为例，假设广播序列中每个信道占据一个时隙。如图1所示，在k=10时隙，单跳广播成功，则该单跳时延t=10。因此，广播时延表达式为：

T=min(t(v0,vi)+∑t(vi,vj)+t(vj,vs))vi≠vj

(1)

式中：vi和vj为v0到vs的广播路径上经过的节点。选取不同路径上的最短时间作为广播时延。

1.3 广播冲突

本文考虑的广播冲突发生条件如图2所示。在中继节点v1发送广播消息给接收节点v3时，若同时有中继节点v2接收到广播消息也要发给v3，则当v1、v2存在公共可用信道时，可能造成广播冲突。

图2 广播冲突发生条件

如图3所示，v1的可用信道广播序列Tx1为{1,3,7,10,13,15,16,17,18,19,20,22,25}，v2的可用信道广播序列Tx2为{3,5,6,7,8,10,11,15,16,19,23,24,26}，v3的可用信道广播序列Rx为{2,4,5,6,9,11,12,13,14,19,21,23,27}。在k=10时隙，v3在信道19上同时接收到中继节点v1和v2的广播消息，从而造成广播冲突。

图3 广播冲突举例

1.4 综合评价函数

对广播成功率、广播时延、广播冲突和节点转发率进行综合考虑，广播成功率越大越好，广播时延、广播冲突和节点转发率都是越小越好。因此，本文利用非线性加权综合法，提出综合评价函数y如下：

(2)

式中：y越大代表广播算法的综合性能越好。

2 基于中继节点选择的广播算法

本文提出的基于中继节点选择的多跳CR Ad Hoc网络广播算法由两部分组成，分别是广播序列构建和中继节点选择与广播调度。假设每个SU已知其所有相邻两跳节点的信息，并且每次广播源节点和目的节点唯一确定。

2.1 广播序列构建

图4 广播序列构建

由于wr(vj)=max(ws(vi),vi∈N(vj))，则ws(vi)≤wr(vj)。又因为接收节点的每个可用信道都重复wr(vj)次，在这wr(vj)个连续时隙上，发送节点的每个可用信道至少出现一次。

也就是说，只要发送节点和接收节点之间存在公共信道，且发送节点的广播序列长度大于接收节点的广播序列长度，就必然存在一个时隙发送节点和接收节点跳转到同一信道上，保证广播成功。

2.2 中继节点选择与调度

本文中继节点的选择主要依赖可用信道集合大小和节点的邻居情况。

如图2所示，如果存在具有相同子节点的多个中间节点，则选择具有最小ws且最大转发概率的中间节点作为中继节点重新广播。当中继节点间存在下一跳公共节点时，对相应中继节点执行广播冲突避免方案，即将可用信道集随机左移m位，m∈[1,ws]。

根据网络中每个节点的邻居情况，节点vi的转发概率[7]为：

(3)

2.3 广播算法

在广播开始之前，每个节点利用两跳位置信息计算自己和邻居节点的ws、wr和Palter。根据上述信息，节点确定自己邻居节点中的中继节点。根据有无下一跳公共节点判定中继节点是否需要执行广播冲突避免方案，若需要，生成对应随机数。在节点广播消息前，将中继节点和对应随机数信息以及目的节点信息添加到广播包中。随后，节点构建广播序列，并按照广播序列在各信道上跳跃广播。未发送广播的节点均视为接收节点。接收节点构建广播序列，按照广播序列在各信道上跳跃监听。第一次接收到该广播消息的接收节点通过提取广播包判断自己是否为中继节点或目的节点。若是中继节点，继续进行下一跳中继节点选择与调度并将信息添加到广播包中，随后立即转发。若是目的节点，则广播结束。因此，本文算法主要步骤如下：

1) 计算ws、wr和Palter；

2) 确定源节点和目的节点；

3) 选取邻居节点中的中继节点；

4) 判断中继节点间有无下一跳公共节点，若有，为中继节点生成对应随机数；

5) 将中继节点和随机数信息以及目的节点信息添加到广播包中；

6) 发送节点构建广播序列并广播，接收节点构建广播序列并监听；

7) 接收节点接收到广播后提取广播包中的信息；

8) 判断是否为目的节点，若是，则广播成功，否则继续；

9) 判断是否为中继节点，若是，转3)，否则不转发。

2.4 广播冲突概率推导

本节分析上述算法的广播冲突概率。如图2所示，假设v1和v2是中继节点，v3是接收节点。v1、v2、v3的可用信道集的大小分别记为ws(v1)、ws(v2)、ws(v3)。将v1与v3的公共可用信道数记为x，v2与v3的公共可用信道数记为y，v1、v2、v3的公共可用信道数记为z。则v1与v3有x个公共可用信道的概率表达式为：

(4)

同理，v2与v3有y个公共可用信道的概率表达式为：

(5)

v1、v2、v3有z个公共可用信道的概率表达式为：

(6)

因此，接收节点v3在时隙k第一次出现公共信道的概率为：

(7)

在接收节点v3的每个时隙上发生广播冲突的概率为：

(8)

式中：K=ws(v3)·wr(v3)；X=min(ws(v1)，ws(v3))；Y=min(ws(v2)，ws(v3))；Z=min(x，y)。

加入随机左移，引入平均移位因子α，在接收节点v3的每个时隙上发生广播冲突的概率为：

(9)

由式(9)可知，在接收节点v3处发生广播冲突概率主要受α和可用信道集大小ws(v1)、ws(v2)、ws(v3)和wr(v3)的影响，并且可用信道越多，发生广播冲突的概率越低。为了证明上述推导和分析的正确性，以w(此时假设ws(v1)=ws(v2)=ws(v3)=wr(v3)=w)为自变量，对单个节点发生广播冲突概率进行仿真并与理论推导结果相对比，结果如图5所示。

图5 不同w下的仿真和理论广播冲突概率比较

由图5可知，单个节点的广播冲突概率的仿真值和理论值曲线基本重合，并且广播冲突率随w的增大而降低，可以证明上述推导和分析的正确性。

因此，由单个节点扩展到整个网络，发生广播冲突的平均概率为：

(10)

式中：N为网络中的节点数目。

3 算法仿真与性能分析

本节分析比较本文广播算法、分布式广播协议BRACER[15]和MDSBA[16]的性能。假设所有移动节点具有相同的广播传输半径，R=4.5 km，广播过程中节点被视为静止，节点建立并维护二跳邻居节点的信息表。对给定的节点数N和信道数M，利用MATLAB生成50个网络拓扑结构，随后对每个网络分别进行1 000次仿真，得到广播成功率、广播时延、广播冲突和节点转发率。

3.1 节点数对算法性能影响

令M=35，N=5、10、15、20、25时，三种广播算法的广播成功率、广播时延、广播冲突率、节点转发率和综合评价函数与节点数N的关系曲线分别如图6至图10所示。

图7 不同节点数下的广播时延比较

图8 不同节点数下的广播冲突概率比较

图9 不同节点数下的节点转发率比较

图10 不同节点数下的综合评价函数比较

由图6可知，随着节点数的增大，分布式广播协议的成功率快速下降，而本文广播算法的成功率基本不变，明显优于前者，但略低于MDSBA。

由图7可知，随着节点数的增大，本文广播算法和MDSBA的时延略有降低，但分布式广播协议的时延略有增大；且本文广播算法时延低于分布式广播协议，但略高于MDSBA。这是由于广播时延的大小取决于中继节点选择与调度算法，获取的广播路径越短，单跳时延越小，广播成功率越高，广播消息从源节点发送到目的节点的平均耗时越小。

由图8可知，随着节点数的增大，三种算法的冲突概率增大；本文广播算法的冲突概率比MDSBA的低，但比分布式广播协议的高。根据式(10)计算得到的本文算法的理论广播冲突概率如曲线“*”所示，与仿真结果基本一致。

由图9可知，本文广播算法的节点转发率最低，MDSBA的节点转发率最高；随着节点数的增大，三种算法的转发率先增大，后下降，本文算法增大最慢下降最快，MDSBA增大最快下降最慢。MDSBA以较大的节点转发率为代价，取得较好的广播成功率和广播时延，但网络中转发节点过多会增加网络开销，并可能导致广播风暴，大大影响网络和广播性能。

由图10可知，在信道数M一定，节点数N改变的情况下，本文广播算法的综合性能更好，并且更适用于节点密度较高的网络。

3.2 信道数对算法性能影响

令N=20，M=20、25、30、35、40时，三种广播算法的广播成功率、广播时延、广播冲突、节点转发率和综合评价函数与M的关系曲线分别如图11至图15所示。

图11 不同信道数下的广播成功率比较

图12 不同信道数下的广播时延比较

图13 不同信道数下的广播冲突概率比较

图14 不同信道数下的节点转发率比较

图15 不同信道数下的综合评价函数比较

由图11和图12可知，当信道数目改变时，本文广播算法的广播成功率和广播时延性能都优于分布式广播协议，但略差于MDSBA。随着信道数的增加，广播成功率提高，广播时延变大。广播时延变大是因为信道数增加导致广播序列长度增加。

由图13可知，三种广播算法的广播冲突概率都随信道数目的增加而略有降低。本文广播算法的冲突概率低于MDSBA1.52%，高于分布式广播协议1.37%。根据式(10)计算得到的本文算法的理论广播冲突概率也与本文算法的仿真结果基本一致。

由图14可知，本文广播算法的节点转发率始终低于分布式广播协议和MDSBA，且信道数目的增加对本文算法的影响不大，而分布式广播协议和MDSBA的节点转发率随信道数目增加而略有增大。同样，MDSBA以较大的节点转发率为代价，取得较好的广播成功率和广播时延，但网络中转发节点过多会增加网络开销，并可能导致广播风暴，大大影响网络和广播性能。

由图15可知，在节点数N一定，信道数M改变的情况下，也是本文广播算法的综合性能最好，并且信道数的变化对于综合性能影响不大。

4 结 语

本文利用中继节点选择，实现了多跳CR Ad Hoc网络的广播，本文广播算法与避免冲突的分布式广播协议相比，提高了广播成功率，降低了广播时延和节点转发率；与低延迟广播算法相比，降低了节点转发率和缓解了广播冲突。但是，由综合评价函数可知，本文广播算法的综合性能更好。