Elsevier

Computer Communications

Volume 29, Issue 12, 4 August 2006, Pages 2261-2268
Computer Communications

A topology discovery algorithm for sensor network using smart antennas

https://doi.org/10.1016/j.comcom.2006.03.002Get rights and content

Abstract

Wireless sensor networks have recently attracted lots of research effort due to its wide range of applications. In this paper, we focus on sensor network topology discovery problem, where accurate network topology information is important for both network management and application performance prediction. We present on demand algorithm to discover the sensor network topology. The node that receives our topology request collects all topology related information from each node in the network and constructs link information databases.

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...
  • D.B. Johnson 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...
  • W. Chen 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:...
  • L. Fang, W. Du, P. Ning, A beacon-less location discovery scheme for wireless sensor networks, in: IEEE Infocom,...
  • Wendi Heinzelman, J. Kulik, H. Balakrishnan, Adaptive protocols for information dissmintion in wireless sensor...
  • Mark Hedley, Mark Johnson, Chris Lewis, D. Carpenter, H. Lovatt, D. Price, Smart sensor network for space vehicle...
  • C. Intanagonwiwat et al.

    Directed diffusion for wireless sensor networking

    ACM/IEEE Transaction on Networking

    (2002)
  • C. Intanagonwiwat, R. Govindan, D. Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor...
  • 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.

    View full text