Keywords

1 Introduction

Wireless Ad Hoc networks are playing important role in critical and home automation applications due to its simplicity and cost. Military applications, emergency services, environment monitoring, disaster monitoring, car-to-car communications [1], etc. are some real-time applications using wireless Ad Hoc networks. Wireless Ad Hoc networks are constructed using devices which are having capability to sense and communicate with other. Devices are having their own resources such as battery, radio, memory, and computational power. Devices are having finite source of energy by means of battery; otherwise in some cases, solar charging units are provided. Generally, devices are in very small size of millimeter resulting in preserving limited resources. With these limitations, it is always being a challenge for researchers to construct a long life, energy efficient, and secure network of wireless devices which are used for real-time critical applications. Nodes are spread over large geographical area to collect and forward the real-time information in distributed fashion. As manual configuration and maintenance are troublesome, automatic configuration and maintenance are recommended. Automatic configuration and maintenance can simply be termed as “self-organization.”

All the nodes do not know their role at the start of network. Once network formation starts, different behaviors are assigned to nodes dynamically by the network to achieve the global role of the network. Broadcast mechanism is used by nodes to reach to all other remaining nodes of network. Runtime data is sensed by the nodes, and basic processing is done locally. This processed data is routed to base station through some intermediate nodes. Localized distributed processing is done on collected data to achieve smooth running of global network. Constructing an energy efficient, long life, maintainable, scalable, and secure [2] wireless Ad Hoc network with limited resources attracted attention of many researchers. Next section of this paper is organized into the following sections: self-organization, strategies of self-organization for hierarchical structure, and conclusion.

2 Self-organization

In wireless Ad Hoc networks, hundreds or thousands of nodes are spread over large geographical area. These nodes collect some real-time information, process it, and forward it to centralized base station. Each node will have an unique identification like IP address in the network. Nodes communicate directly or through neighbors to forward processed data. As broadcasting is the base of communication forwarding, more and more messages in the network utilize energy of nodes causing early exhaust of the node battery. Once the battery of the node is exhausted, node becomes dead and the corresponding portion of network gets disconnected from network. This makes researchers to think about energy consumption and minimum broadcast of messages while designing strategies for wireless Ad Hoc networks to extend the life of network. Generally, battery of the nodes taking part in forwarding of data of their neighbors exhausts early as compared with others. As nodes do not know their role in the network at the start, by applying some policies nodes with higher energies can be chosen to work as backbone for forwarding data. These networks are self configuring and self managing; hence, self-organization can be defined as “A network is said to be self-organized if it is organized without any centralized or external control” [3]. Different strategies are suggested by researchers to minimize broadcast in the network to minimize consumption of the energy and make network long life. These strategies for self-organization are inspired from real-life self-organizations such as school of fish, ant colony, and synchronization in fireflies while emitting light. While applying these strategies, various network structures used for wireless Ad Hoc network are like the following [4, 5]:

  1. 1.

    Location based—In location-based networks, geographical location of the node is used as an unique identification of node. Nodes are spread over large geographical area to collect real-time information, Fig. 1a.

    Fig. 1
    figure 1

    Network structures of wireless Ad Hoc network

    Full size image
  2. 2.

    Flat based—Flat-based networks are having all nodes at same level and profile. They form a mesh among them and coordinate to forward data till base station, Fig. 1b.

  3. 3.

    Hierarchical network—In hierarchical networks, nodes are arranged level wise and low-level nodes can communicate only with upper-level nodes. Upper-level nodes forward data to base station. Low-level nodes never communicate with base station directly, Fig. 1c.

3 Strategies of Self-organization for Hierarchical Structure

Generally, wireless Ad Hoc network is modeled using 2D Graph as G = (V, E), where V is vertices (nodes) and E are edges (links) of the given network [6]. In this to minimize broadcasting of messages, maximum independent set and minimum dominating sets are formed [7, 8]. Members of independent set cannot communicate with each other directly, and members of dominating set have at least one node from independent set in reach. Members of dominating set participate in constructing virtual backbone till base station and of independent set nodes forwards messages to one of the node in the dominating set to forward it to base station.

In January 2001 [9], a long-term Terminode project was started which was one main step toward self-organization. This paper gives overview about wireless Ad Hoc networks, self-organization, and its long-term potential. Nodes in this networks were termed as terminode which is combination of terminal and node with its own sensing unit, computational unit, memory, radio frequency, and battery. It elaborates characteristics, challenges, and technical issues involved in constructing and maintaining self-organized wireless Ad Hoc network.

Toner [10] suggests a scheme for address management and merging of small networks to create a global wireless Ad Hoc network. It uses a 32-bit IP address and a 32-bit network address. A leader is selected by leader election algorithm that maintains a list of address used by connected nodes. New node interested to join should choose a random address and make a join request. The leader assigns a valid address to this new node. As leader has complete knowledge of network, it broadcasts the table to all its neighbors with version number. In case of the absence of leader, a node with latest version of table and sufficient energy is selected as leader. When a node receives a beacon from a foreign leader, it is forwarded to its leader. Merging of two networks is done through the node who forwarded beacon, and two networks are differentiated by means of network ID. Overall, in this approach, primarily clusters are created with one leader each and then in merging clusters are connected to form a global network.

Krishnan [11] suggests an efficient clustering algorithm with maximum limit on number of nodes in a cluster called budget. This strategy consists of three algorithms:

  1. 1.

    Expanding ring—In this, initiator sends messages to neighbors in rounds. In each round, scope of neighbor is incremented by “1.” In some rounds, initiator gets complete list of associated nodes. If associated list of nodes is larger than budget, some nodes are dropped from cluster with a message broadcast in the network.

  2. 2.

    Rapid algorithm—Initiator is assigned with budget “B” including itself so with “B-1” initiator broadcasts messages to its neighbors. At each new neighbor, budget is decremented by 1. As budget is exhausted, message is not forwarded further. All nodes getting valid budget message acknowledge the initiator and become cluster member.

  3. 3.

    Persistent algorithm—This algorithm is recursive, and working is similar to rapid algorithm with one difference. Neighboring nodes receiving message with budget do not acknowledge initiator immediately. It waits for acknowledgment from its neighbors and checks all possibilities for further growth. If further growth is possible, it allows, and if not, it acknowledges to initiator.

Chang [12] suggests a cluster-based self-organization management protocol. While developing this strategy, 20/80 rule is followed to create upper-level nodes and low-level nodes. It uses on-demand routing to route packet in backbone. Cluster head is selected by broadcasting “Hello” message to the neighbors, but these cluster heads are just to manage cluster not involved in routing of packets. Each node of cluster maintains a routing table in which paths for desired destination nodes are present. While routing a packet source node checks in its table for destination if available packet is routed on the path, and if not, a route request is generated and is broadcasted in neighbors. This is forwarded till destination once reached new path which is updated in the table of source. In this way, every node maintains a path to destination may be in same cluster or in other cluster.

Venuturumilli [3] suggests a self-organization model for heterogeneous WSN. Heterogeneous WSN is all nodes are with different profile. It is considered that every node can choose different transmission ranges such as whisperer, shouter, and speaker. Algorithm works in three different steps: 1. initial setup, 2. basic radius updates, and 3. enhanced radius update.

  1. 1.

    Initial setup—At the start of network, every node in the shouter range collects information about neighboring nodes and downgrades the range to whisperer. At this collection node creates three lists one with nodes in the whisperer range, another with nodes outside whisperer range but inside shouter range, and current neighbors depending upon current transmission range.

  2. 2.

    Basic radius update—In this phase, each node checks whether all its ring nodes are reachable through whispering neighbor. If all its ring nodes are reachable through whisperer range of neighbors, there is no need to change transmission range from whisperer to shouter.

  3. 3.

    Enhanced radius update—In phase two, only one-hop neighbors are checked to reach to all ring nodes, and if not, reachable transmission range is boosted to shouter. This would be unnecessary as maybe remaining ring nodes are reachable through two-hop neighbors. This phase works in similar way but checks for two-hop neighbors to reach to ring nodes.

Lehsaini [13] suggests an efficient self-organization algorithm for clustering. In this strategy, a limit is given to maximum and minimum number of nodes in a cluster. To select a cluster head triplet metric k-density, residual energy, and mobility are used. A node with highest weight in comparison with two-hop neighbors is selected as cluster head. This leader is not permanent after specific time interval, and leader selection algorithm is executed. Each node holds information such as Nodeid, Nodech, Weight, Hop size, Threshlower, and ThreshUpper. Cluster head holds information about other cluster heads such as Nodech and Weight. This algorithm works in two phases.

At the start, any random node initiates process of cauterization by sending “Hello” message to all its two-hop neighbors. Among receiving nodes, one node with highest weight is selected as cluster head. This new cluster head sends connection request to other neighbors if Threshupper is not reached. In first phase, clusters are created but some of them may be with fewer nodes than Threshlower. In second phase, such clusters are merged with other clusters. Cluster heads with less nodes than Threshupper broadcast a message of re-affiliation to other clusters. Result of second phase is clustered with more nodes than Threshlower is formed.

Chawla [14] suggests node stability-based clustering algorithm. Node stability is mobility of the node in the network. In this approach, three parameters are used for selecting cluster head degree of node, remaining battery power, and stability. Stability of a node at the start of network is always “0.” Once a network is formed, each node keeps neighbors ID with “Hello” messages from neighbors. At next time, cycle node again gets “Hello” messages from neighbors and IDs of them. These IDs are compared to find out stability.

Algorithm starts with each node broadcasting a “Hello” message to its neighbors. Receiving nodes calculate their three factors in which stability is kept as “0.” Receiving node replies with “Hello” to the sender with this triplet. Out of collected triplets, maximum competency is calculated, and the node with maximum competency is selected as cluster head. If competency value of two nodes is matching, then the node with lower ID is selected as cluster head. Finally, each node broadcasts a “Hello” message with cluster head ID to convey new cluster head. This process of electing cluster head is periodic and carried out after fixed amount of time. If any cluster head moves out of cluster before time expires, another node with next higher competency is selected as cluster head till timeout.

Salzmann [15] suggests a strategy to form clusters without knowing their position, and only one node of the cluster has to be active per cluster. This strategy is designed for homogenous WSN and works in three phases, namely information phase, clustering phase, and affirmation phase.

Starting node with transmission power RW broadcasts a message “Possible Cluster Head” to all neighbors. All neighboring nodes change their mode to “Possible Cluster Head” and transmit this message with RW. By lowering the range to 50 % (with RW/2), starting node forces neighboring nodes to join cluster. They join the cluster and change mode to “Join Cluster.” At the last in Affirmation phase, all joined nodes confirm their joining to cluster and broadcast a message with RW/2 to all nearby nodes to show already joined a node.

Orfanus [16] suggests an algorithm for power-low topology in self-organization. When degree of distribution followed power function, the network is called as power-low network.

It is assumed that a peer “N” with “m” links arrived in the network. “N” requests to bootstrap server for IDs for all “m” links from existing network. Bootstrap server chooses a random peer “D” with low degree to connect with “N.” “N” initiates the process by requesting ID of peer to be attached with. “D” sends its own ID or one of the neighbors ID. “N” makes connection with the node whose ID is sent by “D.” This algorithm takes care of security of network by taking all decisions in the existing network not at the new arriving peers.

Kalita [4] suggests clusterization by using triangular method for self-organization. In this, at the start of network formation, a node is chosen at random suppose “A.” Then, find another point “B” such that AB is minimum. A and B are connected and are now a live edge. Then, find third point “C” such that ABC is min triangle. Further, choose a live edge from AC and BC. This algorithm will work in loop and form a complete network till all nodes are joined. Clusters are formed by ordering procedure.

Qi [17] suggests hierarchical protocol architecture with multiple clustering. In general clustering, algorithms’ certain probability is used to choose cluster head, and all non-cluster head node should transfer data to cluster head and cluster head forwards it to base station. In the suggested MCEE protocol, cluster head sends data to super node and super node forwards it to base station. Cluster head is selected by broadcasting “Hello” messages in the neighbors, and at the same time, a super node is also selected. Super node is a functionality which is rotating or interchangeable among cluster head and other nodes of the cluster. This interchangeability is done to achieve load balancing as super node has more packets forwarding load than other nodes.

Hanchichi [18] suggests a virtual topology for routing in Ad Hoc networks. Based on virtual topology, cluster heads and gateways contribute in searching destination. In this algorithm, cluster head is chosen on preference from neighbors. Higher choice node is chosen as cluster head by neighboring nodes. In this, one secondary cluster head is also selected per cluster. Cluster head, secondary cluster head, and normal nodes form a forest of links inside the cluster. As forest is created of links, routing become necessary to forward packets inside the cluster. Two different approaches are used while routing, inside cluster proactive routing is used, and among clusters, on-demand routing is used. Cluster head maintains a table of routes to the desired destinations. When a node of cluster is interested to forward a packet to other node, it sends a route request to the cluster head, and if the destination is in the cluster and route present in the table, then packets are forwarded through cluster head to destination. If node is not member of cluster and its route not present in the table then cluster head initiates a search in neighboring clusters. If route is present in any one of the cluster head then it is replied to source cluster head. If not present in any of the cluster, a route request is broadcasted to all its neighboring cluster heads. Replied route is updated in the table of requesting cluster head, and data is forwarded accordingly.

Heinzelman [19] suggested a Low-Energy Adaptive Clustering Hierarchy (LEACH). Two assumptions were made while developing this protocol: 1. A unique base station is present to which all nodes are interested to communicate with base station, and 2. all nodes are having capability to communicate with base station. In this protocol, cluster head is decided by self declaration by the node. Node who is interested to be as a cluster head elects himself by some probability as a cluster head and conveys its status to all its neighbors by means of broadcast message. As such many broadcast messages may be received by any node in the network, nodes decide their association with a particular cluster head by calculating minimum energy to communicate with them. Cluster head utilizes its energy at more extend as compared with other nodes to avoid cluster head battery exhaust, and selection process is done after every random time. After a random time “d,” another interested node with enough energy elects itself a cluster head.

Biradar [20] suggests a multi-hop LEACH. In this cluster formation procedure used is same as LEACH protocol, but routing is dome using multi-hop technique. A message from a node reaches to the base station through a path starting from cluster head of its cluster to base station. This involves a sequence of other cluster heads (hops) rooted at the base station called as multi-hop inter-cluster operation. In intra-cluster operation, nodes that are in direct visibility of the cluster head sends messages directly to it, but nodes that are not in the visibility of cluster head can take a route to it through nodes that are in visibility.

Rauthan [21] suggests an improved multi-hop LEACH. In this, one more node is elected as vice cluster head. This node is used as backup for cluster head in case of any accidental death of cluster head. This node works as cluster head at any accidental case to avoid data loss of nodes and cluster.

Olascuaga-Cabrera [22] suggested a strategy of self-organization for a network in which all nodes are mobile nodes. They are with different constraints/profile and can enter or leave network at any time. In this algorithm, agents play multiple roles in the network such as leader, gateway, and members. Each group has at least one agent as leader, zero, or more agents as gateway and one or more agent as member. As network starts, wake-up agents do not have any role in the network. The first role assigned is leader. Many agents may get role of leader at the start so this conflict is solved by leader election algorithm, and only one agent is elected as a leader. If an agent is visible to two or more nearby leaders, it is selected as gateway between the leaders, and remaining nodes remains as member of clusters. Leaders and gateways spend more energy as compared to other agents of the network so agents decide by their own to change their role depending upon current status of energy. Leader election algorithm is executed in the network whenever need arises like due to low energy leader changed its role to normal agent.

Routing table and its updates are broadcasted to all member agents of the cluster by the leader. To achieve optimistic energy consumption, at stable state of the network, broadcast of routing update is done with low frequency, and at unstable state, this frequency is comparatively high.

Olascuaga-Cabrera [23, 24] has done an improvement in the strategy suggested in [22]. This approach uses one or more role of Bridge other than leader, gateway, and member. This is done to solve segmentation problem discussed in [21]. Bridge is an agent which on detecting another agent from other group tries to establish a connection with them. If connection is established, agent switches its role to Bridge.

At the start of network, each agent broadcasts “Hello” messages to their neighbors, depending upon their neighbor’s role of agent is decided in the network. If a node has no neighbor, it gets a role of “any” at the start. If in the neighborhood leader agent does not exist, role of leader is assigned to node, and if only one leader is detected in the neighborhood, agent becomes a member agent. When a member detects two or more than two leaders in the neighborhood, it changes its role to gateway. When a agent detects another agent from other group, it sends a Bridge request to other agent. Agent from other group first becomes Bridge and sends acknowledgment to requesting node. After receiving this acknowledgment, agent becomes a Bridge.

Shirsat [5, 25] suggested modified version for the algorithm in [23, 24] and roles of agents in the network. This approach is based on minimum spanning tree and concentrates on minimizing number of backbone links so that broadcast will be minimum and energy will be conserved.

Four different roles are identified for the agents leader, gateway, willing to act as gateway, and agent. At the start of network, first agent will get the role of leader, and if conflict arises, leader selection algorithm decides one agent as leader out of conflicting nodes. To achieve load balancing, leader selection algorithm is executed periodically. Agents who are having two or more than two leaders at the neighbor are selected as gateway, and remaining agents are members. In this way, a virtual backbone is created of cluster heads and gateways for communication of network. In the formation of network, it is possible that two or more than two agents are selected as gateway on same path. This approach tries to achieve backbone close to minimum spanning tree, but with such multiple gateways on the path, this cannot be achieved. When multiple gateways are present on the same path, only one is kept as gateway and remaining become willing to act as gateway. Willing to act as gateway works as a normal agent of the cluster but when needed can become gateway.

4 Conclusion

In this paper, the survey of various self-organization strategies is discussed. Algorithms for hierarchical network structures are studied and discussed in detail. In this survey, it is observed that hierarchical network structures of self-organization are economic in management and energy consumption. So, we want to focus on role-based cluster formation strategies/algorithms for further topic of research. Further study involves identification of efficient roles, effective formation, and maintenance of self-organized wireless Ad Hoc network such that energy consumption will be minimum. Also, we want to add a backup mechanism in case of failure of backbone network.