Fuzzy-controlled energy-efficient single hop clustering scheme with (FESC) in ad hoc networks

Abstract

A mobile ad hoc network (MANET) is formed when group of mobile wireless nodes collaborate between them to communicate through wireless links in the absence of the fixed infrastructure and any centralized control. These characteristics make it able to adapt and operate in difficult conditions. It is vital to keep the topology stable as long as possible. An effective clustering scheme renders longer cluster lifetime and incurs low maintenance overhead. However, the mobility of nodes adversely affects the hierarchical structure. Therefore, electing nodes with small relative velocity with respect to it’s 1-hop downlink neighbors or cluster members, for the role of cluster head is a preferred option that makes the clusters more stable. In the proposed scheme FESC, we present a relatively stable clustering scheme by considering more powerful however less mobile (w.r.t. the cluster members) nodes as cluster heads. The cluster heads can themselves estimate the competency value of the cluster. If it is small enough, then it advises the nodes with other cluster options to join some better clusters so that they don’t arbitrarily join and leave available clusters. The simulation analysis confirms that our scheme delivers more stable clusters with low maintenance effort.

1 Introduction

1.1 Preface

An ad hoc network is a multi-hop wireless network that is established by a group of mobile nodes without depending on any infrastructure. It finds a lot of applications particularly in emergency situations like war, natural disaster etc. [1, 2, 16, 20, 30]. The network only consists of certain nodes that move freely, with arbitrary velocity in arbitrary direction. Each node is equipped with an abstract electronic circle around it, which is called radio-range. Nodes lying within the radio-range of a node n_i, are called 1-hop downlink neighbor or simply downlink neighbor of n_i. Similarly, if n_i is present within radio-circles of some nodes, say, n_j, n_k and n_g, then n_j, n_k and n_g will be called uplink neighbors of n_i. Inherent uncertainty of the environment along with unpredictable dynamism, make the network communication more challenging and the management more difficult [15, 25, 29, 30]. Furthermore, scalability is a critical concern among various other difficulties in the ad hoc networks. Large number of nodes competes for limited bandwidth in wireless network. The size of routing table grows with the increase in number of nodes.

Particularly during broadcast operations, data packets are to be supplied to each and every node in the network. This becomes easier with clustering. Instead of blind flooding, if clustered flooding is applied, then responsibility on individual routers reduces up to a great extent [12, 22, 24]. If a broadcast message is delivered by a router to head of a cluster, then it is highly expected that the clusterhead will definitely forward the message to its cluster members. Hence, load on that router decreases and it can now concentrate on other neighbor clusterheads. During route discovery in ad hoc networks, route-request (RREQ) packets are to be forwarded to all nodes in the network in order to discover the destination. This operation is the basis of all data packet unicast as well as multicast operations. If number of node in the network is a huge one then it will cause a lot of problems. One prominent approach for overcoming the scalability problem is clustering. Abstracting the network topology into different hierarchies of nodes is termed as clustering. Easy administration is another offshoot of clustering [1, 21, 29].

The clustering scheme works in two stages; in the initial phase the nodes are divided into groups and in the later phase efforts are made to maintain the structure created in first phase. In any clustering scheme, first phase is initialization and later on the maintenance procedure is invoked repeatedly to avoid the complete deterioration of the structure created before [6, 8, 11]. The frequent invocation of second phase incurs higher overhead. By making the initialization phase highly stable one can reduce the number of invocation of maintenance phase [2, 4, 7, 13]. Because of the high cost of re-clustering, stable clustering schemes have gain more attention in recent years. The mobility of nodes plays an important role in cluster stability. Mobility causes a node to frequently join and leave a cluster. As a result, clustering schemes for MANETs are designed to be adaptive towards node mobility. However, many of the schemes presented before have not taken mobility into consideration and thus make the cluster unstable [3, 7,8,9,10,11].

All clustering schemes initially elect a node as clusterhead and the downlink neighbors are by default included in the single hop cluster. A cluster may be isolated or connected. An isolated cluster is of no use because it will not be able to send to and receive information from the rest of the network. On the other hand, a connected cluster is one which is connected to at least one cluster [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15].

1.2 Why single hop

Compared to multi-hop clusters, single hop clusters are easy to manage. Updating the number of cluster members requires only three consecutive HELLO messages. If an existing cluster member does not respond to three consecutive HELLO messages sent by the clusterhead i.e. it’s ACK message does not reach the clusterhead, it is understood by the clusterhead that the node has exited from it’s radio circle and therefore, is no longer a cluster member [22, 29]. On the other hand, in multi-hop clusters the similar event will not be directly detected by the clusterhead but by the predecessor of the node which, in turn, will have to report it to the clusterhead through a multi-hop route in most cases (unless the exiting node is just two hops away from the clusterhead). In case of multiple such events, congestion may occur within the cluster. Intra-cluster communication will involve multi-hop paths though inter-cluster communication will be smaller in number. Management of both intra-cluster and inter-cluster communications is a great concern for the heads of multi-hop clusters. Therefore we concentrate on the single hop clustering in ad hoc networks.

1.3 Contributions of the present scheme FESC

The present article proposes an energy and mobility aware clustering scheme that assigns weight to the clusterheads depending upon its residual energy, relative mobility with respect to its 1-hop downlink neighbors and connectivity with neighbor clusters. As a result, comparatively stable clusters are formed. Certain clustering schemes demonstrated earlier the importance of remaining battery power and relative velocity between a potential clusterhead and it’s 1-hop downlink neighbors, but still the impact of network connectivity in election of clusterheads as well as evaluation of attachment between a clusterhead and a node that has newly arrived in it’s vicinity, was not an explored area. FESC not only presents novel formulation of these mentioned criteria of nodes but also elaborately discusses the kind of network connectivity a potential clusterhead should have. Our intention is not only to form clusters but the clusters that will be connected to at least some part of the network; the communication may be from clusterhead to network, to network from the clusterhead or both. Isolated clusters are of no use; a good amount of inter-cluster connectivity is the need of the hour.

FESC emphasizes on the fact that even if a newly arrived node increases the load on the clusterhead, still the load is tolerable provided inclusion of the node in the cluster improves inter-cluster communication capacity of that cluster. Pictorially we have also demonstrated that even if a node doesn’t have any non-clustered downlink neighbor, still it’s clusterhead status may significantly improve inter-cluster connectivity. The nodes are basically classified into four categories—clusterhead, ordinary member, gateway and supporting gateway. Their roles in ad hoc network are illustrated using pictures. The scheme is capable of computing the optimum positions of gateways for consumption of minimum energy during communication from one cluster to another.

The clusters produced by FESC are stable, where the rate of re-election of clusterheads is small and the rate of change of cluster by it’s members is also small. In presence of more than one inter-cluster route, priority is given to the one that consumes least energy. Therefore, average node lifetime also increases up to a great extent.

1.4 Organization of the article

The remainder of the paper is organized as follows. Section 2 surveys related work on clustering schemes, mostly single hop. Section 3 illustrates the main idea behind cluster formation along with analytical study whereas Sects. 4 and 5 describe the design of fuzzy controllers used in FESC. Section 6 shows the effectiveness of our protocol through simulation while Sect. 7 concludes the paper.

2 Related work

The components of a clustered ad hoc network are cluster heads and cluster members. The responsibilities of a cluster head are managing the cluster and coordinating intra as well as inter-cluster communication. A cluster member is a non-clusterhead node belonging to a cluster. A lot of clustering schemes have been proposed in literature that elect clusterheads and maintain communication to and from the cluster [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18, 21,23,24,25,26,27,28]. Among them, some state-of-the-art protocols are mentioned here. In mobility based clustering or MOBIC [13], the metric used is relative mobility or RM, which is based on the difference of strengths of two consecutive received signals. If the node is moving close to (or going far from) the potential clusterhead, the strength of the signal received second, will be higher (lower) than the strength of the signal received first. This indicates that the relative velocity of the node with respect to the potential clusterhead has become smaller (larger). In order to become a clusterhead, a node must have small relative velocity with respect to its downlink neighbors. But, the elected clusterhead may soon run out of power if residual energy of nodes is not considered during election of clusterheads.

In distributed clustering scheme (DCA [1]) the node having highest number of downlink neighbors among it’s 1-hop neighborhood, is elected as the clusterhead. Since it does not consider relative velocity of nodes, it is unsuitable for dynamic networks. Distributed modified scheme for clustering (DMAC [5]) is an enhanced version of DCA that takes care of relative mobility between neighbors. Leader clustering scheme (LCA [12]) elects the node that has got the highest identification number within its 1-hop neighbors. LCA has a definite bias towards higher id nodes while electing clusterheads.

LCA has been modified in LCA2 [12, 16]. It says that a node may declare itself as a clusterhead provided it has got the lowest identification number among all of it’s non-clustered 1-hop downlink neighbors. WCA [14] elects clusterheads based on three different criteria—degree of nodes, time duration for which it has acted as clusterhead in the past and average speed. The idea behind is that, if a node has already acted as clusterhead for sufficient long time then the node is expected to have very small remaining battery power and with this small residual power it is not suitable for the responsible position of a clusterhead. The weight is directly proportional to mobility and inversely proportional to the remaining power; the node with smallest weight is chosen as the clusterhead. Energy aware load-balanced clustering (LS-WCA) [22] concentrates on the fact that a clusterhead may become overloaded due to uncontrolled number of migrating nodes within its vicinity. It imposes an upper limit on the number of members a clusterhead can have. LS-WCA utilizes the techniques of WCA to elect a clusterhead.

Topology adaptive clustering scheme (TACA [15]) considers the remaining power of a node as well as it’s relative velocity with respect to downlink neighbors. The average of last few displacements is computed to get an estimation of the average speed. The mobility factor of a node is defined to be the difference between the maximum permissible speed of a node and it’s average speed. If it is large, then the node is not highly mobile. On the other hand, if it is small, then the node is very fast. Nodes are assigned weights based on the factors mentioned above. The one with the maximum weight is elected as the clusterhead. In mobility based clustering scheme (MBCA [21]) all nodes send and receive “Hello” messages to and from their 1-hop downlink and uplink neighbors. From the differences in signal strength of two consecutively received Hello messages, pairwise relative velocity is calculated. The authors claim that this will form more stable clusters (although residual energy of nodes is not considered), each clusterhead is supposed to work for a long time and the election scheme won’t repeat.

3 Proposed work FESC

3.1 Network model

Before FESC is applied on the ad hoc network, it is modeled as a graph G = (V, E) where V is the set of vertices and E is the set of edges. The task of FESC is to discover individual clusters in ad hoc network. Each node regularly broadcasts HELLO message within its downlink neighborhood and all nodes residing within its radio range reply with an acknowledgement or ACK message in response to that HELLO. This attributes of HELLO message are as follows:

• (i) Identification number

• (ii) Geographical position in terms of latitude and longitude

• (iii) Radio-range

• (iv) Maximum transmission power

• (v) Clusterhead status

Clusterhead status is 1 if the node declares itself as clusterhead or wants to continue with the status of a clusterhead. A node can upgrade itself to the status of a clusterhead from an ordinary node, provided it satisfies certain criteria. For example, it is supposed to live long. In order to bring stability in the network structure we must not alter heads of clusters every now and then. Hence, residual energy of a potential clusterhead should be high and that representative of the cluster should maintain should have small relative velocity with it’s downlink neighbors. Also it needs to maintain good connectivity with neighbor clusterheads for effective and efficient message forwarding. Last but not the least; a king is not a king without a subject. Therefore, a node must be equipped with a good number of downlink neighbors not attached to any cluster so far, to strengthen its claim of clusterhead status. These requirements are combined using a fuzzy controller head_elector which is embedded in each node. A node itself can determine whether it is capable of forming its own cluster or not.

Components of an ACK message the first four attributes of HELLO message along with cluster member status of the node. Cluster member status of a node denotes the list of clusterheads along with their last known geographical locations and radio ranges, to which the node is attached and similar information about the clusterheads residing within the radio range of that node. Whenever a new node enters vicinity of a cluster, it checks through another fuzzy controller affinity_detector (like head_elector, affinity_detector is also embedded in each node) whether it should join the new cluster or not. If the node is not already attached to a number of clusters, has low relative velocity with respect to head of the new cluster and opens up the door to new intercluster connectivity, then chances are high that the node will join the new cluster.

Please note that, multiple criteria are governing both the election of clusterhead as well as attaching nodes to clusters. The way those criteria influence FESC, are mostly represented in the form of natural language (particularly usage of the words good, bad, high, low, small etc.). These phrases encouraged us to use fuzzy logic in designing the clustering scheme. Fuzzy logic is flexible, tolerant of imprecise data and based on natural language [31]. Therefore, we have used two fuzzy controllers both of which are embedded in every node—head_elector for electing clusterheads affinity_detector in order to judge the attachment between a node and a cluster.

FESC divides the network into a number of clusters. G is converted to G_clus = (V_clus, E_clus) where V_clus is the set of one hop clusters and E_clus is the set of inter-cluster edges. Each one hop cluster v_cls ∈ V_clus, is expressed as v_cls = (head_cls, mem_cls, ∀_{member_cls ∈ mem_cls} e(head_cls, member_cls)), where head_cls is head of the cluster v_cls; mem_cls is the set of ordinary members of the same cluster. e(head_cls, member_cls) is the edge from head_cls to member_cls.

3.2 Distinct entities in clusters

In clustering procedure, a representative of each sub-domain (cluster) is ‘elected’ as a cluster head (CH) and a node which serves as intermediate for inter-cluster communication is called gateway. Remaining members are called ordinary nodes. The boundaries of a cluster are defined by the transmission area of its CH. With an underlying cluster structure, non-ordinary nodes play the role of dominant forwarding nodes, as shown in Fig. 1.

Fig. 1

Cluster heads, ordinary nodes and gateways

Figure 1 shows three clusters A, B and C. In all three of them, the cluster heads are denoted by red color; ordinary members are white whereas gateways are grey. The gateways can be again classified as in gateways and out gateways. For example, in cluster A, n_p is an in gateway whereas n_q is a out gateway. Similarly, n_r is a out gateway for cluster B and n_s is a in gateway for cluster C. A gateway can act both as in and out gateways in certain cases. It is better if two clusters have more than one in as well as out gateways. That will balance load among the gateways during inter-cluster communication.

The concept of supporting in gateway in introduced in Fig. 2. In Fig. 1, the head of cluster C is within the radio range of n_s. But, if that is not the case, then n_s will have to find a route to the head of cluster C through some members of the cluster C. Those members will be termed as supporting in gateways. For example, in Fig. 2, n_v and n_w are supporting in gateways (colored in sky blue) whereas n_s continues to be an in gateway for cluster C.

Fig. 2

Demonstration of supporting in gateways

It will be relevant here to make it clear that there is no existence of supporting out gateways because all the cluster members are within the radio range of the cluster head and the head does not need any support to communicate with any of its members. The communication is completely single hop, from the head to a downlink neighbor.

Below we illustrate the computation of optimum position of gateways in two different cases of shortest possible communication between two clusterheads B and C.

3.3 Optimum gateway positions

3.3.1 Case-1: out gateway of B and in gateway of C are different

The shortest inter-cluster communication between two clusterheads say from B to C (where the out gateway of B and in gateway of C are different) will take place provided the following conditions satisfy:

• (i) There is no supporting in gateway for C.

• (ii) The out gateway of B and the in gateway of C both lie on the straight line connecting the heads of the clusters B and C. The reason is that, if the gateways deviate too much from that straight line, it will increase the path length the signal has to cover to reach the receiver from the transmitter. Increased distance will increase the energy consumption too.

The above mentioned conditions are pictorially shown in Fig. 3.

Fig. 3

Different out gateway of B and in gateway of C

As per the Friis transmission equation, if a node transmits with power Pt, and a node in its radio range receives that with power Pr, then,

$${ \Pr } = {\text{Pt}} \times {\text{K}}/{\text{dist}}^{\text{m}}$$

(1)

where m = 2 if the signal attenuation is only due to distance, i.e. no wall or any similar hindrance is there between the transmitter and the receiver. Otherwise, it is a general practice in ad hoc networks to take m = 3 or m = 4, because this is sufficient to model real life signal attenuation situation.

Computation of the optimum positions of the out gateway of cluster B and in gateway of cluster C is illustrated next. The clusterheads of B and C are n_B and n_C, respectively. The out gateway of B is n_r and the in gateway of C is n_s. Let the distance between n_B and n_C is V, between n_B and n_r is x, between n_C and n_s is y. Therefore, the distance between n_r and n_s, is (V − x − y). Also assume that the threshold receive power of any node n_i is thr(i).

As per the Friis equation, energy consumed in

• (i) n_B is (thr(r) x^m)

• (ii) n_r is (thr(s) (V − x – y)^m)

• (iii) n_s is (thr(C) y^m)

Therefore, the total energy consumed ϕ(B,C) is formulated as,

$$\upphi \left( {{\text{B}},{\text{C}}} \right) \, = {\text{ thr}}\left( {\text{r}} \right){\text{ x}}^{\text{m}} + {\text{ thr}}\left( {\text{s}} \right) \, \left( {{\text{V}} - {\text{x}} - {\text{y}}} \right)^{\text{m}} + {\text{ thr}}\left( {\text{C}} \right){\text{ y}}^{\text{m}}$$

(2)

$${\text{So}},\;\frac{{\partial \upphi \left( {{\text{B}},{\text{C}}} \right)}}{\partial {\rm x}} = {\text{m thr}}\left( {\text{r}} \right){\text{ x}}^{{{\text{m}} - 1}} + {\text{ m thr}}\left( {\text{s}} \right) \, \left( {{\text{V}} - {\text{x}} - {\text{y}}} \right)^{{{\text{m}} - 1}} \left( { - 1} \right)$$

(3)

$${\text{And}}\;\frac{{\partial \upphi \left( {{\text{B}},{\text{C}}} \right)}}{{\partial {\text{y}}}} = {\text{m thr}}\left( {\text{s}} \right) \, \left( {{\text{V}} - {\text{x}} - {\text{y}}} \right)^{{{\text{m}} - 1}} \left( { - 1} \right) \, + {\text{ m thr}}\left( {\text{C}} \right){\text{ y}}^{{{\text{m}} - 1}}$$

(4)

$${\text{Let}}\;{\text{D}}\left( {{\text{B}},{\text{C}}} \right) \, = \frac{{\partial^{ 2} \upphi \left( {{\text{B}},{\text{C}}} \right)}}{{\partial {\text{x}}^{ 2} }}\frac{{\partial^{ 2} \upphi \left( {{\text{B}},{\text{C}}} \right)}}{{\partial {\text{y}}^{ 2} }}\left[ {\frac{{\partial^{ 2} \upphi \left( {{\text{B}},{\text{C}}} \right)}}{{\partial {\text{x}}\partial {\text{y}}}}} \right]^{ 2}$$

$${\text{So}},\;{\text{D}}\left( {{\text{B}},{\text{C}}} \right) \, = {\text{ F}}\left( {{\text{B}},{\text{C}}} \right){\text{ m}}^{ 2} \left( {{\text{m}} - 1} \right)^{ 2}$$

(5)

$$\begin{aligned} {\text{F}}\left( {{\text{B}},{\text{C}}} \right) \, & = {\text{ thr}}\left( {\text{r}} \right){\text{thr}}\left( {\text{s}} \right){\text{x}}^{{{\text{m}} - 2}} \left( {{\text{V}} - {\text{x}} - {\text{y}}} \right)^{{{\text{m}} - 2}} \nonumber\\& \quad+ {\text{thr}}\left( {\text{r}} \right){\text{thr}}\left( {\text{C}} \right){\text{x}}^{{{\text{m}} - 2}} {\text{y}}^{{{\text{m}} - 2}} + {\text{thr}}\left( {\text{s}} \right)^{ 2} \left( {{\text{V}} - {\text{x}} - {\text{y}}} \right)^{{ 2 {\text{n}} - 4}} \nonumber\\ & \quad + {\text{thr}}\left( {\text{s}} \right){\text{thr}}\left( {\text{C}} \right){\text{y}}^{{{\text{m}} - 2}} \left( {{\text{V}} - {\text{x}} - {\text{y}}} \right)^{{{\text{m}} - 2}} - {\text{thr}}\left( {\text{s}} \right)^{ 2} \left( {{\text{V}} - {\text{x}} - {\text{y}}} \right)^{{ 2 {\text{n}} - 4}} \end{aligned}$$

(6)

$$\begin{aligned} {\text{i}}.{\text{e}}.\;{\text{F}}\left( {{\text{B}},{\text{C}}} \right) & = {\text{ thr}}\left( {\text{r}} \right){\text{thr}}\left( {\text{s}} \right){\text{x}}^{{{\text{m}} - 2}} \left( {{\text{V}} - {\text{x}} - {\text{y}}} \right)^{{{\text{m}} - 2}} \nonumber\\&\quad+ {\text{thr}}\left( {\text{r}} \right){\text{thr}}\left( {\text{C}} \right){\text{x}}^{{{\text{m}} - 2}} {\text{y}}^{{{\text{m}} - 2}} + {\text{thr}}\left( {\text{s}} \right){\text{thr}}\left( {\text{C}} \right){\text{y}}^{{{\text{m}} - 2}} \left( {{\text{V}} - {\text{x}} - {\text{y}}} \right)^{{{\text{m}} - 2}} \end{aligned}$$

(7)

$${\text{Therefore}},\;{\text{D}}\left( {{\text{B}},{\text{C}}} \right) \, = {\text{m}}^{ 2} \left( {{\text{m}} - 1} \right)^{ 2} \left( {{\text{thr}}\left( {\text{r}} \right){\text{thr}}\left( {\text{s}} \right){\text{x}}^{{{\text{m}} - 2}} \left( {{\text{V}} - {\text{x}} - {\text{y}}} \right)^{{{\text{m}} - 2}} + {\text{thr}}\left( {\text{r}} \right){\text{thr}}\left( {\text{C}} \right){\text{x}}^{{{\text{m}} - 2}} {\text{y}}^{{{\text{m}} - 2}} + {\text{thr}}\left( {\text{s}} \right){\text{thr}}\left( {\text{C}} \right){\text{y}}^{{{\text{m}} - 2}} \left( {{\text{V}} - {\text{x}} - {\text{y}}} \right)^{{{\text{m}} - 2}} } \right)$$

(8)

Since all three of thr(r), thr(s) and thr(C) are greater than 0, so D(B,C) > 0.

$$\begin{aligned} & {\text{Let}}\;{\text{E}}\left( {{\text{B}},{\text{C}}} \right) \, = \frac{{\partial^{ 2} \upphi \left( {{\text{B}},{\text{C}}} \right)}}{{\partial {\text{x}}^{ 2} }} \hfill \\ & {\text{i}}.{\text{e}}.\;{\text{E}}\left( {{\text{B}},{\text{C}}} \right) \, = {\text{ m}}\left( {{\text{m}} - 1} \right)\left\{ {{\text{thr}}\left( {\text{r}} \right){\text{x}}^{{{\text{m}} - 2}} + {\text{thr}}\left( {\text{s}} \right)\left( {{\text{V}} - {\text{x}} - {\text{y}}} \right)^{{{\text{m}} - 2}} } \right\} \hfill \\ \end{aligned}$$

(9)

So, E(B,C) > 0

For ϕ(B,C) to be minimum, the required conditions are

• (i) $\frac{{\partial \upphi \left( {{\text{B}},{\text{C}}} \right)}}{{\partial {\text{x}}}} = 0$

• (ii) $\frac{{\partial \upphi \left( {{\text{B}},{\text{C}}} \right)}}{\partial y} = 0$

• (iii) D(B,C) > 0 at the values of x and y solved using the conditions (i) and (ii) mentioned above

• (iv) E(B,C) > 0 at the values of x and y solved using the conditions i and ii mentioned above

Solving the conditions (i) and (ii) mentioned above, we get,

$${\rm{x}} = {\rm{V}}\left/\left( {\sqrt[{{\rm{m}} - {\rm{1}}}]{{\left( {{\rm{thr}}\left( {\rm{r}} \right)/{\rm{thr}}\left( {\rm{s}} \right)} \right)}} + \sqrt[{{\rm{m}} - {\rm{1}}}]{{\left( {{\rm{thr}}\left( {\rm{r}} \right)/{\rm{thr}}\left( {\rm{C}} \right)} \right)}} + {\rm{1}}} \right)\right.$$

(10)

$${\text{and y}} = {\rm{V}}\sqrt[{{\rm{m}} - {\rm{1}}}]{{\left( {{\rm{thr}}\left( {\rm{r}} \right)/{\rm{thr}}\left( {\rm{C}} \right)} \right)}}\left/\Bigg( {\sqrt[{{\rm{m}} - {\rm{1}}}]{{\left( {{\rm{thr}}\left( {\rm{r}} \right)/{\rm{thr}}\left( {\rm{s}} \right)} \right)}} + \sqrt[{{\rm{m}} - {\rm{1}}}]{{\left( {{\rm{thr}}\left( {\rm{r}} \right)/{\rm{thr}}\left( {\rm{C}} \right)} \right)}} + {\rm{1}}} \Bigg)\right.$$

(11)

It has already been proved that D(B,C) and E(B,C) both are greater than 0.

Let the corresponding positions of n_r and n_s are denoted as (Xr, Yr) and (Xs, Ys), respectively. Assuming that the current positions of n_B and n_C are (XB, YB) and (XC, YC), the values of Xr, Yr, Xs and Ys are calculated as,

$${\text{Xr}} = {\text{XB}} + \left( {{\text{XC}}{-}{\text{XB}}} \right){\text{x}}/{\text{V}}$$

(12)

$${\text{Yr}} = {\text{YB}} + \left( {{\text{YC}}{-}{\text{YB}}} \right){\text{x}}/{\text{V}}$$

(13)

$${\text{Xs}} = {\text{XB}} + \left( {{\text{XC}}{-}{\text{XB}}} \right)\left( {{\text{V}}{-}{\text{y}}} \right)/{\text{V}}$$

(14)

$${\text{Ys}} = {\text{YB}} + \left( {{\text{YC}}{-}{\text{YB}}} \right)\left( {{\text{V}}{-}{\text{y}}} \right)/{\text{V}}$$

(15)

3.3.2 Case-2: out gateway of B and in gateway of C are same

The shortest inter-cluster communication between two clusterheads say from B to C (where the out gateway of B and in gateway of C are same) will take place provided the following conditions satisfy:

• (iii) There is no supporting in gateway for C.

• (iv) The out gateway of B or the in gateway of C lie on the straight line connecting the heads of the clusters B and C. The reason is that, if the gateway deviates too much from that straight line, it will increase the path length the signal has to cover to reach the receiver from the transmitter. Increased distance will increase the energy consumption too.

The above mentioned conditions are pictorially shown in Fig. 4.

Fig. 4

Same out gateway of B and in gateway of C

The clusterheads of B and C are n_B and n_C, respectively. The out gateway of B is n_r. Let the distance between n_B and n_C is V, between n_B and n_r is x. Therefore, the distance between n_r and n_C, is (V − x). Also assume that the threshold receive power of any node n_i is thr(i).

As per the Friis equation, energy consumed in

• (i) n_B is (thr(r) x^m)

• (ii) n_r is (thr(C) (V − x)^m)

Therefore, the total energy consumed ϕ(B,C) is formulated as,

$$\upphi \left( {{\text{B}},{\text{C}}} \right) = {\text{thr}}\left( {\text{r}} \right){\text{x}}^{\text{m}} + {\text{thr}}\left( {\text{C}} \right)\left( {{\text{V}} - {\text{x}}} \right)^{\text{m}}$$

(16)

$$\frac{{{\text{d}}\upphi \left( {{\text{B}},{\text{C}}} \right)}}{\text{dx}} = {\text{m thr}}\left( {\text{r}} \right){\text{ x}}^{{{\text{m}} - 1}} + {\text{ m thr}}\left( {\text{C}} \right)\left( {{\text{V}} - {\text{x}}} \right)^{{{\text{m}} - 1}} \left( { - 1} \right)$$

(17)

$$\frac{{{\text{d}}^{ 2} \upphi \left( {{\text{B}},{\text{C}}} \right)}}{{{\text{dx}}^{ 2} }} = {\text{ m}}\left( {{\text{m}} - 1} \right)\left( {{\text{thr}}\left( {\text{r}} \right){\text{ x}}^{{{\text{m}} - 2}} + {\text{ thr}}\left( {\text{C}} \right)\left( {{\text{V}} - {\text{x}}} \right)^{{{\text{m}} - 2}} } \right)$$

(18)

For ϕ(B,C) to be minimum, the conditions to be satisfied are,

• (i) $\frac{{{\text{d}}\upphi \left( {{\text{B}},{\text{C}}} \right)}}{\text{dx}}$ is 0

• (ii) $\frac{{{\text{d}}^{ 2} \upphi \left( {{\text{B}},{\text{C}}} \right)}}{{{\text{dx}}^{ 2} }}$ is greater than 0

Solving (17) for x, we get,

$${\text{x}} = {\text{V}}/\left( {\sqrt[{{\text{m}} - 1}]{{\left( {{\text{thr}}\left( {\text{r}} \right)/{\text{thr}}\left( {\text{C}} \right)} \right)}} + 1} \right)$$

(19)

The value of (Xr, Yr) is calculated using (10) and (11).

3.4 Clustering strategy in FESC

The clustering strategy of FESC consists of deciding upon clusterhead status of a node, adding nodes to a cluster, deleting nodes from a cluster and merging of clusters. In order to become a clusterhead, a node should have at least one downlink neighbor.

3.4.1 Factors influencing the competency of a clusterhead

Please note that, if a node is a clusterhead, it cannot be an ordinary member of another cluster. On the other hand, a non-clusterhead node may be a member of more than one cluster. By declaring ownself as the clusterhead, if a node can substantially increase the number of clustered nodes in the network, then it is advantageous for the whole network. Even if a node does not have any non-clustered downlink neighbors, still it’s clusterhead declaration may facilitate inter-cluster connectivity. This is illustrated in Fig. 5a, b.

Fig. 5

a n_B is not a clusterhead yet. b n_B is a proud clusterhead now

It is evident from Fig. 5a that all three downlink neighbors of n_B belong to cluster C, so none of them depend on n_B. Therefore, those downlink neighbors of n_B are not supposed to receive messages from n_B, but from the head of cluster C. But, if n_B declares itself as the clusterhead and includes those three downlink neighbors as members, then head of cluster C will be able to receive messages from head of cluster A, since n_B can receive messages directly from the downlink neighbor n_p of the head of cluster A. n_B will forward that to its cluster members and one of those members embrace the head of cluster C within its radio-range. So, a new inter-cluster path from head of A to head of C, is formed. As soon as n_B decides to become a clusterhead they will be automatically included as members and they will act as gateways to cluster C, as shown in Fig. 5b. Claim of n_B will gain strength if it has sufficient residual battery life and small relative velocity with respect to downlink neighbors.

As far as election of a clusterhead is concerned, the clusterhead should have high residual energy, small relative velocity with respect to downlink neighbors, a good number of dependent downlink neighbors and good connectivity with other clusters. The components of good inter-cluster connectivity are connectivity from outside network to the elected clusterhead as well as connectivity from the elected clusterhead to other clusters. Also the gateways should be close to their optimum positions described above in this section, in order to preserve energy. For example, consider Fig. 6. There are three path options from communication between B and C. Among them, path option 1 is close to the optimum whereas path option 2 is inefficient since it involves more number of gateways than option 1 and even one supporting in gateway. Moreover, the gateways are at a higher distance from the straight line connecting the heads of the clusters B and C, compared to the gateway in path option 1. If only path option 2 remains available at any point of time, for communication from cluster B to cluster C then, the connectivity from B to C will be considered weak and existence of weak links does not increase the reputation of a node as the clusterhead. A node may be elected as clusterhead provided it is equipped with a good number of strong inter-cluster links (small number of gateways placed close to the straight line joining the node being considered, with other neighbor clusterheads).

Fig. 6

Electing a path from cluster B to C

3.4.2 Factors influencing the attachment of a node with a cluster

Strength of links plays an important role in attaching new nodes to the clusterheads, too. For example, consider Fig. 7a where initially the clusters A and B are not connected and a node n_p has newly arrived within the radio-range of the head of cluster A. Also note that n_p contains the head of cluster B within its radio circle. So, if n_p is included within the cluster A, a new inter-cluster route will be formed from cluster A to cluster B. This is greatly advantageous for the whole network. Figure 7b indicates the situation after inclusion of n_p into A. n_p is an out gateway of A now.

Fig. 7

a Before inclusion of n_p in cluster A. b After inclusion of n_p in cluster A

3.4.3 Merging of two clusters

Consider Fig. 8a. Initially the clusters A and B are completely disjoint. Gradually the head of cluster B begins to come close to A along with its members and a time comes when the head of B and all its members are embraced by the radio-circle of the clusterhead of A. In that case, the head of B looses it’s clusterhead status and the two clusters merge. This is seen in Fig. 8b. But if it happens that some cluster members of B remain out of A (as seen in Fig. 8c) then the competency of B will be re-evaluated depending upon the criteria mentioned above. If the head of B continues to prove itself worthy of remaining a clusterhead, then the two clusters won’t merge. But if the head of B is unable to remain a clusterhead, then it will loose it’s clusterhead status and become a member of A along with the members of B that has come within the radio-circle of head of A. The members of B outside A, will become non-clustered if they are not already attached to some clusters other than B.

Fig. 8

a Cluster B comes within cluster A. b Cluster B merges with cluster A. c At least one member of cluster B is out of A

3.4.4 Deleting a node from a cluster

A cluster member is deleted from a cluster only if the clusterhead looses it’s head status i.e. the cluster dissolves or the node moves out of the radio-range of the clusterhead.

4 Head_elector

Head_elector of a node n_i accepts certain input parameters and determines whether n_i can be clusterhead or not. The input parameters are resn(i), depn(i) and connect(i). The output produced is head_eff(i) which denotes competency of n_i as a clusterhead. If head_eff(i) is greater than a predefined threshold, then n_i declares itself as clusterhead to all of its downlink neighbors. Subsection 1 mathematically describes these parameters whereas rule bases are designed in the subsection 2.

4.1 Input parameters of head_elector

4.1.1 Current residual energy of n_i(resn(i))

The current residual energy of node n_i is denoted as resn(i) and formulated in (20). E_i and e_i denote the maximum battery power and battery power consumed so far, respectively, of node n_i.

$${\text{resn}}\left( {\text{i}} \right) \, = { 1 }{-}{\text{ e}}_{\text{i}} /{\text{ E}}_{\text{i}}$$

(20)

The values of resn(i) ranges between 0 and 1. Values close to 1 indicate that n_i has sufficient remaining battery power and it can efficiently handle the status of the clusterhead.

4.1.2 Dependent downlink neighbors of n_i(depn(i))

Let dn(i) be the present set of downlink neighbors of n_i and non-cls(i) be the set of non-clustered neighbors of the same node n_i. Then, definitely, non-cls(i) ⊆ dn(i). The non-clustered downlink neighbors of n_i will look for being attached to n_i. They are the dependent downlink neighbors of n_i.

$${\text{depn}}\left( {\text{i}} \right) = \left\{ {\begin{array}{*{20}l} 1 \hfill & {{\text{if }}\left| {{\text{non}}-{\text{cls}}\left( {\text{i}} \right) > 0} \right|} \hfill \\ 0 \hfill & {\text{otherwise}} \hfill \\ \end{array} } \right.$$

(21)

The values of depn(i) are 0 and 1. The value 1 indicate that some of downlink neighbors of n_i depend on n_i and so n_i should declare itself as clusterhead to do justice to them, especially if n_i’s inter-cluster connectivity is good.

4.1.3 Cluster stability of n_i based on mobility (mobs(i))

In order to form a more-or-less stable cluster, n_i should have small relative velocity with respect to its downlink neighbors. Without any loss of generality, we shall consider last v ACK messages sent by each member of non-cls(i) to n_i. Let p_trans(a) denotes the transmission power of n_a ∈ dn(i) and distt_l(a,i) is the distance between n_a and n_i as per the power of the signal l-th ACK (1 ≤l ≤ v) received by n_i from n_a. The l-th ACK of n_a is received by n_i with signal power p_recv(i,l). Also assume that the time difference between two consecutive ACK messages is tme. As per Frii’s transmission equation,

$${\text{p}}\_{\text{recv}}\left( {{\text{i}},{\text{l}}} \right) = {\text{p}}\_{\text{trans}}\left( {\text{a}} \right){\text{K}}/{\text{distt}}_{\text{l}}^{\text{m}} \left( {{\text{a}},{\text{i}}} \right)$$

(22)

$${\text{So}},\;{\text{distt}}_{\text{l}} \left( {{\text{a}},{\text{i}}} \right) = \sqrt[{\text{m}}]{{\left\{ {{\text{p}}\_{\text{trans}}\left( {\text{a}} \right){\text{K}}/{\text{p}}\_{\text{recv}}\left( {{\text{i}},{\text{l}}} \right)} \right\}}}$$

(23)

For $2\le {\text{l}} \le {\text{v}},{\text{ if distt}}_{\text{l}} \left( {{\text{a}},{\text{i}}} \right) < {\text{distt}}_{{{\text{l}} - 1}} \left( {{\text{a}},{\text{i}}} \right),{\text{ then }}\left( {{\text{distt}}_{\text{l}} \left( {{\text{a}},{\text{i}}} \right) \, - {\text{ distt}}_{{{\text{l}} - 1}} \left( {{\text{a}},{\text{i}}} \right)} \right) = 0$.

Then the relative mobility rmv(a,i) between n_a and n_i is given by,

$${\text{rmv}}\left( {{\text{a}},{\text{i}}} \right) = \sum\limits_{{{\text{l}} = 2}}^{\text{V}} {\left( {{\text{distt}}_{\text{l}} \left( {{\text{a}},{\text{i}}} \right) - {\text{distt}}_{{{\text{l}} - 1}} \left( {{\text{a}},{\text{i}}} \right)} \right)/\left( {{\text{tme}} \times {\text{v}} \times {\text{rad}}\left( {\text{i}} \right)} \right)}$$

(24)

where rad(i) is the radio range of n_i.

$${\text{Therefore}},\;{\text{mobs}}\left( {\text{i}} \right) = {{ 1- \left[ {\sum\limits_{{{\text{n}}_{\text{a}} \in {\text{dn}}\left( {\text{i}} \right)}} {{\text{rmv}}\left( {{\text{a}},{\text{i}}} \right)} \, } \right]} \mathord{\left/ {\vphantom {{ 1- \left[ {\sum\limits_{{{\text{n}}_{\text{a}} \in {\text{dn}}\left( {\text{i}} \right)}} {{\text{rmv}}\left( {{\text{a}},{\text{i}}} \right)} \, } \right]} {\left| {{\text{non-cls}}\left( {\text{i}} \right)} \right|}}} \right. \kern-0pt} {\left| {{\text{non-cls}}\left( {\text{i}} \right)} \right|}}$$

(25)

As per the formulation in (25), mobs(i) ranges between 0 and 1. If it is high, then the cluster of n_i will be stable and n_i can declare itself as the clusterhead.

4.1.4 Inter-cluster connection that will be available to n_i(connect(i))

Assume that, the set of neighbor clusters of n_i is given by nei-cls(i) and the set of two hop neighbors (uplink as well as downlink) of n_i is tdn(i). Let in-clus(i) be the set of downlink neighbors of n_i which are either directly connected to some clusterheads or through some gateways and if n_j ⊆ in-clus(i) then n_i ⊆ dn(j). These nodes will help to bring information inside the cluster of n_i. If n_j ⊆ in-clus(i), then assume that q_j is the set of clusterheads from which it can presently receive information either directly from the clusterhead or through gateways. On the other hand, out-clus(i) is the set of downlink neighbors of n_i which contain some clusterheads or predecessors of them within their own radio-ranges. Nodes like this will help to propagate information from the cluster of n_i to the rest of the network. If n_j ⊆ out-clus(i), then assume that u_j is the set of clusterheads that can receive information from n_i through n_j. If n_x ∈ q_j then, min-dist(x, j, i) is the minimum perpendicular distance of a gateway on the route from n_x to n_i through n_j, from the straight line connecting n_x and n_i. In the same way, max-dist(x, j, i) can be defined. It may be noted that here we are not interested in computing the deviations of the gateways from the optimum positions because the number of gateways for communication from the network (say, neighbor cluster A) to n_i, is virtually unlimited and in that case, it is not possible to compute optimum positions of all. Only we may say that for energy conservation and less delay in communication, the gateways must come down as close as possible, to the straight line connecting n_i with the neighbor cluster A.

$${\text{avg-dist(x}},{\text{j}},{\text{i)}} = ( {\text{min-dist(x}},{\text{j}},{\text{i)}} + {\text{max-dist(x}},{\text{j}},{\text{i))}}/ 2.$$

Similarly, n_x∈ u_j then, min-dist(i,j,x) is the minimum perpendicular distance of a gateway on the route from n_i to n_x through n_j, from the straight line connecting n_i and n_x. Therefore, max-dist(i,j,x) and avg-dist(i,j,x) can be computed easily.

Based on these information, connect(i) is formulated below.

$$\begin{aligned} {\text{connect}}\left( {\text{i}} \right) & = \left\{ {\begin{array}{*{20}l} 1 \hfill & {{\text{if}}\; {\text{nei-cls}}\left( {\text{i}} \right) = \emptyset \;{\text{and tdn}}\left( {\text{i}} \right) \ne \emptyset } \hfill \\ 0 \hfill & {{\text{if}}\;{\text{nei-cls}}\left( {\text{i}} \right) = \emptyset \;{\text{and tdn}}\left( {\text{i}} \right) = \emptyset } \hfill \\ {{\text{connect1}}\left( {\text{i}} \right) \times {\text{nei-imp}}\left( {\text{i}} \right)} \hfill & {\text{otherwise}} \hfill \\ \end{array} } \right. \\ {\text{connect1(i) }} & {\text{ = \{[in-connect(i) + out-connect(i)]/2\}}} \\ \end{aligned}$$

(26)

$${\text{in-connect}}\left( {\text{i}} \right) = \left( {{{ 1{-} 1} \mathord{\left/ {\vphantom {{ 1{-} 1} {\left( {\left| {{\text{in-distinct}}\left( {\text{i}} \right)} \right| + 1} \right)}}} \right. \kern-0pt} {\left( {\left| {{\text{in-distinct}}\left( {\text{i}} \right)} \right| + 1} \right)}}} \right)\left( {{{ 1{-} 1} \mathord{\left/ {\vphantom {{ 1{-} 1} {\left( {{\text{in-connect1}}\left( {\text{i}} \right) + 1} \right)}}} \right. \kern-0pt} {\left( {{\text{in-connect1}}\left( {\text{i}} \right) + 1} \right)}}} \right) \,$$

(27)

Similarly,

$${\text{out-connect}}\left( {\text{i}} \right) = \left( {{{ 1{-} 1} \mathord{\left/ {\vphantom {{ 1{-} 1} {\left( {\left| {{\text{out-distinct}}\left( {\text{i}} \right)} \right| + 1} \right)}}} \right. \kern-0pt} {\left( {\left| {{\text{out-distinct}}\left( {\text{i}} \right)} \right| + 1} \right)}}} \right)\left( {{{ 1{-} 1} \mathord{\left/ {\vphantom {{ 1{-} 1} {\left( {{\text{out-connect1}}\left( {\text{i}} \right) + 1} \right)}}} \right. \kern-0pt} {\left( {{\text{out-connect1}}\left( {\text{i}} \right) + 1} \right)}}} \right)$$

(28)

${\text{in-distinct}}\left( {\text{i}} \right) = \mathop \cup \limits_{{{\text{n}}_{\text{j}} \in {\text{in-clus}}\left( {\text{i}} \right)}} {\text{q}}_{\text{j}}$ and ${\text{out-distinct}}\left( {\text{i}} \right) = \mathop \cup \limits_{{{\text{n}}_{\text{j}} \in {\text{out-clus}}\left( {\text{i}} \right)}} {\text{u}}_{\text{j}}.$

$${\text{in}}-{\text{connect1}}\left( {\text{i}} \right)\left\{ {\begin{array}{*{20}l} {\left[ {(|{\text{in-clus(i)}}|/|{\text{dn(i)}}|) \left\{ {\prod\limits_{{{\text{n}}_{\text{j}} \in {\text{in}}-{\text{clus}}\left( {\text{i}} \right)}} {( 1 { }{-}{\text{ dist}}\_{\text{fn}}\_{\text{in}}\left( {{\text{i}},{\text{j}}} \right)/(|{\text{q}}_{\text{j}} | + 1)} } \right\}^{{ 1/|{\text{in}}-{\text{clus}}\left( {\text{i}} \right)|}} } \right]^{0. 5}} & {\text{if }} {\text{in-clus}}\left( {\text{i}} \right) \ne \emptyset \\ 0 & {\text{Otherwise}} \\ \end{array} } \right.$$

(29)

$${\text{out-connect1}}\left( {\text{i}} \right) = \left\{ {\begin{array}{*{20}l} {\left[ {(|{\text{out-clus(i)}}|/|{\text{dn(i)}}|) \left\{ {\prod\limits_{{{\text{n}}_{\text{j}} \in {\text{out-clus}}\left( {\text{i}} \right)}} {( 1 { }{-}{\text{ dist}}\_{\text{fn}}\_{\text{out}}\left( {{\text{i}},{\text{j}}} \right)/(|{\text{u}}_{\text{j}} | + 1)} } \right\}^{{ 1/|{\text{out-clus}}\left( {\text{i}} \right)|}} } \right]^{0. 5} } & {{\text{if out-clus}}\left( {\text{i}} \right) \ne \emptyset } \\ 0 & {\text{Otherwise}} \\ \end{array} } \right.$$

(30)

$$\begin{aligned} {\text{dist}}\_{\text{fn}}\_{\text{in}}\left( {{\text{i}},{\text{j}}} \right) & = \left[ { 1- \prod\limits_{{{\text{n}}_{\text{x}} \in {\text{q}}_{\text{j}} }} {\left\{ { 1/\left( {{\text{avg}}\_{\text{dist}}\left( {{\text{x}},{\text{j}},{\text{i}}} \right) + 1} \right)} \right\}} } \right]^{{( 1/|{\text{q}}_{\text{j}}|)}} \\ {\text{dist}}\_{\text{fn}}\_{\text{out}}\left( {{\text{i}},{\text{j}}} \right) & = \left[ { 1- \prod\limits_{{{\text{n}}_{\text{x}} \in {\text{u}}_{\text{j}} }} {\left\{ { 1/\left( {{\text{avg}}\_{\text{dist}}\left( {{\text{i}},{\text{j}},{\text{x}}} \right) + 1} \right)} \right\}} } \right]^{{( 1/|{\text{q}}_{\text{j}}|)}} \\ {\text{nei-imp}}\left( {\text{i}} \right) & = {{ 1{-}\left[ {\sum\limits_{{{\text{A}} \in {\text{nei-cls}}\left( {\text{i}} \right)}} {\left\{ {{\text{connect1}}\left( {\text{A}} \right)|_{{{\text{n}}_{\text{i}} \;{\text{is not a clusterhead}}}} /{\text{connect1}}\left( {\text{A}} \right)|_{{{\text{n}}_{\text{i}} \;{\text{is a clusterhead}}}} } \right\}} } \right]} \mathord{\left/ {\vphantom {{ 1{-}\left[ {\sum\limits_{{{\text{A}} \in {\text{nei-cls}}\left( {\text{i}} \right)}} {\left\{ {{\text{connect1}}\left( {\text{A}} \right)|_{{{\text{n}}_{\text{i}} \;{\text{is not a clusterhead}}}} /{\text{connect1}}\left( {\text{A}} \right)|_{{{\text{n}}_{\text{i}} \;{\text{is a clusterhead}}}} } \right\}} } \right]} {\left| {{\text{ nei-cls}}\left( {\text{i}} \right)} \right|}}} \right. \kern-0pt} {\left| {{\text{nei}}-{\text{cls}}\left( {\text{i}} \right)} \right|}} \\ \end{aligned}$$

(31)

connect1 is concerned with the own connectivity of n_i whereas nei-imp mathematically expresses the improvements produced by “I am a clusterhead” declaration of n_i. in-distinct(i) is the set of clusters from which n_i can receive messages without the involvement of other clusterheads. Similarly, out-distinct(i) is the set of clusters to which n_i can send messages without cooperation of other clusterheads. As in-distinct(i) increases, the capability of n_i to receive messages from different clusters, increase. Similarly, with increase in out-distinct(i), the capability of n_i to propagate its information to other clusters, increase. Please note that, one must distinguish between the situations where clusterhead n_i can receive message only from clusterhead n_j through four different gateway links and where n_i can receive messages from clusterhead n_j through two gateway links and clusterhead n_k through two gateway links. Definitely the second one is better because of the increased chance of inter-cluster connectivity. In the first situation n_i can communicate with n_j only whereas in the second situation n_i can communicate with both n_j and n_k.

Similarly the role of out-distinct of n_i can be explained. If four out gateways of n_i can send messages to another clusterhead n_j, it is better if two of them send the message to clusterhead n_j and other two to clusterhead n_k. In the mathematical expressions (27), (28), (29) and (30), 1 is added to the denominator to avoid division by zero. The expressions actually emphasize the fact that as far as inter cluster communications are concerned, it is always better to be connected with a huge number of clusterheads having multiple links with each of them where the gateways are placed very close to the straight line connecting the clusterheads. The situation (nei-cls(i) = ∅ and tdn(i) = ∅) indicates that n_i is isolated from the network whereas if (nei-cls(i) = ∅ and tdn(i) ≠ ∅) then there are high chances that some clusters will be formed around n_i in near future; at least the cluster is not a partitioned entity in the network. Like the earlier parameters of head_elector, connect(i) also ranges between 0 and 1. Values close to 1 show a very favorable inter-cluster communication scenario of n_i.

4.2 Fuzzy rule bases of head_elector

Table 1 describes the crisp ranges of the parameters of head_elector whereas Tables 2, 3 and 4 show their fuzzy combinations.

Table 1 Crisp range divisions of input parameters and fuzzy premise variables

Table 2 Fuzzy combination of resn and mobs producing t1

Table 3 Fuzzy combination of t1 and depn producing t2

Table 4 Fuzzy combination of t2 and connect producing head_eff

According to the discharge curves of batteries heavily used in ad hoc networks, at least 40% residual charge is required to remain in operable condition; 40–60% is satisfactory, 60–80% is good and more than that is more than sufficient to remain alive in the network and perform its tasks. Based on this information, 0–1 range of resn is divided into four sub-ranges as per Table 1. The parameters mobs and connect are divided in four uniform ranges between 0 and 1. A cluster is termed as an active cluster provided it’s connect is not a, i.e. the cluster is not detached from the network.

Table 2 presents the fuzzy combination of resn and mobs producing a temporary output t1. Both are given equal weight since both are equally indispensable for the sustainment of the cluster. In Table 3, t1 is combined with depn. When t1 = a, the node is either starving for charge or just operational and/or it’s link with the downlink neighbors is about to be broken. In both the cases it is absolutely unsuitable for acting as clusterhead, irrespective of its number of downlink members which are completely dependent on him i.e. which are not member of any other cluster. There is no point in electing a node as clusterhead which is about to die, even if it has got a huge number of non-clustered downlink neighbors, because the cluster will dissolve soon. The chance of being a clusterhead, is kept alive in Table 2 in three situations—t1 = c, depn = 1, t1 = d, depn = 1 (these situations symbolize the fact that the node is equipped with sufficiently high expected residual lifetime and low relative mobility with respect to downlink neighbors and also there are downlink neighbors depending on it), and t1 = d and depn = 0 (although there is no downlink neighbor depending on the current node but still, the node can declare itself as the clusterhead if it is equipped with high residual energy and low relative mobility with respect to potential cluster members; it can spend some of its energy to bridge the gap between its neighbor clusters). t2 is combined with connect in Table 4 producing the output head_eff of the fuzzy controller head_elector. A node can declare itself as head of its cluster provided head_eff is c or d.

In Table 4, if t2 = a, head_eff = a or b, even if connect is c or d. It symbolizes the situation that when a node is on the verge of death or just operational and/or moving far from its potential cluster members. Therefore, it cannot be a clusterhead even if it is connected to a huge number of clusterheads through gateways. When t1 = c or d, the node is capable of declaring itself as the clusterhead unless its inter cluster connectivity is very poor which is symbolized by connect = a. It is unnecessary to form a single hop cluster which is almost isolated from the network.

5 Affinity_detector

Let us assume that a node n_p has newly arrived within the vicinity of cluster A i.e. within the radio-range of the clusterhead n_A. Its inclusion in A is governed by a fuzzy-controller affinity_detector. Its input parameters are resn(p), aff(p,A), connect-impr(p,A) and clustered(p). The output produced is attach(p,A) which evaluates the attachment between n_p and A. If attach(p,A) is greater than a predefined threshold, then n_p is included as a member of A. Subsection 1 mathematically describes these parameters whereas rule bases are designed in the subsection 2.

The parameter resn is already described. aff measures connect-impr(p,A) is concerned with the enhancement in network connectivity that is produced by inclusion of n_p in A. The parameter clustered signifies that if n_p is not already attached to many clusters then it may be included in A.

5.1 Input parameters of affinity_detector

Among the parameters of affinity_detector, resn is described earlier. The other three are as follows.

Affinity with clusterhead of A with respect to mobility(aff(p,A))

$${\text{aff}}\left( {{\text{p}},{\text{A}}} \right) \, = { 1 } - {\text{ rmv}}\left( {{\text{p}},{\text{A}}} \right)$$

(32)

Increased value of aff will indicate small relative velocity with respect to n_p and clusterhead of A.

5.1.1 Connectivity improvement produced by n_p(connect-impr(p,A))

connect-impr(p,A) indicates the inter-cluster connectivity improvement that n_p brings to cluster A. It is formulated in (32), and the value ranges between 0 and 1, because inclusion of a node in a cluster can not break any existing link or deteriorate inter-cluster connectivity. If it is high or close to 1, it is highly recommended that n_p joins A because n_p has come with a gift of substantial inter-cluster connectivity. cluster(A) is the set of nodes belonging to a cluster head.

$${\text{connect-impr}}\left( {{\text{p}},{\text{A}}} \right) = 1{-}{\text{connect1}}\left( {\text{A}} \right)|_{{{\text{np}} \in {\text{cluster}}\left( {\text{A}} \right)}} /{\text{connect}}\left( {\text{A}} \right) 1|_{{{\text{np}} \in {\text{cluster}}\left( {\text{A}} \right)}}$$

(33)

5.1.2 With how many clusters n_p is attached (clustered(p))

Let ϕ(p) denote the set of clusters to which n_p is presently attached as member.

$${\text{Then}},\;{\text{clustered}}\left( {\text{p}} \right) = 1{-} 1/\upphi \left( {\text{p}} \right)$$

(34)

It is evident from (28) that clustered(p) ranges between 0 and 1. Values close to 0 denote that n_p is not presently attached to many clusters and so n_A should include it as member.

5.2 Fuzzy rule bases of affinity_detector

Crisp range of resn is presented in Table 1. Table 5 describes the crisp ranges of the parameters of affinity_detector whereas Tables 6 and 7 show their fuzzy combinations.

Table 5 Crisp range divisions of input parameters clustered and connect-impr and fuzzy premise variables

Table 6 Fuzzy combination of resn and aff producing t3

Table 7 Fuzzy combination of t3 and connect-impr producing t4

The parameters are divided in four uniform ranges between 0 and 1.

Table 6 combines resn and aff. Both are given equal weight, producing the temporary output t3. Table 7 presents the fuzzy combination of t3 and connect-impr generating the output t4. connect-impr has an impact when t3 is high; Small values of it (a or b) will diminish the value of t3 from c to b; from d to b when connect-impr = a. When t3 is low connect-impr is immaterial because the inter-cluster connection improvement that is produced by a node connected to the clusterhead through a weak wireless link, is negligible. t4 and clustered are united in Table 8 producing the output attach. The node is attached to the current cluster provided attach is c or d.

Table 8 Fuzzy combination of t4 and clustered producing attach

6 Simulation results

Simulation is performed using ns-2 [19] simulator. A number of $\wp$ nodes are deployed using a random number generator initialized by independent seeds. In simulation runs, value of $\wp$ has been varied from 10 to 100 (values being 10, 30, 50, 70 and 100). The transmission range is a random number between 10 and 50 cm. Each simulation runs for 1000 s. Each data point is presented as an average of 10 simulation runs. The nodes are placed uniformly at random locations in a rectangular universe of size 10 m × 10 m. Size of each grid cell has been assumed to be 10 m × 6 m. Network-wide node speed is varied between 0 to 50 cm/s.

Each node moves according to a random-waypoint mobility model in first 4 simulation runs, gaussian model in subsequent 4 and random walk model in last 4 runs. Under random waypoint model, each mobile node randomly elects one location in the simulation field as the destination. It then travels towards this destination with constant velocity chosen uniformly and randomly from [0,V_max], where the parameter V_max is the maximum allowable velocity for every mobile node. The velocity and direction of a node are chosen independently of other nodes. Upon reaching the destination, the node stops for a duration defined by the ‘pause time’ parameter denoted as T. If pause time is 0, this leads to continuous mobility. After this duration, it again chooses another random destination in the simulation field and moves towards it. The whole process is repeated again and again until the simulation ends. Here V_max and T are the two key parameters that determine the mobility behavior of nodes. If V_max is small and the pause time T is long, the topology of ad hoc network becomes relatively stable. On the other hand, if the node moves fast (i.e., V_max is large) and the pause time T is small, the topology is expected to be highly dynamic. Varying these two parameters, especially the V_max parameter, the random waypoint model can generate various mobility scenarios with different levels of nodal speed. The random walk model was originally proposed to emulate the unpredictable movement of particles in physics. It is also referred to as the Brownian Motion. Because some mobile nodes are believed to move in an unexpected way, random walk mobility model is proposed to mimic their movement behavior. The random walk model has similarities with the random waypoint model because the node movement has strong randomness in both models. Random walk model may be thought of as the specific random waypoint model with zero pause time. On the other hand in Gaussian model, the velocity of mobile node is assumed to be correlated over time and modeled as a Gauss-Markov stochastic process. Traffic model used is constant bit rate. Primary energy of each node ranges from 15 j to 25 j. The packet size is 512 bytes and the medium access protocol is IEEE 802.11. FESC is compared with other state-of-the-art single hop clustering protocols like WCA, TACA and LS-WCA. The parameters used for performance measurement are data packet delivery ratio, average node lifetime in seconds, rate of re-election of clusterheads, rate of change of cluster by members, and average delay in delivering a packet.

6.1 Explanation of results

As seen in Fig. 9, the data packet delivery ratio is FESC is much better compared to WCA, LS-WCA and TACA. The reason is that FESC provides much better inter-cluster connectivity. This parameter is given huge importance in election of clusterhead as well as attachment of nodes with the clusters. More number of routes is available between all pairs of clusterheads. Among these routes, the one with the maximum of minimum residual energy considering all the routers, is elected for inter-cluster communication. As a result, communication between multiple clusters is performed through the least energy consuming path. Also it may be noted that, residual energy is considered as a very important parameter in clusterhead election and deciding on attachment of nodes with the clusters. Therefore, FESC is much more energy efficient than all its competitors. This is evident from Fig. 9.

Fig. 9

Data packet delivery ratio vs. number of nodes

The factors that hamper stability of a cluster are small remaining lifetime of a clusterhead and its high relative velocity with respect to cluster members. These are given great importance in electing a clusterhead in FESC through the design of the fuzzy controller head_elector. This is similar to WCA and LS-WCA. But the additional positive aspect of FESC is that the clusterheads always try to communicate through a path which is very close to the straight line connecting them and involving a small number of gateways. This not only reduces the delay in communication but also preserves energy. Hence, the average node lifetime in FESC is much higher (Fig. 10) than the other clustering protocols mentioned here. But there exists another component of delay which is the number of cluster members. Since FESC does not impose any upper limit on the number of cluster members (unlike LS-WCA), the delay faced by FESC is higher than LS-WCA and close to WCA. The reason is that sometimes a huge number of cluster members introduce congestion, especially during intra-cluster communications. This is seen in Fig. 11.

Fig. 10

Average node lifetime

Fig. 11

Average delay in delivering a packet

Rate of re-election of clusterhead is much lesser in FESC (Fig. 12) due to the high average lifetime of nodes which includes clusterheads too. As far as the rate of change of cluster by members is concerned, FESC produces the best performance (Fig. 13) because it is greatly concerned with residual energy of a clusterhead and mobility relation between the new node and the head of that cluster. A node never attaches itself with a cluster whose head is on the verge of death or has high relative velocity with respect to the newcomer. Before joining a cluster, the new node always calculates how much stable its bond is going to be using the fuzzy controller affinity_detector. So more or less stable bonds are formed and the nodes need not change their clusters every now and then.

Fig. 12

Rate of re-election of clusterhead

Fig. 13

Rate of change of cluster by members

7 Conclusion

FESC is a single hop clustering scheme that produces more stable clusters compared to other state-of-the-art single hop clustering schemes. The nodes are equipped with fuzzy controllers using which they themselves can evaluate their competency as clusterhead and also measure the strength of wireless bond of a node with a cluster within whose vicinity it has just arrived. Also the optimum positions of gateways are computed for minimum energy communication between various clusters. The more close the gateways are to their respective optimum positions, the lesser will be the cost of inter-cluster communication. This is taken care of during selection of the optimum path for communication between different clusters. Also the inter-cluster route selected by FESC may not produce least delay, it definitely consumes least energy among all the available paths. Therefore, on an average, the lifetime of nodes increase substantially.