无线网络中基于最高向量权独立集的分群算法

ad hoc 网络是多跳无线网络,网络节点通信不依赖于预先架设的固定设施,这种动态网络的重要特点是寻找好的路由算法,基于群的算法是最有效和可伸缩的.然而,由于高度动态拓扑且缺少固定架构,系统重构经常是不可避免的,因此,尽可能长时间使拓扑稳定是至关重要的.极大独立集(MWIS)是一个分群算法,用于将整个网络划分为群,每个群选举一个群首.基于MWIS,提出了最高向量权独立集(HVWIS)算法.首先,每一节点被分配一个向量权,其动机是要考虑相邻节点的多个因素;其次,算法使用了模糊决策模型.这样,群首形成了一个最高向量权独立集,确定了其拓扑和其稳定性.本文证明了HVWIS 算法的正确性并分析了其时间复杂度.

A CLUSTERING ALGORITHM BASED ON HIGHEST VECTOR-WEIGHTED INDEPENDENT SET IN WIRELESS NETWORK

A mobile ad-hoc network is a multihop wireless network,where the nodes communicate with each other without any pre-deployed infrastructure.The most important problem on such dynamic networks is to find routing algorithms performing well in most cases.Cluster based algorithms are among the most effective and scalable methods. However,due to the highly dynamic topology and the absence of any fixed infrastructure in a mobile ad-hoc network, a reconfiguration of the system is often unavoidable.So,it is vital to keep the topology stable as long as possible. MWIS(maximal weighted independent set)is a clustering algorithm. It is used to partition the whole network into non-overlapping clusters, where a clusterhead is elected in each cluster.Based on MWIS, HVWIS (highest vector-weighted independent set) algorithm was proposed. First, a vector weight is assigned to each node, its motivation is to think over the neighboring multi aspects. Second, the algorithm uses a fuzzy decision model. Thus, the clusterhead that forms a HVWIS in the network determines the topology and its stability. The correctness of HVWIS algorithm is proved and its time complexity analyzed.