Title: A Survey of Design Issues in Self Organizing Wireless Networks

Author: Yasir Drabu
email: ydrabu@cs.kent.edu, homepage: http://www.cs.kent.edu/~ydrabu

Prepared for Prof. Javed I. Khan
Department of Computer Science, Kent State University
Date: November 2001

Abstract: Since the inception of communication, self-organizing wireless networks has been an intellectual fantasy of communication researchers. Self organizing networks are based on sophisticated protocols that allow diverse computing devices to establish a communication system without human intervention. This survey investigates these networks and tries to present the various issues and challenges they pose. Further the contributions made towards solving these problems are also outlined.

Keywords: self-organizing networks, ad hoc wireless networks, dynamic reorganizing networks.

Other Survey's on Internetwork-based Applications
Back to Javed I. Khan's Home Page

Introduction

With miniaturization of computing elements we have seen many mobile devices appear in the market. In the present day scenario an average user has a multitude of devices ranging for PDAs to laptops. To make communication between these devices as well as other users for any kind of collaboration becomes very cumbersome and to some extend counter productive. With the idea of simplifying the networking of diverse computing devices this survey investigates the concept of self organizing networks. It is important to observe that self organizing network are more than just smart wireless cabling technologies like Bluetooth in that they are actual networks with routing elements. They can be used as fully functional autonomous networks (e.g. Tactical Network) or as an extension to the current infrastructure network by extending its reach.

First we understand what self organizing networks are, then in the next section we discuss the key issues and challenges posed in the development of these networks.

What are self-organizing networks?

A self organizing network is an ad hoc network architecture that can be rapidly deployed without relying on a pre-existing fixed network infrastructure with minimal or no human administration. They are also know as zero-config or Reconfigurable Wireless Networks (RWN) The nodes in this type of network can join and leave the network frequently, often without any prior warning and possibly without disruption of other nodes’ communication. The nodes of this type of network have assumed to be highly mobile and thus can rapidly change the node constellation and the presence of absence of links.

Some typical self organizing networks are:

Collaboration in a business or educational environment, to share ideas, plans and information among diverse electronic devices.
Military operation, to create network in hostile locations.
Sensory networks – for communication between intelligent sensors to exchange information.

These are just a few examples; once realized this type of extreme networking based applications can have far reaching implications.

Problems and Proposed Solutions

There are lot of technical issues involved in the creation of an ad hoc network and then making it self organizing. Configuration, discovery, routing, MAC layer adaptation, security are some of the key issues. Further power and processing capabilities are scarce resources in mobile device, thus making protocols design even more complex.

In this section we discuss these unique challenges associated with a self organizing network.

Configuration

Most of today’s networks are relatively static. They involve a large management cost to be setup and maintained. Today to setup connection to the Internet we need to have an IP address assigned by a network administrator and some manual entries in the DNS server. Further if the node moves to a new location this configuration has to be changes. This technique though workable, is highly inefficient for a frequently changing network. Further the problem is complicated by a multitude of devices and diverse platforms. Here the key paradigm shift with respect to self organizing networks is that these networks do not need any human intervention to lay down the address plan.

The best automatic configuration that can simplify some of the above issues is the use of Dynamic Host Configuration Protocol (DHCP), which assigns IP addresses to hosts dynamically from a pool of addresses. This technique though becomes ineffective when it come to self organizing networks as each node is not expected to have access to a central DHCP server. Thus a technique to configure the network has to be developed that can be effective and efficient in this scenario.

One way to configure the nodes to give each node an international name using the International Naming Scheme as suggested in [8]. In this scheme the name of the network element describes its attributes like location (which is hierarchal), services it provides, and owner of the node, a unique id, and access privileges. Thus just by acquiring the name of a networking element, all this information becomes available. This has the dual advantage of providing service discovery, but at that same time can be too much data overhead for just knowing the name of a computing device.

Another method suggested by [2] is to have a permanent End-System Unique Identifier (EUI) and then have a Location Dependent Address (LDA). The LDA is a triplet formed by giving the node its latitude, longitude and altitude. How these parameters are obtained is discussed in the next section.

Discovery

Discovery is a very important aspect of making an ad hoc network self organizing. Discovery deals with two issues –

The discovery of the node itself within the network.
The discovery of the services available to the node once it has placed itself in the network.

The simplest way a node can discover itself is by using a Global Positioning System (GPS). The GPS can provide the node with its location and then it can start looking for nodes in its “zone”. If the GPS service is not available for reasons like weak signal, signal jamming, etc, then we can use a Self Positioning Algorithms (SPA) [2]. This technique uses the distance between nodes to form a Network Coordinate System, which is used to define the location of the node.

Once a node has discovered the network, the next natural aspect is for it to look for services provided to it by the network it is connected to. This aspect of service discovery was realized and lot of research is going on to develop and effective protocol. The protocols being developed are discussed and compared in [7]. Some of the vendors that are developing service location protocols are:

Microsoft is developing Universal Plug n Play (UPnP)
Sun Microsystems is pushing Jini which is java based
Salutation being developed by a group of companies (Fuji, Konica, IBM etc).
Bluetooth Service Discovery Protocol.

The IETF is developing the Service Location Protocol, SLP. This protocol is intended to be vendor independent (version 2 is currently available). This protocol consists of three main components, the User Agent (UA) – which looks of a service on behalf of the user, the Service Agent (SA) – which advertises its services and the Directory agent – which collects information from SA and provides it to the UA.

These service discovery protocols need to be modified to better suit self organizing networks.

Routing

Routing is one of fundamental operations of a network. Thus there are a lot of routing protocols proposed to work with ad hoc networks. Link state and distance vector are two common approaches to solve the routing problem. In the link state each router has a good picture of the network topology and thus does not prove to be a good approach for self organizing networks.

Broadly speaking routing protocols are classified into two –

Proactive: These types of protocols constantly evaluate the routes within the network so that when a packet needs to be forwarded the route id already known. E.g. Open Shortest Path First (OSPF), Wireless Routing Protocol (WRP), Destination-Sequenced Distance-Vector (DSDV).
Reactive: This type of protocols determines the route on demand. E.g. Temporally-Ordered Routing Algorithm (TORA), Ad hoc On Demand Distance Vector (AODV) and Dynamic Source Routing (DSR).

Proactive protocols have a low delay as the route is already known, but they consume too much bandwidth to propagate the routing information. Reactive protocols use bandwidth efficiently but have a high delay and thus are not suitable for real time traffic.

Ideally the routing protocol for a self organizing network should be a combination of both the scheme, like the Zone Routing Protocol. ZRP limits the scope of the proactive procedure to the node’s local neighborhood, but the search throughout the network, although global, is done by querying only a subset of the network nodes. The protocol is discussed in [4].

Cooperation Incentive

Self organizing network are highly cooperative, since each node of the network acts as an autonomous network elements and provides all the services themselves. Since providing service to the network does not provide any direct advantage to the users of such a node, they may just consume services and not provide any. So mechanisms are required to encourage end-users to let their node act as a relay, and keep their terminal turned on and not tamper with them. Further such a mechanism should also discourage end-users from overloading the network, in particular limit the number of long distance communications.

This incentive can be provided by using virtual currency, called the nuglet [2]. This can be implented as two models models :

Packet Purse Model in which the payment by the sender
Packet Trade Model in which the payment by the receiver.

In each of these models the integrity and fairness of the nuglet has to be maintained.

Mojo Nation (http://www.mojonation.net) has implemented such a mechanism on the Internet, for peer to peer file sharing providing an incentive for peers to remain online and share digital media.

Security

Security issues like legitimacy of the users, confidentiality and integrity of information in self organizing networks are similar to that of conventional networks. But this type of network has more complex issues as listed below:

The medium used it wireless, thus it becomes easier to eavesdrop.
These networks do not have a centralized monitoring or management point.
The network configuration changes dynamically owing to the dynamic nature of the network.
Mobile devices have a limited processing capacity and battery life, so any kind of solution has to take these factors into account.
Mobile devices can be captured unlike fixed

To secure a self organizing network, we consider the following attributes: availability, confidentiality, integrity, authentication, and non-repudiation.

To ensure that the message delivered has not been modified a technique called diversity coding can be used. The basic idea is to transmit redundant information through additional routes for error detection and correction without message retransmission. Thus even if one route is compromised, the other routes can be used to get the correct information across.

To authenticate a user [8] proposes a technique called threshold cryptography which takes advantage of the link redundancy of these types of network. It discusses the how distribution of trust can make Certification Authorities more robust and resistant to attack.

Further since each node itself it a router or a relay, it should protect its routing information. As we have discussed above that routing protocols for ad hoc networks must handle outdated routing information to accommodate the dynamically changing topology. False routing information generated by compromised nodes could, to some extent, be considered outdated information. As long as there are sufficiently many correct nodes, the routing protocol should be able to find routes that go around these compromised nodes. Such capability of the routing protocols usually relies on the inherent redundancies in such networks. If routing protocols can discover multiple routes, nodes can switch to an alternative route when the primary route appears to have failed.

Summary

The design of self organizing networks as we have seen involves the resolution of lot of complex issues. In this survey we have discuss some of these issues ranging from configuration to security. We have also outlined some of the possible approaches that can be adopted to resolve them. But the potential benefits like ease of use, robustness and overall efficiency of such networks warrant further research till they can be commercially realizable.

References

Research Papers

1. J.P. Hubaux, Th. Gross, J. Y. Le Boudec, M. Vetterli, "Towards self-organized mobile ad hoc networks: the Terminodes project",IEEE Communications Magazine, January 2001.

2. L. Blazevic,L. Buttyan S. Capkun, S. Giordano, J. P. Hubaux, J. Y. Le Boudec,"Self-Organization in Mobile Ad-Hoc Networks: the Approach of Terminodes ", IEEE Communications Magazine, June 2001

3. David B. Johnson and David A. Maltz. Protocols for Adaptive Wireless and Mobile Networking. IEEE Personal Communications, 3(1):34-42, February 1996.

4. J.Haas and M. R. Pearlman, "The Zone Routing Protocol (ZRP) for Ad Hoc Networks," IETF Internet Draft, June 1999.

5. “DEAPspace – Transient ad hoc networking of pervasive devices” - Computer Networks Volume: 35, Issue: 4, March, 2001, pp. 411-428

6. “Distributed Services for Information Dissemination in Self-Organizing Sensor Networks," by Alvin Lim, Journal of Franklin Institute, Volume: 338, Issue: 6, September, 2001, pp. 707-727

7. A Comparison Of Service Discovery Protocols And Implementation Of The Service Location Protocol , In Proceedings EUNICE 2000, Sixth EUNICE Open European Summer School, Twente, Netherlands, September 2000

8. W. Adjie-Winoto, E. Schwartz, and H. Balakrishnan , ”An architecture for intentional name resolution and application-level routing” , Proc. 17th SOSP, Kiawah Island, SC, Feb 2000.

9. L.Zhou and Z. J. Haas. "Securing ad hoc networks," IEEE Networks, 3(6):24—30 , 1999.

Research Groups

1.Terminode Project (MISC) 2.Monarch Project (CMU)

Scope

1.Key words: Self configuration, dynamic configuration wireless/mobile networks.
2. Self organizing, dynamic reorganizing wireless/mobile networks.

The Digital Libraries used for locating the documents where:
     1.The Research Index
     2.Ohio Link
     3.ACM Search Portal