Design And Analysis Of Virtual Backbone Network Construction Algorithm In Unstructured Network

Compared with traditional wired networks,wireless networks are widely used in search,rescue,military,agricultural and industrial applications owing to the rapid deployment,flexibility,scalability,widespread coverage and strong anti-destructiveness.However,due to lacking infrastructure and inherent flat structure of the wireless network,network management and other issues are highlighted.It is necessary to construct a virtual backbone network(VBN)to serve as the basis of the network for improving resource utilization and optimize the network performance.In mathematics,the construction of the VBN is equivalent to solve the minimum connected dominating set(MCDS)of the graph.Therefore,numerous works have been done on constructuing MCDS in wireless network.However,the communication model used in the existing works generally assumes that the nodes have sufficient network knowledge,strong communication capability and does not consider the collision problem caused by sending messages between nodes.This is relatively easy to design a simple and effective CDS algorithm,but it is difficult to apply in practice.In addition,in the cognitive radio networks(CRNs),due to the random activities of primary users(PUs),cognitive users(CUs)have to access the spectrum(channel)authorized to the PUs opportunistically,causing discontinuity of the channel.Therefore,the CDS with the longest lifetime is significantly more popular than with smaller size in CRNs.However,in the existing works,it is intended to design a MCDS algorithm with smaller size.Aiming at these problems,in this paper,the distributed CDS algorithms have been proposed in the anonymous wireless networks and the CRNs,respectively.The contents and contributions are as follows:In the anonymous wireless network,the network is modeled as a unit disk graph and the MDS and MCDS algorithms are proposed respectively.The collision problem between sending nodes is considered in this paper,which is different with the existing algorithms.By setting the jitter,the sending time of the nodes is made,and the carrier sensing capability of the nodes is used to reduce the collision problem.For the design of the algorithms,counting one-hop neighbor(COHN)algorithm with the time complexity of the O(log N)is proposed firstly,where N is the upper size of the network.Subsequently,the degree of the nodes is converted into the binary string of the ?log N?? ?,which is transmitted bit by bit from high to low.And by the way,obtain the nodes with the local maximum degree as the leader,and get a DS.Moreover,we propose a layer-based L-MCDS algorithm for the construction of the CDS based on theCOHN algorithm.A source node(generally a cluster head or a sink node)is selected as the 0th layer.Based on this layer,iterate layer by layer and divide the network into different layers.The leader nodes are selected on each layer after the layering is completed,and the union of all the leader nodes is the CDS.In the CRNs,we propose a CDS construction algorithm with maximum lifetime based on the deletion strategy.The algorithm is divided into four phases: first,the link with less lifetime is deleted in the network;then,the number of connected components is computed by setting the flag variable;subsequently,the link with the largest lifetime selected and joined to the network,so that the network is connected;Finally,by setting rules,the redundant nodes in the network are deleted under guaranteeing that the CDS is valid,so as to obtain a CDS with the small size.The simulation results show that the proposed algorithm has a better lifetime than the traditional CDS design algorithms(WanPJCDS,GuhaCDS,WuLiCDS and StojmenovicCDS).