Scalable Routing Modeling for Wireless Ad Hoc Networks by Using Polychromatic Sets

摘要

Graph theory is a traditional mathematical method to analyze computer networks, including intelligent wireless networks, such as ad hoc networks, sensor networks, and wireless mesh networks. Because of the variety of the network nodes and wireless links, conventional graph theory and set theory used to describe the element of the network (node and link) are not suitable to model the modern complex wireless networks. Recent research in weighted graph and random graph theories that place a weight on the links and a probability to decide the existence of the link or not is a further step to model the wireless network in a near real-life scenario. However, it lacks the ability to describe the properties of the network node. In this paper, a new mathematical tool, polychromatic sets (PS-sets), is introduced in modeling the complex wireless networks. PS-sets have the ability to describe the property of each element, which we believe will be a perfect tool to describe the network nodes and links of wireless networks. This paper demonstrates a scalable network modeling using PS-sets theory and a routing scheme based on this model. Evaluation results show that it is simple and scalable, and its performance is superior to other conventional routing schemes. The PS-sets theory could become a new tool in studying modern complex wireless networks.