Mobile agent based TDMA slot assignment algorithm for wireless sensor networks

摘要

In this paper we propose an on-line TDMA slot assignment/graph coloring algorithm for wireless sensor networks with the help of a mobile agent. It is known that graph coloring problem is NP-complete and several heuristics have been developed. Many of them are centralized algorithms and assume global knowledge of the network. We developed a mobile agent based slot assignment (MASA) algorithm in which a mobile agent moves from node to node and assigns a slot to nodes using two-hop neighborhood information. MASA is close to degree based lower bound (d + 1). It requires d + 1 number of colors or slightly more than d + 1 number of colors depending upon the topology, where d is the maximum nodal degree of the graph.