Abstract: A Mobile Ad-hoc NETwork (MANET) is a set of wireless mobile devices forming a temporary network without the aid of any fixed infrastructure or central administration. These devices are characterized by the following features: mobility, heterogeneity, limited battery powers. In such an environment, the MANET offers opportunities for sharing services and resources made available by member nodes. All nodes are equal and communicate over radio transmission, but each one has a limited and partial capacity of services and resources. To be effective, each member node needs a local and self-organized mechanism to discover the whole network architecture (topology discovery) and consequently, to use and to take advantage of the different services offered by the other member nodes. In this study, we propose a new system for the topology discovery which is inspired from a bees’ society. It is based on swarm intelligence emerged from the communication between bees and it is reactive system. The main idea is to allow each node discovers its own view of the whole network topology (global vision) from its particular knowledge (local vision) without any central control and in adaptation with the MANET features. We proceed with a set of simulation experiments using the Netlogo simulator with the aim of showing the satisfactory results of this system.
INTRODUCTION
Since a few years research interest in MANETs has been growing (DiCaro et al., 2004) and especially the design on self-organization and adaptive techniques of the MANETs problems. Consequently, many researchers study the MANETs in point of view a complex system. In other words, they consider the MANETs as complex systems because they verify the complex systems structures and functions. They can be regarded as a collection of information gathering entities which respond to the environment and to each other; segregate information from random noise; compress regularities into a model; modify their internal characteristics (adaptation) to improve their performance of the desired tasks. Typically, they display emergent (self-organized) behavior and give rise to unexpected consequences (Pines, 1998).
Mobile ad-hoc networks are networks in which all nodes (hosts) are mobile and communicate with each other via wireless connections. Nodes can join or leave the network at any time. There is no fixed infrastructure deployed in MANETs. All nodes are equal and there is no centralized administration, control or overview (Royer and Toh, 1999). In other words, MANETs are networks that do not have a fixed infrastructure: this is an emerging but highly useful and promising type of network communication method (Ashwini and Fujinoki, 2005).
Contrary to the wire networks or the cellular networks, the MANETs users will want to communicate in delicate situations in which it is impossible to set up fixed wired infrastructure. For example, a class of students may need to interact during a lecture, friends or business associates may run into each other in an airport terminal and wish to share files, or a group of emergency rescue workers may need to be quickly deployed after an earthquake or flood. In such situations, a collection of mobile hosts with wireless network interfaces may form a temporary network without the aid of any established infrastructure or centralized administration (Johnson and Maltz, 1996). Thus, a meeting of business people scattered over large area having no fixed infrastructure will be best supported by this kind of network. This type of network can be described as network of mobile devices that is created or destroyed as needed (Ashwini and Fujinoki, 2005).
In this research project, we study the topology discovery problem in the MANETs. In other words, we search to gathering for each node the information related to the network architecture: nodes, links and their organization. This information can be used to control transmission power, avoid congestion, compute routing tables, discover resources and to gather data (Chandra et al., 2002). Therefore, our problematic is: In a mobile ad-hoc network, how each node (host) can discover the topology of the whole network in an intelligent way and without any central control, starting from local information?
Each node is in interaction with the nodes which are in its covering zone and in interaction with its environment which is described as shared and dynamic. This discovery must be updated in real time in order to overcome the failures which can appear at any time in the network. This is the adaptive aspect called self-organizational aspect. The complexity of this problem is due to the absence of a central control which refers to lack of fixed and wired infrastructure.
In this way, we propose a new system that we call the bees system which is inspired from the bees’ society. Our system has a objective to perform the topology discovery. This system can be considered as a system for the resolution of other problems in other fields such as the optimization. We qualify the bees’ system as original meta-heuristics method (Bitam and Batouche, 2006).
Bees’ system is based on the remarkable interaction between bees that aims to construct the best bees network (the information circulation between bees). In the organization of the beehive, the methodical search for nectar and pollen of the flowers by the workers requires a mode of communication between them. When a worker bee locates the food source, it communicates the site of its discovery with the rest in the beehive by a series of codified movements called dance of the bees. This dance is carried out compared with the vertical ray of the beehive.
If the located place is close the bee carries out a round dance, by changing direction more or less frequently. The other worker bees use the key of their antennas to identify the odor of pollen and leave at once to search for the detected flower.
If the localization is more distant a different movement is carried out. It is called the wagging dance. The bee describes two half-circles successively while passing by a straight line where it agitates its abdomen and emits a buzz with its wings. The rectilinear journey time and the frequency of wriggling indicate the distance to the source. To proceed these rules, each bee is able to know the new topology directly or indirectly without any central control.
In the MANET environment, we apply a projection. We regard the bees as nodes, the two types of dances like two types of signals and the bee discovery as new node discovery. We devote a whole paragraph to explain our system.
MOBILE Ad-hoc NETWORK
We can distinguish between two types of dynamic networks. Each one has its own properties and its own constraints of topology that may be and typically are, realized. We speak about the overlay networks and the wireless ad-hoc networks.
In overlay networks, every node can send a message to any other node, provided that the target network address is known. That is, a node can actually send a message only if it knows the address of the target node. This means that the view of a node does not and cannot contain the entire network. Therefore the topology will not be the complete graph, but a graph in which nodes have a limited degree, that is, they have a limited number of neighbors. Another characteristic of overlay networks is that the topology can be chosen almost arbitrarily. The underlying routing service ensures that in principle any pairs of nodes can be connected, so there is a large degree of freedom for defining the actual topology. This makes topology construction and maintenance a crucial function in overlay networks (Canright et al., 2004).
In mobile ad-hoc networks a set of wireless mobile devices self-organize into a network without relying on a fixed infrastructure or central control. All nodes are equal, they can join and leave the network at any time and can serve to route data for each other in a multi-hop fashion (Royer and Toh, 1999).
As opposed to overlay networks, we cannot take a routing service for granted and the only means of communication in our model is therefore explicit point-to-point radio transmission. Most notably, like in overlay networks, the topology is also restricted. This is due to the limited power of the nodes, which means they are typically not able to cover the entire span of the network.
Besides, apart from the power constraints, the problem of interference also restricts the transmission range. Nodes can transmit only when the frequency is free. If the range is too large, there are too many overlapping transmissions which render the network unusable. The difference from overlay networks is that topology is given by the physical location of the nodes. By changing the transmission power (and therefore the range) of the nodes, it is possible to tune the topology.
TOPOLOGY DISCOVERY IN MOBILE AD-HOC NETWORK
A network topology is a definition of the network architecture. It
gives certain provisions of the various nodes (components) of the network
and an organization of these nodes (Bitam and Batouche, 2006).
Automatic network discovery is a feature of many common network management tools, such as HP’s OpenView and IBM’s Tivoli (Siamwalla et al., 1999). This is for the wired networks, but in the ad-hoc networks, the problem of topology discovery is significantly different. There is no IP subnet hierarchy and nodes might have stale neighborhood information. Additionally, there is no popular network management protocol, such as SNMP, for ad-hoc networks. Therefore, previously proposed topology discovery protocols for the internet, such as (Siamwalla et al., 1999; Breithart et al., 2000), ((http:www.openview.hp.com/; http:www.tivoli.com) perform poorly in MANETs (Chandra et al., 2002).
We propose here a new system that we called Bees’ system. It has as an objective the definition, for each node, the MANET topology (discovery the whole network topology). In other words, With Bees’ system, each network node will be able to collect network topology information. It can know situations of the other nodes (distances toward others and nodes directions: angles between the local node, the node discovered and the vertical). We obtain at the end and for each node, a better collection of information concerned the architecture of MANET which might be useful for other functions such as the routing, search, discovery, monitoring, collective computation etc. This is an adaptive system which is characterized by the real time updating.
The great importance of this system in this area is the possess of the global data (the whole network topology) starting from a partial data (on node level), without any central administration.
Bees’ system: our contribution: As stated earlier, the Bees’ system is a system which defined, for each node of MANET, the network architecture. We inspire this approach from a natural and biological phenomenon; it is the bees’ communication. We start in this section with a detailed description of the bees’ communication then, we carry out a projection on topology discovery. Thereafter, we specify the approach in the form of algorithms and finally we conclude by deducing their advantages.
Description of the system: The bees communicate each other by a system that is different from the human language. Karl von Frisch, an Austrian scientist (1886-1982) had discovered in 1919 the bees’ communication in dances format. Frisch was worded the Nobel Prize of physiology and medicine in 1973 for this research. These discoveries could be confirmed, in 1986 by German and Danish researchers, using a miniature robot able to carry out this dance between the bees.
First of all the bee seeks the source of food (nectar) then it communicates with the others the localization of food (distance and direction) through two types of dance.
Round dance (the source is in a radius of 100 m): The bee describes a circle, finds itself with its starting point, makes half-turn and takes again the same movement in opposite direction. The other bees observe the dance and find that food is located at less than 100 m (distance). They do not have any indication on its direction.
Wagging dance (the source is beyond 100 m): The bee is directed in comparing to the sun direction. It has the eyes which enable it to locate the sun even through the clouds. It starts by describing a half-circle, then moves towards its starting point while following a straight line, of return to the starting point it remakes a half rings but in the other direction, it includes the same straight line again, with the end it takes again the first half-circle and so on. It describes thus an eight scheme. When it traverses the straight line it agitates its abdomen on the right and on the left, it wags.
The distance which separates the source of food from the hive is calculated and transmitted including the speed of the bee dance; the more food is near the more movements are fast and light. The bee carries out on average 40 turns per minute if the indicate distance 100 m, 24 turns if they are 500 m. For the long distances (being able to go up to 11 km approximately), the dance becomes very slow and the oscillations of the abdomen are more prolonged.
To find the food direction, the bee achieves its dance in comparing to the vertical ray so that the angle of its axis with the vertical ray is the same one as the angle of food relating to the sun in the plane horizon. The direction of the sun is thus represented by the vertical, sight upwards; and the angle formed between the direction of the food with that of the sun is compared to this ascending vertical. If the discovery is exactly in the direction of the sun, the dancer carries out its rectilinear course from bottom to top; if it is exactly in the opposed direction, it goes from top to bottom; if the food is with 45° on the left of the direction of the sun, the bee goes up obliquely towards the left, with 45° of the ascending vertical and so on. The other bees measure the angle of the observed dance axis with the vertical.
Projection in the topology discovery area: The mobile ad-hoc network contains a set of nodes inter-connected in a direct way (node to node one-hop) or in an indirect way (by the intermediary of another node multi-hop) (Fig. 1).
| Fig. 1: | Mobile ad-hoc network topology |
We consider the bees and the food as MANET nodes, because, a bee (node) collects information concerned food (another node). The bee disseminates (transmitting node) the collected information to the other nodes which are in its range (in its covering zone). Then, in each change (new node appearance or in any modification), each node calculates the new distance and finds the new direction in the same way as a bee.
If the discovery is close: (lower than a definite threshold): The transmitter diffuses the distance which separates it from the discovery, but no information concerning the direction is transmitted. In this case, we mention the profit of energy because there are no operations of direction calculating. Moreover, if it is necessary to apply a function such as the routing, the node must disseminate information. Thus, as the discovery is close, then there is not great energy consumption.
If the discovery is beyond the definite threshold: The transmitting node diffuses the distance which separates it from the discovery. For the direction, we propose that each node has a compass, which replaces the sun in the bees’ phenomenon. The transmitter diffuses the angle between the north (find by the compass) and the direction of the discovery. The receiving nodes calculate-in their own positions-the angle between the north and the direction of the discovery.
The distance in both cases (inferior or superior to the threshold) and the direction in the second case are calculated as follows:
The required distance is: the segment A
We have: C2 = A2 + B2 (the Pythagoras theory),
The required direction is: the angleă
the known angle is:
We have:
We have too:
We propose that the segment D and the segment C
form an angle:
Consequently, Sin
| (1) |
| (2) |
We conclude that the node i can calculate the distance and the direction toward the discovery. In the same way the node j calculates its distance and its direction from the received information from transmitter. However, the node k is out of the transmitter range. It can, thus find the information concerned the transmitter by an indirect way, it must be pass by the node i (it is in its range).
Formal specification algorithms
Notation and tasks: In this study, we assume the following notation
as shown in Table 1.
The threshold definition: We take into account the node capacity to determine the threshold.
Initialization (for each node)-example node i-
The Init task initializes the data structure of node i such as (line 1): radio transmission range. The initial value of this data is according to the node type (different from a node to another). Then, node i seeks the nodes which appear in its covering zone. It registers the node detected in a dynamic list by the execution of NewInLis procedure (line 3). Thus, node i calculates the distance and the direction with the detected node j (lines 4-5) as it was explained earlier.
In the case of change: (For each node) example node i: When there is a change in the covering zone of the current node i, it executes the following algorithm. Change cases: a new node penetration, a node exit, a current node i displacement, displacement of the node j already in the covering zone of node j.
| Table 1: | Variables notation used in the following algorithms |
The Change task deals with the change which can occur in the covering zone of node i. We start with the situation consultation, there are two possible scenarios.
The first scenario: if node i is not moved, then, that depends on the node j. We distinguish three cases. The first case: the node j is a new node in the covering zone of node i, which implies a new insertion of the node j in the list (NewInLis), then, a calculation of direction and distance is essential (lines 3-5). The second case: an old node j has exited the covering zone of node i, then we must eliminate this node from the list (Delete) (line 7). The third case: an old node j has just moved in the covering zone of node i, then there is an update on the distance and direction (lines 9-10).
The second scenario: it is the displacement of node i. In this scenario, it is necessary to visualize the new covering zone of node i. For each node in new covering zone and which was in the preceding covering zone, we modify distance and direction (line 17-18). However, for the nodes which are new, they must be inserted in the list with their distances and directions (line 21-23). For the nodes which were in the preceding covering zone but they do not appear in new covering zone, they must be eliminated (line 27).
The system philosophy can be used to resolve other problems which search solutions in meta-heuristic methods (Bitam and Batouche, 2006).
SIMULATION EXPERIMENTS
Simulation environment: We have implemented Bees’ approach in NetLogo simulator version 3.1.3 (Wilensky, 1999). For the simulation, we have used a simulation area of 1200x1200 units. We choose the threshold equal to 10 units. We employed 100 mobile nodes (100 bees). We let the mobile nodes moved in random direction. In each movement, the node makes one step (one unit) during 100 iterations (the number maximum of steps carried out by mobile node). Moreover, we consider the variability of the covering zone radius of each node. For this, for each node, the covering zone rayon = threshold_min + random_value (between 0 and 15) specified by the experimenters.
The Table 2 results are reached after 10 tests. The main goal of this simulation is to prove the connections possibility between the different nodes in direct or in indirect manner.
We remark for covering zone rayon which is equal to: 10 units, a node can know only 10% of the network nodes and all these connections are direct (it knows only the nodes which are in its range).
For a covering zone rayon that is equal to: 20 units, a node can know 90% of the network nodes, but 84% of the known connections are direct and 16% are indirect (these last are out of the range of the node). For covering zone rayon of: 25 units, a node can know 100% of the network nodes. 85% of the known connections are direct and 15% are indirect.
We concluded that our approach helps to the topology discovered, even in the cases of distant nodes (which do not have a covering zone in intersection). For the medium value of the covering zone concerned node i (micro-level) = 25 units, it is possible to know information 100% about distance and direction for the other nodes: this is the network topology discovery (macro-level).
| Table 2: | Simulation results showing for each node the rate of network topology discovery |
CONCLUSIONS
In this study we have defined a new system bees’ system for the topology discovery problem. This system had been inspired from the communication between bees. In this way, our system considers, for each node that, the other nodes in its covering zone may be divided in two sets. The first node contains the close nodes and the second contains the distant nodes. For the former, each node calculates only the distances with the nodes in this set. However, for the later, each node calculates the distances and the directions. In all cases, the nodes transfer the topology information what leads to topology discovery for each node. Bees system’ presents some advantages in comparing with other topology discovery method. First, it ensures the equality between nodes. There is no clustering and no cluster head in the network. Moreover, our system avoids the flooding in the case of distant nodes and economizes the energy for the close nodes.
Also, bees’ system is an adaptive system which updates the topology information in real time manner. The topology discovered by this system may be making easier other MANETs problems such as routing, energy economy etc.