Wireless sensor networks are normally characterized by resource challenged nodes. Since communication costs the most in terms of energy in these networks, minimizing this overhead is important. We consider minimum length node scheduling in regular multi-hop wireless sensor networks. We present collision-free decentralized scheduling algorithms based on TDMA with spatial reuse that do not use message passing, this saving communication overhead. We develop the algorithms using graph-based k-hop interference model and show that the schedule complexity in regular networks is independent of the number of nodes and varies quadratically with k which is typically a very small number. We follow it by characterizing feasibility regions in the SINR parameter space where the constant complexity continues to hold while simultaneously satisfying the SINR criteria. Using simulation, we evaluate the efficiency of our solution on random network deployments.
McDiarmid and Reed showed that the chromatic number of general hexagonal graphs is bounded by 4 3 times the clique number @cite_13 . This result suggests that our hexagonal scheduling algorithm, the complexity of which is also bounded by 4 3 times the clique number, might indeed be very close to optimal. A 4 3-approximate distributed channel assignment algorithm that uses several rounds of message passing is presented in @cite_18 .
@cite_18 @cite_13
2074982499 2082873662
A cellular network is generally modeled as a subgraph of the triangular lattice. In the static frequency assignment problem, each vertex of the graph is a base station in the network, and has associated with it an integer weight that represents the number of calls that must be served at the vertex by assigning distinct frequencies per call. The edges of the graph model interference constraints for frequencies assigned to neighboring stations. The static frequency assignment problem can be abstracted as a graph multicoloring problem. We describe an efficient algorithm to multicolor optimally any weighted even or odd length cycle representing a cellular network. This result is further extended to any outerplanar graph. For the problem of multicoloring an arbitrary connected subgraph of the triangular lattice, we demonstrate an approximation algorithm which guarantees that no more than 4 3 times the minimum number of required colors are used. Further, we show that this algorithm can be implemented in a distributed manner, where each station needs to have knowledge only of the weights at a small neighborhood. In cellular telephone networks, sets of radio channels (colors) must be assigned to transmitters (vertices) while avoiding interterence. Often, the transmitters are laid out like vertices of a triangular lattice in the plane. We investigated the corresponding weighted coloring problem of assigning sets of colors to vertices of the triangular lattice so that the sets of colors assigned to adjacent vertices are disjoint. We present a hardness result and an efficient algorithm yielding an approximate solution.