A topology discovery algorithm for sensor network using smart antennas
Introduction
A sensor network consists of a collection of sensors distributed over some area that form Ad Hoc network. Each sensor node is equipped with some limited memory and processing capabilities, multiple sensing modalities and communication capabilities. The topology information of the sensor network is an important aspect for the supervisor, for example, the network supervisor of a sensor network will need the topology information to know the areas that are not monitored by the sensor nodes, the nodes that run out batteries and the nodes that carried out away by wind or get eaten by wild boar. These changes are discovered by topology discovery algorithms. Topology discovery algorithms will help in maintaining connectivity and conserving the rare resources, such as power and bandwidth of the network.
An omnidirectional antenna is an antenna that transmits and receives equally in all directions. The natural broadcasting characteristic of an omnidirectional antenna limits both the medium use efficiency and the bandwidth reutilization efficiency. For these reasons, directional antennas were designed to fix the radio propagation directions. However, directional antennas do not eliminate the most significant disadvantage of omnidirectional antennas, i.e., interferences. The next step in designing antennas therefore has to be the deployment of antennas that can minimize these interferences. These antennas are called smart antennas. A smart antenna is an antenna composed of many antenna elements that are arranged in a linear, circular or planar configuration. The number of these antenna elements is a characteristic of the smart antenna. Their role is to increase the radio signal quality by optimizing radio propagation and to increase medium capacity by increasing bandwidth reutilization. Their smartness resides in the combination of the signals received within the smart antenna elements. This combination is ensured by the Digital Signal Processing (DSP). So we consider the use of smart antenna systems in order to achieve reliable and efficient data delivery in wireless sensor networks.
In this paper a topology database called FDB is constructed by collecting topology link information from all nodes where link information is defined and identified by the IDs of two nodes that it connects. This topology database is able to answer queries, for example, the query of the existence of a path to a certain destination.
The rest of this paper is organized as follows. Section 2; describe the previous studies on the topology discovery problem. The description of relevant terms are introduced in Section 3. In Section 4, we introduce the algorithm to carry out topology discovery based on smart antennas. The simulation of our algorithm is presented in Section 5. In Section 6, we compute the complexity of our algorithm. In Section 7, we conclude this work.
Section snippets
Related research
The growths in hardware and wireless network technologies have created low cost, low power, multi functional miniature sensor devices. These devices make up hundreds or thousands of Ad Hoc tiny sensor nodes spread across a geographical area. These sensor nodes collaborate among themselves to establish a sensor network. Sensor networks promise to revolutionize sensing in a wide range of application domains. Examples of such applications include: fine grain monitoring of habitats with a view to
Description of relevant terms
We assume that we work with sensor nodes that are randomly distributed and they are having no knowledge about their neighbor nodes. Also we consider that each node is distinguishable by unique identifier such as MAC address, and each is equipped with smart antenna. Our goal is to design an algorithm that determines the topology of the network. To accomplish this goal, we choose to drive the network topology by directing topology request message to any sensor node in the network, and then obtain
Algorithm outlines
After the deployment of the sensor nodes over the area, all nodes are in the idle state, i.e., they have no knowledge about their around neighbors. The FDB of idle node contains only its entry, i.e., its ID, Location, assigns its level to zero also it has no DCN and its FDB status is set to be incomplete.
In our work the sensor node becomes active node in the following two cases:
- •
Case 1: when the node receives topology request message from the user;
- •
Case 2: when the node receives message from its
The simulation results
In this section we analyze the performance of our proposed algorithm. Our topology discovery algorithm is evaluated by comparing the percentage of discovered nodes in the network to the actual number of sensor nodes.
We use the same antenna model as discussed in [25]. In this model a modified MAC is proposed where an adaptive beam forming technique is used to steer the beam pattern of the antenna array with two or four antenna elements, also a mixed approach is used where both the transmitter
Complexity analysis
In this section we present analysis of the network load. We are mainly considering the energy expended in communication (transmission and reception of packets) as the network load. This is because it is far greater than the energy consumed by the processor in computation. There are two main factors contributing to the network load.
- •
The number of packets exchanged in node vicinity.
- •
The traffic load on the intermediate nodes for routing the response back to the coordinator.
In our algorithm every
Conclusion
In this paper, we have described a topology discovery algorithm for wireless sensor networks. The algorithm consists of two phases, the first phase discovers the around nodes and in that phase the smart antenna algorithm built the desired beam pattern that made all communication between the sensor nodes occurred in a smart manner. The second phase aggregates the complete link information of sensor network in a database that can be used for any kind of applications. We worked with sensor nodes
Dr. Ahmed M. Khedr received his B.Sc degree in Mathematics in June 1989 and the M.Sc degree in the area of optimal control in July 1995 both from Zagazig University, Egypt. In March 2003 he received his Ph.D. degree in computer science from University of Cincinnati, Ohio, USA. From March 2003 to January 2004, he was a research Assistant Professor at ECECS Department University of Cincinnati, USA. From January 2004 till now he is working as Assistant Professor at Department of Mathematics,
References (30)
- Adnan Ahmed, Behrouz Homayoun Far, Topology discovery for network fault management using mobile agents in ad hoc...
- et al.
Dynamic source routing in ad hoc wireless network
- Ranveer Chanadra, Christ Fetzer, H. Karin, Adaptive topology discovery in hybrid wireless networks, in: Proceedings of...
- et al.
ANMP: Adhoc network management protocol
IEEE Journal on Selected Areas in Communications
(1999) - A. Cerpa, J. Elson, D. Estrin, L. Girod, M. Hamilton, J. Zhao, Habitat monitoring: an application-driver for wireless...
- Budhaditya Deb, S. Bhatnagar, B. Nath, A topology discovery algorithm for sensor networks with applications to network...
- Tassos Dimitriou, Antoins Kalis, Efficient delivery of information in sensor networks using smart antennas, Athens...
- A. Downey, Using pathchar to estimate internet link characteristic, in: Proceedings of the SIGCOMM 1999, Cambridge, MA,...
- C.E. Perkins, E.M. Royer, Ad hoc on-demand distance vector routing, in; Proceedings of the 2nd IEEE Workshop on Mobile...
- D. Estrin, R. Govindan, J. Heidemann, S. Kumar, Next century challenges: scalable coordination in sensor networks, in:...
Directed diffusion for wireless sensor networking
ACM/IEEE Transaction on Networking
Cited by (0)
Dr. Ahmed M. Khedr received his B.Sc degree in Mathematics in June 1989 and the M.Sc degree in the area of optimal control in July 1995 both from Zagazig University, Egypt. In March 2003 he received his Ph.D. degree in computer science from University of Cincinnati, Ohio, USA. From March 2003 to January 2004, he was a research Assistant Professor at ECECS Department University of Cincinnati, USA. From January 2004 till now he is working as Assistant Professor at Department of Mathematics, Faculty of Science, Zagazig University, Egypt. He has coauthored 20 works in journals and conferences relating with optimal control, distributed databases, sensor network and decomposable algorithms.