摘要：

针对无线自组织网络带宽利用率低的问题，在主干扰模型的基础上，提出一种基于分布式极大独立集(MIS)的无线自组织网络STDMA节点调度算法。该算法以分布式MIS算法为基础，在算法进入平衡状态时，优先让度大的节点加入MIS，再通过将其结果转化成 染色，从而完成时槽分配。该算法是完全分布式的，且时间复杂度为 。仿真结果表明，与分布式MIS算法相比，该算法收敛速度平均提高23.6%。

关键词: 无线自组织网络, 调度, 极大独立集, 分布式, 主干扰模型, 带宽

Abstract:

Aiming at the problem of low throughput utility rate in wireless ad hoc networks, a STDMA node scheduling algorithm which is based on a novel distributed Maximal Independent Set(MIS) algorithm is proposed, on the assumption of the primary interference model. Based on the distributed MIS algorithm proposed, the node whose degree is the maximal among its neighbors has a preference for joining MIS when the balanced state emerges. The output of MIS is converted into a node coloring, thus the MAC scheduling policy is correspondingly determined. The algorithm is fully distributed and its time complexity is proved to be . Simulation result shows that the convergence time has an average increase of 23.6% compared with that of MIS algorithm.

Key words: wireless ad hoc networks, scheduling, Maximal Independent Set(MIS), distributed, main interference model, band width

中图分类号: 

• TP393