基于最大完全子图与最小树形图的无线定向网络广播算法

现有关于无线定向网络广播的研究主要集中于如何选择中继节点或计算转发概率以提升分组递交率，减少广播冗余，但未对中继节点选择及波束指向计算开展联合设计，导致源节点及中继节点在广播过程中存在冗余指向，增加了消息转发次数。为提升无线定向网络广播效率，提出一种基于最大完全子图与最小树形图的无线定向网络广播算法(maximum complete subgraph and minimum arborescence based directional broadcasting algorithm, MCSMA)。算法首先利用最大完全子图理论计算源节点或中继节点波束指向，使单个波束指向覆盖的邻居节点数量最多，然后利用最小树形图理论选择中继节点，使中继节点使用少量波束覆盖全网所有节点，降低广播过程中的消息转发次数。仿真表明，所提算法可有效减少广播过程中源节点和中继节点的波束指向次数，提升定向广播效率。

Maximum Complete Subgraph and Minimum Arborescence based Broadcasting Algorithm in Directional Wireless Networks

The majority researches of directional broadcasting in wireless networks put effort to optimize packet delivery ratio and reduce transmission redundancy through relay selection and forwarding probability deduction. However, relay selection and beam pointing calculation were not considered jointly, which may cause inferior beam pointing scheme and increase message relay times. To improve the efficiency of directional broadcasting, a Maximum Complete Subgraph and Minimum Arborescence (MCSMA) based directional broadcasting algorithm is proposed. The maximum complete subgraph theory is used to calculate the beam direction of the source or relay node to cover the maximum number of neighbor nodes. The minimum arborescence theory is used to select relays to cover all nodes with fewer beams, which can decrease the message relay times. Simulation shows the proposed algorithm can effectively reduce the required beams of the source node and all relays during the broadcasting process, and improve the efficiency of directional broadcasting.