| Spatial multiplexing resources is a key feature of the wireless network, and multiplexingspatial resources can not only improve network capacity, but also cause the common channelconflicts, which are considered as a major cause of degradation of a wireless communication.The nature of the conflict is the interference, and interference modeling is a common method toquantify interference. Distributed theory has been widely used in wireless sensor networks，manywireless network problems are the classic problem of distributed algorithm design to face.Vertex coloring does have quite a few practical applications, not only in the area of wirelessnetworks where coloring is the foundation of so-called TDMA MAC protocols, but also is usedas a means to break symmetries, one of the main themes in distributed computing.The problems in distributed theory have a certain degree of difficulty, giving an illusion thata large fault exists between theory and practical application, that theory is very mature, but thepractical application of a relatively is abstract. In this thesis, we explore the classical theory ofdistributed wireless sensor networks appearing in algorithm design from the application point ofview, and discuss the relationship between some of the classic issues, such as independent setsand coloring, independent sets and dominating sets and so on.There are all kinds of interference models such as conflict graph (CG) model,general graph(GG) model, protocol interference model (PM) and physical interference model (signal tointerference plus noise, SINR), each of these models have different applicable circumstances.Through modeling of interference the SINR model can be extended so that some of the CGmodel or PM can better describe the actual situation. Finally, under the SINR model weexpanded, we design coloring algorithm using the idea of weak graph coloring. Specific researchcontents are given as follows:In the various types of interference models, the physical interference model can betterdescribe the actual situation of conflict, and2-distance conflict graph model can better limitinterference, but can only simulate two concurrent transmissions. Due to SINR model is closer tothe actual in describing the interference impact, it is more suitable to evaluate and research theability for the physical layer issues. In this thesis, we summarize the general process that theconflict graph model transformed into SINR model, and transform the σ model into the standard2-distance model by selecting the appropriate factors, and transform the PM model which centeris the sending node into σ protocol model and transform the PM model which center is thereceiving node into σ-Txprotocol mode by the formula to achieve the transformation from PMto SINR.We have various solutions for coloring problem under different interference models, and we study the problem deeply and receive a distributed (Δ+1)-coloring algorithm under SINRmodel with the weak coloring idea i.e. defective and partially proper coloring. We assume thatevery graph is colored by xcolors with every vertex’s ID different from each other. We computea MIS firstly, its time complexity isO (logn)and then receive a K-partially proper coloring inO (Δ)which K <Δ and a D-defective algorithm which repeats in O (log Δ). We use the greedystrategy and heuristic rules in the design of the weak coloring algorithm, such that nodes canchoose the right color without generating an error. At last we get a (Δ+1)-coloring intime O (log n+Δ). In this thesis, we analyze each algorithm rigorously and prove the correctnessof algorithms and their time complexity. |
PDF Full Text Request