Graph-based routing, broadcasting and organizing algorithms for ad-hoc networks

The development of networks of low-cost, low-power, multi-functional devices has received increasing attention over the last ten years. These devices are small in size and able to process data, communicate with each other, typically over a radio channel, and even sense. Each device particpates in a self-configuring infrastureless network connected by wireless, called ad-hoc network. Since most of the individual node in ad-hoc networks is inherently resource constrained: limited processing speed, storage capacity, and communication range and energy, it is impossible to achieve application requirements by individual device or unattached devices. A number of devices within a network have to combine as an aggregate collaborating to achieve application requirements. However, such massive devices cooperation must be achieved by the necessary organizational structures without requiring human intervention. An ad-hoc network is able to arrange itself to achieve the application requirements according to the present situations. Hence, wireless communication has to be the primary means to enable information exchange among these devices. In a wired network like the Internet, each router connects to a specific set of other routers, forming a routing graph. In ad-hoc networks, each device has a radio that provides a set of communication links to nearby devices. Multi-hop communication is expected to overcome some of the signal propagation effects experienced in long distance wireless communication. In a wide array of disciplines, an ad-hoc network can be intuitively casted into the format of a graph which is a set of vertex and a set of edges that might connect pairs of the nodes. The ad-hoc network consists of devices (vertex or nodes) and the communication links (edges) between them. Graphs are seemingly ubiquitous in ad-hoc network field. The problems of designing multi-hop routing, broadcasting and organization algorithms for ad-hoc networks have received great considerable attention. All are tightly coupled to the problem of the distinguished graphs. In this chapter, we discuss the routing, broadcasting and organization algorithms and protocols that can be formulated by three types of graph. Most of these problem are either NP-hard. Several approximate and near-approximate algorithms are proposed to solve these issues based on the combinatorial optimization and graph theory. In real mobile ad-hoc networks, there are some restricted conditions to be achieved in various applications, which will make the problems more difficult to solve. In this chapter, we attempt to give a preliminary review of the design and implementation of the heursitic or approxiamte algorithms on routing, broadcasting and organization by using the combinatorial optimization and graph theory.