| Wireless ad hoc network is a communication network technology that has been developed for more than 50 years.It is based on wireless communication technology.Compared with traditional communication,it has many characteristics such as no center,fast networking,strong anti-destruction ability,etc.It expands application scenarios that cannot be popularized by traditional networks,and provides a guarantee for free communication anytime,anywhere.It has achieved good development in many fields such as military communication and wireless sensor network by virtue of its special networking method.With the development of "5G" communication and the emergence of concepts such as "Internet of Everything",the realization of many technologies and scenarios require the support of wireless ad hoc networks,so the research on wireless ad hoc networks is still a very meaningful work.By comparing the wireless ad hoc network with the traditional network,this thesis makes it clear that the MAC protocol design of the wireless ad hoc network is one of the important research objects.In the communication network based on TDMA,one of the most important contents is the research of time slot scheduling algorithm.The main works are as follows:(1)Analyzing the time slot scheduling algorithm based on link or node scheduling,it will have different degrees of influence on broadcast type and unicast type of services and network throughput.In order to obtain greater network throughput,this thesis adopts linkbased time slot scheduling to improve network throughput by increasing the degree of time slot reuse.Aiming at the problem that link interference needs to be avoided when the TDMA wireless ad hoc network is used for resource allocation,the original directed network model graph is converted into an undirected conflict graph.It intuitively depicts the interference relationship between links,simplifies the problem of conflict avoidance in slot scheduling,and turns the problem into a mathematical graph coloring problem.(2)Researching the waste of time slot resources when using the graph coloring algorithm for time slot scheduling in the traditional method.By reconstructing the mathematical model and solving it,the degree of time slot reuse is further improved.In the research,it is found that the restriction that each link can only be dyed once and the absolute fairness of relaxed link scheduling can be relaxed to improve the degree of time slot reuse where the graph coloring algorithm link is scheduled only once and reaches the optimum.A new constraint is constructed,and the problem of graph coloring is transformed into a search problem of optimal combination by completing the conflict graph into a complete graph.Aiming at this problem,a centralized algorithm is designed to search downward from the maximum number of combination members,so that the algorithm can terminate in time after obtaining the optimal combination,and ensure that the number of members in each combination is as large as possible.It means that as many links as possible are scheduled in each time slot.Through the simulation comparison on the random graph,it is verified that the algorithm has a significant improvement effect on the degree of time slot reuse.(3)For the distributed time slot scheduling problem with large network scale,this thesis further improves the degree of time slot reuse by improving the distributed MIS algorithm proposed by Schneider and Wattenhofer.In a distributed scenario,each node can only obtain the local network conflict graph and can only decide the time slot for sending and receiving on the link related to itself.Therefore,multiple rounds of negotiation between nodes are required to converge and determine the final time slot allocation result.In the centralized graph coloring algorithm,the degree of nodes is a very important factor.Based on the distributed SW-MIS algorithm,the link interference number is introduced as the link weight,and the processing flow is simplified when the weights are equal.Multiple scheduling of links is achieved by adding repeatable states to links and adding selection links for repeating links after each round of MIS calculation.In order to ensure the consistency of each round of MIS calculation process in the whole network,the attribute of algorithm round is added to each node to ensure that each weight comparison is performed in the same round.Finally,through simulation,it is verified that the algorithm can improve the degree of time slot reuse. |
