E-MCDA: Extended-Multilayer Cluster Designing Algorithm for Network Lifetime Improvement of Homogenous Wireless Sensor Networks

Abstract

The proposed idea in this paper is the constructive ramification of cluster designing mechanism floated in recently published work, multilayer cluster designing algorithm (MCDA) to ameliorate the performance in network lifetime. Novel algorithms for time slot allocation, minimizing the cluster head completion candidates, and cluster member selection∖node affiliation to cluster head play underpinning roles to achieve the target. These incorporations in MCDA result in minimizing transmissions, suppressing unfavorable response of transmissions and near-equal size and equal load clusters. We have done extensive simulations in NS2 and evaluate the performance of E-MCDA in energy consumption at various aspects of energy, packets transmission, number of designed clusters, number of nodes per cluster, and unclustered nodes. It is found that the proposed mechanism optimistically outperforms the competition with MCD and EADUC.

1. Introduction

Grouping of autonomous nodes in a centralized way to designate one node as head and other nodes as members is called clustering. Group is named cluster. Designated head is termed as cluster head and its member nodes are called as cluster members. If all the nodes in the network are of the same configuration (energy, computation power, memory, etc.) they are called homogenous nodes [1] and such network is named as homogenous network and, in case of different configuration, they are termed heterogeneous nodes [2] and the network is called heterogeneous network. Both types of networks have their distinguished challenges due to their unique peculiarities to be considered in protocol design [3]. In this paper, we are considering the homogenous wireless sensor network. In the clustered network, the process of designating a node as the cluster head, that is, CH election/selection, is usually the initial phase, while establishing the route for communicating the sensed/received data from the deployed sensors is usually its last phase [4]. But this sequence is not always the case. Figure 1 demonstrates these steps; those are usually part of protocol design for clustered network.

Figure 1

Steps in constitution of clustered network.

Hence, in clustered network architecture, nodes are designated at different roles. Figure 2 shows the possible states of a node during its lifetime depending upon the underlying clustering algorithm. Underlined node states in the figure are the part of every clustering algorithm. Clustered network is considered to be the most energy-efficient architecture due to its ease in route discovery, fault tolerance, data aggregation, and shortest possible end-to-end delay nature [5].

Figure 2

Statechart diagram of node in clustered network architecture.

Although cluster based network is a proven architecture for energy aware routing, the architectural setup of clustered network has self-support in the conservation of energy. Yet more attention is required to ameliorate the energy consumption aspect of its cluster designing process. Literature is rich in cluster based routing protocols that mostly encompasses cluster designing, route establishment, and cluster head rotation processes. Cluster designing, the core theme of this chapter, consists of cluster head selection, cluster member affiliation to cluster head, and time slot assignment for communicating the sensed data to CH. All the proposed algorithms for the same accomplish these processes either with central control of BS [6] or with locally controlled distributed style [7]. Both the techniques have their pros and cons.

In centralized cluster designing (CCD), the deployed nodes communicate the required decision parameter values (energy level, node degree (also called node density, i.e., number of nodes of a particular node), geographical location, and output of some decision metrics' calculation depending upon the underlying CCD algorithm) to the BS through either direct [8] or multihop using transient nodes [6] depending upon the network scale. Based on which cluster heads are elected in some algorithms affiliated cluster members are also elected. Figure 3 shows the centralized cluster designing approach where all the network nodes are communicating their information to the BS. BS elects the most suitable CH out of the received information and the decision is communicated to the elected CHs. CH then broadcasts its status. Listener nodes affiliate themselves to the most suitable CH. Proximity to CH, distance of CH to BS, energy, load, or the combination of these can be the affiliation decision parameters.

Figure 3

A typical centralized cluster designing (CCD) approach.

In local or distributed cluster designing (DCD) approach decision of CHs is made locally through various fashions as available in literature. The most prevailing style is exchanging the value of decision matric values (energy level, node degree, geographical location, and output of some decision metrics' calculation depending upon the underlying DCD algorithm) among neighboring nodes. The node which has the most optimal value among its neighbors is elected as CH. Another style is random selection based on logical comparison of generated random value in $[\mathrm{0,1}]$ with some calculated probability [9–11]. Elected CH advertises Join_Request packet. Recipient nodes make the joining decision depending upon proximity to CH, distance of CH to BS, energy of CH, load on CH, or the combination of these.

In spite of various advantages of each of the techniques, one drastic energy squeezing common disadvantage of the two is too much broadcasting especially in large networks as well as message exchange until some final decision is made. So, a hybrid solution exploiting the pros of distributed and centralized cluster designing approaches and escaping the cons of both these techniques is highly appreciable. One such effort is seen in [12] for adding more life to the clustered network which increases its more attractiveness for the researchers. Usually the route establishment process starts after cluster designing. Figure 4 is portraying this style of cluster designing in a more elaborative way. Our proposed algorithm, E-MCDA, falls in the former category. But here in this paper our goal is to highlight the cluster designing part of E-MCDA. Moreover, assumptions made for homogeneity of nodes, communication radius model, reliability of communication link, communication neighbor set, and of network nodes are the same as explained in [12]. Contribution of our research work in this paper is summarized as follows:

• (i)

In the extended version of cluster designing idea presented in MCDA, we have introduced $T_{wait(t_i)}$ parameter that has the following benefits and also a scenario for better demonstration of clustering layer design in E-MCDA is depicted, explained, and discussed:

• (a)

Minimizing the message broadcast during selection of decision maker nodes ${Node}_{(dm)}$ and also in the election of cluster heads.

(b)

Incorporation of $T_{wait(t_i)}$ in clustering layer designing significantly modifying the proposed solution in MCDA that makes clear difference in E-MCDA from MCDA.

(ii)

In cluster member selection phase of E-MCDA, we have introduced a new “node∖member affiliation algorithm” that is aiming to design near-equal size clusters and hence with near-equal load. Also a scenario for better demonstration of cluster member selection in E-MCDA is depicted, explained, and discussed.

The rest of the paper is organized as follows. Some of the closely related and state-of-the-art cluster designing approaches are discussed in Section 2 in detail. The assumptions made about our network and simulation model are presented in Section 3. Definitions relating to our presented work are also given in the same section. Proposed extended-multilayer cluster designing algorithm (E-MCDA) is given in Section 4. Working of E-MCDA for network lifetime improvement of homogenous wireless sensor network is presented in the same section. Section 4 explains the comparative analysis of the proposed solution with two protocols; one is the protocol having parent idea presented in E-MCDA and the other is EADUC backing with detailed simulation based results depicted in graphs. Conclusions and future works are given in the subsequent sections followed by Acknowledgments and references.

Figure 4

A typical distributed cluster designing (DCD) approach.

2. Related Work

In the subsequent paragraphs of this section, we are going to present related proposed solutions for cluster designing from different state-of-the-art articles of their time.

Hybrid Energy-Efficient Distributed (HEED) clustering [13], introduced by Younis and Fahmy, is a multihop WSN clustering algorithm which brings an energy-efficient clustered routing with explicit consideration of energy. Different from LEACH in the manner of CH election, HEED does not select nodes as CHs randomly. The manner of cluster construction is performed based on the hybrid combination of two parameters. One parameter depends on the node's residual energy, and the other parameter is the intracluster communication cost. In HEED, elected CHs have relatively high average residual energy compared to member nodes. Additionally, one of the main goals of HEED is to get even-distributed CHs throughout the networks. Moreover, despite the phenomena that two nodes, within each other's communication range, become CHs together, the probability of this phenomena is very small in HEED. In HEED, CHs are periodically elected based on two important parameters: residual energy and intracluster communication cost of the candidate nodes. Initially, in HEED, a percentage of CHs among all nodes, CH prob, is set to assume that an optimal percentage cannot be computed a priori. The value of CH prob, however, is not allowed to fall below a certain threshold. Afterwards, each node goes through several iterations until it finds the CH. If it hears from no CH, the node elects itself to be a CH and sends an announcement message to its neighbors. Each node doubles its CH prob value and goes to the next iteration until its CH prob reaches 1. Therefore, there are two types of statuses that a sensor node could announce to its neighbors: tentative status and final status. If its CH prob is less than 1, the node becomes a tentative CH and can change its status to a regular node at a later iteration if it finds a lower cost CH. If its CH prob has reached 1, the node permanently becomes a CH. In HEED, every node elects the least communication cost CH in order to join it. On the other hand, CHs send the aggregated data to the BS in a multihop fashion rather than single-hop fashion of LEACH.

Yang and Lee [7] have proposed a distributed reclustering routing protocol, Predictive and Adaptive Routing Protocol using Energy Welfare (PARPEW). PARPEW incorporates the concept of energy welfare (EW) and tries to achieve both energy efficiency and energy balance simultaneously. At the beginning of each round, the base station starts the round and broadcasts the TDMA schedule to every node. The TDMA schedule specifies the time slots assigned to each live node to avoid packet collision in the cluster setup stage. PARPEW operates in each round in two stages: the cluster setup stage and steady-state stage. In the cluster setup stage, clusters are formed and CHs are selected. In the steady-state stage, sensors collect data and send it to their corresponding CHs. The CHs then aggregate the data and transfer it to the base station. First cluster is formed then cluster head is designated.

How all this process works is as follows:

• (1)

p value (percentage of cluster head nodes).

(2)

α value (an inequality aversion parameter, which signifies the strength of society's penalty for inequality and usually ranges from 1.5 to 2.5).

Each of the network nodes generates a random number between 0 and 1; if the generated random number is less than the p value, then the node elects itself as the temporal cluster head.

Each selected temporal cluster head broadcasts its status. The recipient nodes join themselves to the closest temporal cluster head based on the signal strength. Each node of the cluster communicates its predictive residual energy after transmission (EAT) and its location information at least if the distance matrix is not available to the temporal cluster head. Using EAT and aversion parameter, energy welfare (EW) function is calculated for each of the cluster nodes. The node having the highest EW value is designated as the real CH. Assigning the time slots based on TDMA to the cluster members to communicate with real cluster head is performed by temporal cluster head.

Multilayer cluster designing algorithm for lifetime improvement of wireless sensor network, MCDA, by Jabbar et al. [12] is a hybrid approach in its communication architecture (CA) perspective and architectural design (AD) perspective. MCDA uses multilayered approach comprising first-flat layer in the footprint of base station and the subsequent clustered layers. Designing of former layer is initiated centrally whilst distributed fashion is applied in the designing of later. The deployed nodes in flat layer are termed as first-layer nodes $({Node}_{L_1})$ . Authors started the network clustering from 2nd layer up to network boundary. The cluster heads in the 2nd layer are selected by the elected decision maker nodes of first layer. Neighbor counter (for preferring one node over others for selection of various positions (decision maker, cluster head) at various steps), decision maker node (nodes for selection of cluster heads from the subsequent layer), and packet sequence ID with postfix counter (packet ID for grouping of nodes and preferring one node over others from that group for becoming CH) are the key factors in designing the clusters. Second layer nodes $({Node}_{L_2})$ elect the node with the highest node density (node degree) as their decision maker node $({Node}_{(dm)})$ ; that is, ${Cnt}_{n_i}>{Cnt}_{n_j}{\forall }_i$ and $j=\mathrm{1,2},3,\dots ,n$ and n is equal to all nodes with same sequence number belonging to same group. Second layer nodes $({Node}_{L_2})$ communicate their nodal density $({Cnt}_{n_i})$ on their turn to their ${Node}_{(dm)}$ to take part in competition of becoming CH. Time slots are assigned to these nodes based on Time Division Multiple Access (TDMA) technique. When the first node of ${Node}_{L_2}$ communicates its nodal density $({Cnt}_{n_1})$ to ${Node}_{(dm)}$ , it assigns sequence number $({Pkt}_{(Seq\_no)})$ with postfix counter “0” to these packets. All the recipient nodes of ${Node}_{L_2}$ save this ${Pkt}_{(Seq\_no)}$ and become part of the same group. All the nodes having packet with the same ${Pkt}_{(Seq\_no)}$ are included in the same group. Only those nodes of a group communicate their ${Cnt}_{n_i}$ to ${Node}_{(dm)}$ which have highest nodal density than their previous nodes. These nodes increment the postfix counter giving twofold advantages: (i) to let the other member nodes of the same group know about their ${Cnt}_{n_i}$ and (ii) to let the nonmember nodes know that neither they should continue this postfix counting nor they should save any info of other group's member nodes. This postfix counter assists the ${Pkt}_{\left(Se{q}_{no}\right)}$ in separating the members of one group from others. The node right after the last member of first group communicates with its ${Node}_{(dm)}$ and assigns the new ${Pkt}_{\left(Se{q}_{no}\right)}$ with postfix counter “0.” After collecting the nodal density of 2nd layer's selected nodes, the decision maker nodes elect the CH having highest nodal density among its 2nd layer's addressed nodes. The elected cluster heads broadcast “Join Request” packets. This is to inform other sensor nodes of its availability as CH. Recipient nodes send their consent message in the form of “join accept” message to become the cluster members. If “join Request” message is received from more than one CH then decision of membership is based on the current load on CH, that is, CH having less number of member nodes is preferred to be attached to. Comparative analysis of discussed clustering algorithm on various parameters is given Table 1.

Table 1

Comparative analysis of discussed clustering algorithm on various parameters.

	[7]	[12]	[14]	[15]
Node type	Both	Homogenous	Both	Homogenous
Comm. to sink	Multihop	NA	Multihop	Multihop
Cluster size	Unequal	Near-equal	Unequal	Unequal
Cluster designing	Distributed	Hybrid	Distributed	Distributed
Suitability to network size	Small	Large	Large	Large
CH election criteria	Residual energy (RE) and distance	Node density	Ratio of avg. RE of neighbor nodes and RE of node itself	Residual energy
Intercluster comm. style	CH to CH	NA	CH to max energy CH	CH to CH
Intracluster comm. style	NA	NA	Direct	Direct
Power adjustment	Dynamic	Static	Dynamic	Dynamic
Cluster head rotation	On each round	NA		On each round

Proposed mechanism, Energy Aware Distributed Unequal Clustering (EADUC) by Yu et al. [14], is an energy aware routing algorithm for cluster based wireless sensor network. They introduced unequal sized clusters for the remedy of hot spot issue that results in better network lifetime. Designing of clustering topology comprises neighbor node information collection phase, cluster head competition phase, and cluster formation phase constituting setup phase. Each phase is given a specific duration, that is, $T_{\mathrm{1}}$ , $T_{\mathrm{2}}$ , and $T_{\mathrm{3}}$ . Next to it is the data transmission phase. To start the cluster formation process, the BS broadcasts a signal at a certain power level. Each node can compute its approximate distance to the BS based on the received signal strength. In first phase, each node broadcasts a Node_Msg message within its radio range r having node ID and its residual energy $E_r$ . Based on collected information, each node calculates average residual energy of its neighbor nodes. Next calculation is of waiting time t using the following formula:

$$\begin{array}{cc}& t=\left\{\begin{array}{cc}\frac{E_a}{E_r}{T}_{\mathrm{2}}{V}_r,\hfill & E_r\ge E_a\hfill \\ T_{\mathrm{2}}{V}_r,\hfill & E_r{E}_a,\hfill \end{array}\right.\end{array}$$

(1)

where $V_r$ is a real value randomly distributed in $[\mathrm{0.9,1}]$ which is introduced to reduce the probability that two nodes send Head_Msgs at the same time. Each node waits until this calculated time prior to broadcast Head_Msg message.

To start cluster head selection competition phase, each node compares its average residual energy to its neighbor's calculated average residual energy and decides to be cluster head or not. After waiting for calculated t time, decision for the nodes to be cluster head is broadcasted within their calculated radio range. If a node does not receive any Head_Msg message until the expiry of its time t, then it broadcasts the Head Msg within radio range $R_{C_i}$ to advertise that it will be a cluster head.

Since the competition radius $R_C$ determines the size of cluster that is based on the proximity to the BS. Each node calculates its own value for $R_C$ using the following formula:

$$\begin{array}{cc}& R_C=\left[\mathrm{1}-\alpha \frac{d_{\mathrm{m}\mathrm{a}\mathrm{x}}-d\left(s_i,BS\right)}{d_{\mathrm{m}\mathrm{a}\mathrm{x}}-d_{\mathrm{m}\mathrm{i}\mathrm{n}}}-\beta \left(\mathrm{1}-\frac{E_r}{E_{\mathrm{m}\mathrm{a}\mathrm{x}}}\right)\right]R_{\mathrm{m}\mathrm{a}\mathrm{x}},\end{array}$$

(2)

where $d_{\mathrm{m}\mathrm{a}\mathrm{x}}$ and $d_{\mathrm{m}\mathrm{i}\mathrm{n}}$ are the maximum and minimum distances from the nodes in the network to the BS, $d(s_i,BS)$ is the distance from node $s_i$ to the BS, α and β are weighted factors in $\left[\mathrm{0,1}\right]$ , and $R_C^0$ is the maximum value of competition radius. This makes the cluster size bigger for farther elected cluster head and smaller for nearer elected cluster head. Each noncluster head node chooses the nearest cluster head and sends the Join_Msg which contains the ID and residual energy of this node. Authors also modify this technique for heterogeneous networks by introducing energy factor in radio range competition radius in order to maximally exploit the higher energy nodes.

A very similar mechanism for energy-efficient routing in clustered wireless sensor network and to target the hot spot issue is given in [15], where Li et al. have proposed an Energy-Efficient Unequal Clustering (EEUC) mechanism for periodical data gathering applications in wireless sensor networks. It wisely organizes the network via unequal clustering and multihop routing. EEUC is a distributed competitive algorithm, where cluster heads are elected by localized competition. First-tentative cluster heads (TCHs) are selected with the predefined probability T. This style of selecting the cluster head is the same as in LEACH where in the start all the deployed nodes are designated as cluster heads. Each tentative cluster head calculates $R_{comp}$ , that is, competition radius (a function of node's distance to the base station). Broadcast range of the tentative cluster heads to define their neighbor area of competition for becoming final cluster head is fixed by $R_{comp}$ value. $R_{comp}$ also dictates the cluster heads with higher residual energy and farther away from the BS to design larger cluster areas as compared to the CH closer to the BS which have smaller clusters. In order to complete the calculation for its maximum competition radius, that is, $S_i$ . $R_{comp}$ , each node must be communicated with the $d_{\mathrm{m}\mathrm{a}\mathrm{x}}$ (maximum distance from the BS) and $d_{\mathrm{m}\mathrm{i}\mathrm{n}}$ (minimum distance from the BS) by the BS. Each tentative cluster head communicates its ${Node}_{id}$ and $RE$ (Residual Energy) value to its neighbor nodes. Thus each TCH prepares its neighbor set, $S_{CH}$ . If the recipient node has the highest $RE$ value among all the received values then it broadcast $FINAL\_HEAD\_MSG$ to propagate its status as cluster head. If it receives another $FINAL\_HEAD\_MSG$ from any other node from its neighbors, then it just broadcasts a $QUIT\_ELECTION\_MSG$ . The noncluster head nodes join the CH based on their closeness to it.

3. Proposed Solution: Extended-MCDA (E-MCDA)

Any clustering algorithm normally comprises three phases, namely, setup phase, steady phase, and routing phase. The first one is related to cluster designing where all communication process works for cluster designing. In literature, this phase comprises CH election/selection, CM selection, and route establishment. This phase is called offline phase or passive phase since all messaging is of control packets and no data is traversed in the network. The other phases come in operational or active phases and data is actually in the network for aggregation and routing. The proposed mechanism, E-MCDA, in the above context is explained in the subsequent paragraphs with comprehensive representation in the form of figures (Figures 5–12) and in the form of tables (Tables 2–6). The said phase of cluster designing is comprised of three steps: self-organizing, flat layer design, and clustered layers design.

Table 2

Representation of ${Msg}_{({CL}_{init})}$ messages by ${Node}_{L_1}$ recipient nodes from ${Node}_{L_2}$ .

Selected nodes from ${Node}_{L_1}$	Waiting time for group of recipient nodes of ${Msg}_{({CL}_{init})}$ message $T_{wait\left(t_i\right)}$	${Msg}_{({CL}_{init})}$ message recipient nodes' group
Y	1200 μs	$f,g,i$ , k, l, a, w
Z	7500 μs	$$\mathbf{a},\mathbf{k},\mathbf{l},\mathbf{w},\mathbf{m},\mathbf{n}$$
U	450 μs	$$\mathbf{w},\mathbf{m},\mathbf{n},y,p,o,r,q,v$$

Table 3

Representation of ${Node}_{L_2}$ that receive multiple ${Rqst}_{{DM}_{Elec}}$ messages from ${Node}_{L_1}$ .

Nodes receiving ${Msg}_{({CL}_{init})}$ messages from
Y and Z	Z and U
$$k,l,a,w$$	$$w,m,n$$

Table 4

Calculation for net waiting time $T_{ne{t}_{wait}}$ for ${Node}_{L_2}$ for energy aware designing of clusters at 2nd layer (the node having the lowest net node degree ${Net\_Cnt}_{n(i)}$ has the highest net waiting time $T_{ne{t}_{wait}}$ value and vice versa).

$$Node\_ID$$	ith node degree ${(Cnt}_{n_i})$	Neighbor from ${Node}_{L_{\mathrm{1}}}$	$${Ne{t}_{Cnt}}_{n(i)}$$	$$T_{c{h}_{elec}}=\mathrm{1}-{\log }_{\mathrm{10}}{(Ne{t}_{Cnt}}_{n(i)})$$	$${T_{ne{t}_{wait}}}^{\ast }=T_{c{h}_{elec}}+T_{wait}$$
f	6	2	4	0.397940009	1650.39794
g	5	1	4	0.397940009	1650.39794
h	6	2	4	0.397940009	1650.39794
i	7	2	5	0.301029996	1650.30103
j	5	1	4	0.397940009	1650.39794
k	4	2	2	0.698970004	1650.69897
l	8	2	6	0.22184875	1650.221849
m	6	2	4	0.397940009	1650.39794
w	7	2	5	0.301029996	1650.30103
n	6	2	4	0.397940009	1650.39794
y	7	1	6	0.22184875	1650.221849
p	6	1	5	0.301029996	1650.30103
o	8	1	7	0.15490196	1650.154902

${}^{\ast }{T}_{wait}=T_{c{h}_{elec}}+\mathrm{\hspace{0.17em}\hspace{0.17em}}\left(T_{es{t}_{tx}}+T_{GI}\right)\times {Cnt(Node}_{L_{\mathrm{1}}})=T_{c{h}_{elec}}+\left(\mathrm{128}\hspace{0.17em}\mu \text{s}+\mathrm{25}\hspace{0.17em}\mu \text{s}\right)\times \mathrm{11}$ .

Table 5

Function of proposed scheme for affiliation of nodes at intersection of communication range of more than one CH.

Steps	$${Cntr}_{n(f)}$$	$${Cntr}_{n(l)}$$	$${Cntr}_{n(o)}$$	Nodes at intersection of
				f and l	l and o
1	6	8	7	i, j	m, n
2	6	7	7	j	m, n
3	6	7	6	j	n
4	6	6	6	0	n
5	6	5	6	0	0

Table 6

Comparison of simple and proposed technique for “decision parameter” for affiliation of nodes at intersection of communication range of more than one CH.

	CH affiliation decision parameter
	Simple	Improved/proposed
$${Cntr}_{n(f)}$$	6	6
$${Cntr}_{n(l)}$$	4	5
$${Cntr}_{n(o)}$$	7	6
Sample variance	2.33	0.33
Performance efficiency of proposed method over simple method		86%

Figure 5

Self-organizing step in E-MCDA and its exploitation for working of other steps in successful designing of energy aware wireless sensor network architecture.

Figure 6

Formation of first layer.

Figure 7

Depiction of calculation of $\Delta t_n$ and $T_{wait(t_i)}$ .

Figure 8

Election of first-cluster head in 2nd layer.

Figure 9

Step 1: completion of clustering process in 2nd layer having one cluster highlighted with node “f” as cluster head.

Figure 10

Nodes at intersection area (highlighted in dark grey).

Figure 11

Step 2: completion of clustering process at layer 2 with resolving of “nodes at intersection” issue.

Figure 12

Sample variance of competing algorithms on equality of cluster size.

3.1. Self-Organizing

When the nodes are deployed either uniformly or randomly, after switching on their active mode, they just give a blink and broadcast a beacon message to show their existence. Neighboring nodes receive their beacon messages, set up their neighbor tables, calculate the link quality, or do necessary calculations for any future decision making depending upon the underlying algorithm. The energy consumption during this self-organizing process is usually almost the same for all the routing/working algorithms for the same size of network and is not considered in the calculation of total energy consumption. We also will not be considering this energy consumption for finalizing the result in our results producing section. The capabilities of this self-organizing are widely exploited by exchanging the node status (location, energy level in case of heterogeneous network). E-MCDA sets up neighbor table at each deployed node by just placing the neighbor count in it rather than all the info of neighbor nodes.

This saves the resources. Since BS is also the listener of ongoing communication of nodes in its neighbor during the self-organizing phase, it also has the node density value with it to be used later for cluster designing process. Figure 5 shows the typical functionalities of self-organizing phase along with example neighbor table in E-MCDA.

3.2. Flat Layer Design

One of the main issues that are usually mentioned in the context of multihop routing process is frequent depletion of energy of nodes that are deployed in the neighbor of base station. This region is usually named as hot spot region of network. In the clustered network, the neighbor clusters of BS are overloaded due to being intermediate points of all paths approaching from different sources to BS. For the remedy of this all-time issue in clustered network, our novel idea is an energy aware contribution in literature of cluster designing. For now, in this chapter, our concentration is on lessening the energy consumption during cluster designing process. If the cluster designing fashion of LEACH [8] and its successors, that is, V-LEACH [9], TL-LEACH [10], C-LEACH [11], and so forth, is followed, then the energy consumption would be drastically high since every node of the network takes part in cluster designing process until cluster head is elected. Also the frequent rotation of cluster heads would be another additive danger to the network lifetime [14]. To cope with all these dangers facing cluster designing especially, our introduced strategy in extended-MCDA gives suitable solutions for these issues. The nodes which are in the communication range of BS do the direct transmission to BS and are considered as the neighbor nodes of BS. These neighbor nodes do not become the part of any cluster and are remained unclustered.

This tier is named as flat layer and deployed nodes in this layer are termed first-layer nodes ${Node}_{L_1}$ . All nodes broadcast beacon message $(Msg\left(Beacon\right))$ piggybacked with the information of their number of neighbors. With this, all recipient nodes including BS set up their neighbor table containing node ID and number of neighbors. BS broadcasts setup initialization message $({Msg}_{\left(setu{p}_{init}\right)})$ to initiate the cluster designing process. Recipient nodes are designated as first-layer nodes $({Node}_{L_1})$ . ${Node}_{L_1}$ send their number of neighbors excluding their neighbors that are not from ${Node}_{L_1}$ , that is, ${Nodes}_{(rem)}$ . Now the BS assigns the node IDS to ${Node}_{L_1}$ according to their ${Nodes}_{(rem)}$ value. Total time slots allocated to the ${Node}_{L_1}$ , that is, $({Total}_{TS})$ , is calculated by BS as follows:

$$\begin{array}{cc}& \Delta t_i=\Delta t_{i-\mathrm{1}}+\Delta t\\ \Delta t=\left(T_{es{t}_{tx}}+T_{GI}\right)\\ {Total}_{TS}={\displaystyle \sum }_{i=\mathrm{1}}^n\Delta t_n+\Delta t.\end{array}$$

(3)

Now, ultimately, BS broadcasts flat layer initialization message $({Msg}_{\left({FL}_{init}\right)})$ to formally initiate the designing of clustered network. ${Msg}_{({FL}_{init})}$ contains ${Total}_{TS}$ , $\Delta t$ , and newly allocated ${Node}_{ids}$ . Recipient nodes of ${Msg}_{({FL}_{init})}$ calculate $T_{wait(t_i)}$ as in

$$\begin{array}{cc}& T_{wait\left(t_i\right)}={Total}_{TS}-\Delta t_i\hspace{0.17em}\hspace{0.17em}\mathrm{o}\mathrm{r}\hspace{0.17em}\hspace{0.17em}{Total}_{TS}-\left(\Delta t\times i\right)\end{array}$$

(4)

$T_{wait(t_i)}$ helps in minimizing the message broadcast during selection of ${Node}_{(dm)}$ and also in the election of cluster heads by suppressing the turn of nodes with equal and lower degree in taking part in said-processes since the decision for the same is based on the highest node degree that has already been done.

To initiate the clustering process in the second layer nodes ${(Node}_{L_2})$ , clustering layer initialization message $({Msg}_{({CL}_{init})})$ that has the information of $T_{wait(t_i)}$ and ${Cnt}_{n_i}$ is broadcasted to ${Node}_{L_2}$ .

Refer to Figure 6; there are $\mathrm{11}$ nodes in the footprint of BS to receive this message and thus are comprising first layer. ${Msg}_{({FL}_{init})}$ message consists of 128 bits and transmission time for a packet is $\mathrm{128}\hspace{0.17em}\mu \mathrm{s}/\mathrm{p}\mathrm{a}\mathrm{c}\mathrm{k}\mathrm{e}\mathrm{t}(\mathrm{m}\mathrm{e}\mathrm{s}\mathrm{s}\mathrm{a}\mathrm{g}\mathrm{e})$ . If $\Delta t$ is the time slot allocated to a node which consists of estimated transmission time $T_{es{t}_{tx}}$ and the safe gap in the transmission of next node called guard interval $T_{GI}$ , then first node from ${Node}_{L_1}$ is allocated $\Delta t_1$ , that is, equal to $\Delta t$ as in

$$\begin{array}{cc}& \Delta t=\left(T_{es{t}_{tx}}+T_{GI}\right)=\left(\mathrm{128}+\mathrm{25}\right)\mu \text{s}=\mathrm{153}\hspace{0.17em}\mu \text{s}.\end{array}$$

(5)

The next allocated time starts right after the completion of this $\Delta t_1$ and so on. Calculation for the same is given as follows based on $\Delta t_i=\Delta t_{i-1}+\Delta t$ :

•  

  Let $i=\mathrm{1}$ and $\Delta t_{\mathrm{0}}=\mathrm{0}$ ,

 

If $i=\mathrm{2}$ and $\Delta t_{\mathrm{1}}=\mathrm{153}\hspace{0.17em}\mu \mathrm{s}$ ,

•  

then $\Delta t_{\mathrm{2}}=\Delta t_{\mathrm{1}}+\Delta t=\left(\mathrm{153}+\mathrm{153}\right)\hspace{0.17em}\mu \mathrm{s}=\mathrm{306}\hspace{0.17em}\mu \mathrm{s}$ .

 

If $n=i$ and $\Delta t_{\mathrm{1}}=\mathrm{306}\hspace{0.17em}\mu \mathrm{s}$ ,

•  

then $\Delta t_{\mathrm{3}}=\Delta t_{\mathrm{2}}+\Delta t=\left(\mathrm{306}+\mathrm{153}\right)\hspace{0.17em}\mu \mathrm{s}=\mathrm{459}\hspace{0.17em}\mu \mathrm{s}$ .

 

⋮

 

Similarly, if $i=10$ and $\Delta t_1=1377\hspace{0.17em}\mu \mathrm{s}$ ,

•  

then $\Delta t_{\mathrm{10}}=\Delta t_{\mathrm{9}}+\Delta t=\left(\mathrm{1377}+\mathrm{153}\right)\hspace{0.17em}\mu \mathrm{s}=\mathrm{1530}\hspace{0.17em}\mu \mathrm{s}$ .

 

And if $i=\mathrm{11}$ and $\Delta t_{\mathrm{1}}=\mathrm{1530}\hspace{0.17em}\mu \mathrm{s}$ ,

•  

then $\Delta t_{\mathrm{11}}=\Delta t_{\mathrm{10}}+\Delta t=\left(\mathrm{1530}+\mathrm{153}\right)\hspace{0.17em}\mu \mathrm{s}=\mathrm{1683}\hspace{0.17em}\mu \mathrm{s}$ .

Hence, based on the above calculation, total transmission time ${Total}_{TS}$ of first-layer nodes having 11 nodes in number is $\mathrm{1683}\hspace{0.17em}\mu \mathrm{s}$ ; that is, $(128\hspace{0.17em}\mu \mathrm{s}+25\hspace{0.17em}\mu \mathrm{s})\times 11$ . Consider

$$\begin{array}{cc}& {Total}_{TS}=\left(\mathrm{128}\hspace{0.17em}\mu \mathrm{s}+\mathrm{25}\hspace{0.17em}\mu \mathrm{s}\right)\times \mathrm{11}=\mathrm{1683}\hspace{0.17em}\mu \mathrm{s}.\end{array}$$

(6)

Since BS knows the number of nodes in the first layer as discussed previously, this all calculation of ${Total}_{TS}$ of first-layer nodes is performed by BS and is piggybacked in ${Msg}_{({FL}_{init})}$ message to be sent to nodes of first layer. We are in a plan that all the ${Node}_{L_2}$ must not participate in the competition of being CH in order to lessen the broadcasting since the CH announcement of highest degree node suppresses the broadcasting of node with equal and lower degree node. Moreover, there is not any possibility that lower degree node may announce its candidacy of being CH before the higher degree nodes and both these nodes are in the communication range of each other.

For the said purpose, each node calculates $T_{wait(t_i)}$ that is equal to ${Total}_{TS}-\Delta t_i$ . Sample calculation for the same is also performed in subsequent paragraphs:

•  

Let ${Total}_{TS}=\mathrm{1683}$ and $i=\mathrm{1}$ .

 

If $\Delta t_{\mathrm{1}}=\mathrm{153}\hspace{0.17em}\mu \mathrm{s}$ ,

•  

then $T_{wait\left(t_{\mathrm{1}}\right)}=\mathrm{1683}\hspace{0.17em}\mu \mathrm{s}-\mathrm{153}\hspace{0.17em}\mu \mathrm{s}=\mathrm{1530}\hspace{0.17em}\mu \mathrm{s}$ .

 

If $\Delta t_{\mathrm{2}}=\mathrm{306}\hspace{0.17em}\mu \mathrm{s}$ ,

•  

then $T_{wait(t_{\mathrm{2}})}=\mathrm{1683}\hspace{0.17em}\mu \mathrm{s}-\mathrm{306}\hspace{0.17em}\mu \mathrm{s}=\mathrm{1377}\hspace{0.17em}\mu \mathrm{s}$ .

 

If $\Delta t_{\mathrm{3}}=\mathrm{459}\hspace{0.17em}\mu \mathrm{s}$ ,

•  

Then $T_{wait\left(t_{\mathrm{3}}\right)}=\mathrm{1683}\hspace{0.17em}\mu \mathrm{s}-\mathrm{459}\hspace{0.17em}\mu \mathrm{s}=\mathrm{1224}\hspace{0.17em}\mu \mathrm{s}$ .

 

⋮

 

Similarly, if $\Delta t_{\mathrm{11}}=\mathrm{1683}\hspace{0.17em}\mu \mathrm{s}$ ,

•  

then $T_{wait(t_{\mathrm{11}})}=\mathrm{1683}\hspace{0.17em}\mu \mathrm{s}-\mathrm{1683}\hspace{0.17em}\mu \mathrm{s}=\mathrm{0}\hspace{0.17em}\mu \mathrm{s}$ .

We can have a look over the calculated values of $\Delta t_n$ and $T_{wait(t_i)}$ from the succeeding process. We notice that the output is in the increasing order in case of $\Delta t_n$ and in decreasing order in case of $T_{wait(t_i)}$ . This is also depicted in part (a) and part (b) of Figure 7.

${Node}_{L_1}$ broadcast this calculated value of $T_{wait(t_i)}$ along with ${Cnt}_{n_i}$ to ${Node}_{L_2}$ in ${Msg}_{({CL}_{init})}$ for further calculation of $T_{ne{t}_{wait}}$ for assigning the turns of second-layer nodes to take part in selection of decision maker nodes $({Node}_{(dm)})$ and later on in CH election. Hence, based on the abovementioned discussion, all the ${Node}_{L_2}$ are at same level to be in fair competition of being CH. The subsequent layers are defined on the basis of transmission range of previous layer nodes (first-layer nodes in this case till now). Figure 6 shows this layered representation of the deployed network and summarized description in the form of legend on formation of first layer.

We started the network clustering from 2nd layer up to network boundary. The cluster heads in the 2nd layer are selected by the elected decision maker nodes of first layer. This saves energy that other cluster based routing algorithms consume for frequent cluster designing in the neighborhood of base station (as in DSS algorithms [16]) or reclustering of whole network (as in centralized cluster based networks). This also decreases the load on the neighbor nodes that ultimately does the load balancing and hence increases the lifetime of network. After setting up of first layer, ${Node}_{L_1}$ play their role for the designing of 2nd layer, clustered layer. Extended-MCDA designates decision maker nodes from ${Node}_{L_1}$ to break the conflict of claim of nodes for heading the nodes in its neighbors. ${Node}_{L_1}$ broadcast ${Msg}_{({CL}_{init})}$ message with the fields ${Cntr}_{n_i}$ (their node degree) and $T_{wait(t_i)}$ (time for which the ${Node}_{{\left(Rx\right)}_i}$ of ${Msg}_{\left({CL}_{init}\right)}$ message must wait before it takes any action) values for the initialization of cluster designing process at 2nd layer. This designing of Flat layer is pseudo coded in Algorithm 1. Designing of 2nd layer is discussed in detail in subsequent subsection along with brief shortcomings of other two competing cluster designing methods.

Algorithm 1: E-MCDA function for flat layer.

START

${Node}_{all}$ broadcasts $Msg\left(Beacon\right)$

${Node}_{all}$ Setup ${Table}_{(nbr)}$

BS  Setup   ${Table}_{(nbr)}$

$R_{(B_{T_x})}=\mathrm{100}$  m

${Msg}_{\left(setu{p}_{init}\right)}{\mathrm{ContainsN}\_Cnt}_{BS}$

BS  broadcast   ${Msg}_{\left(setu{p}_{init}\right)}$

Set   ${Node}_{\left(Rx\right)}={Node}_{L_1}$

${Node}_{(Rx)}{\mathrm{CalculatesN}odes}_{(rem)}$

   If   $Nod{e}_{id}\left[BS\left({Table}_{\left(nbr\right)}\right)\right]=Nod{e}_{id}\left[Nodes\left({Table}_{\left(nbr\right)}\right)\right]$   Then

          ${Cnt}_{\left(node\right)}$ ++

   End  if

${Nodes}_{\left(rem\right)}=\left[{Nodes}_{\left(Tabl{e}_{\left(nbr\right)}\right)}-{Cnt}_{\left(node\right)}\right]$

${Node}_{(Rx)}$   Sends   ${Nodes}_{(rem)}$   to  BS

BS  Generates   $List({Tx}_{seq})$   Based  on   ${Nodes}_{(rem)}$

Sort   $List({Tx}_{seq})$   in  ascending  order

Allocate   ${Node}_{ids}$   to  nodes  based  on  their  values  in  sorted   $List({Tx}_{seq})$

BS  calculates   ${Total}_{TS}$

    $\mathrm{\Delta }t=\left(T_{es{t}_{tx}}+T_{GI}\right)$

    $\mathrm{\Delta }{t}_n=\mathrm{\Delta }{t}_{i-1}+\mathrm{\Delta }t$

    ${Total}_{TS}={\displaystyle \sum }_{i=1}^n\mathrm{\Delta }{t}_n+\mathrm{\Delta }t$

${Msg}_{({FL}_{init})}$   contains   ${Total}_{TS}$ ,   $\mathrm{\Delta }t$   and  newly  allocated   ${Node}_{ids}$

BS  broadcasts   ${Msg}_{({FL}_{init})}$

${Node}_{(Rx)}$   calculate   $T_{wait(t_i)}$

    $\mathrm{\Delta }{t}_i=(\mathrm{\Delta }t\times i)$

    $T_{wait(t_i)}={Total}_{TS}-\mathrm{\Delta }{t}_i$

${Msg}_{({CL}_{init})}=T_{wait(t_i)}+{Cnt}_{n_i}$

${Node}_{L_1}$   Broadcast   ${Msg}_{({CL}_{init})}$

Set  Transceiver  of   ${Node}_{L_1}$ =  Sleep  mode  for  specific  time  interval

If   $recipients\left[{Msg}_{\left({CL}_{init}\right)}\right]\notin {Node}_{L_1}$   Then

   Receive  the  packet

   Set   ${Node}_{(Rx)}={Node}_{L_2}$

End  if

END

3.3. Clustering Layers Design

Centralized cluster designing requires all the network nodes to communicate their status info especially the info of decision metric to the base station which consumes much of the nodes' energy. This becomes a much more energy squeezing process in the large scale network where direct hop does not work well due to greater distance between source and destination than the nodes' normal footprint. Then the only solution of communicating the network nodes' decision metric info to the BS is multihop. The overall energy consumption in such fashion of information collection is directly proportional to the network size. On the other hand, distributed cluster designing requires much of the internode communication to elect the cluster head first and then the cluster members. In this cluster designing method, the internode message exchange is the multiple of “n,” that is, number of nodes. Moreover, the number and size of the clusters either are not fixed in prior or are difficult to manage. The introduced algorithm in extended-MCDA has successfully overcome the issues offered by centralized and distributed cluster designing techniques through its multilayered probabilistic cluster designing approach. This comes up with the result of minimum energy consumption during cluster designing process that ultimately increases the network lifetime. Considering these hazards for energy aware architecture design, extended-MCDA is introducing a new ever technique for designing the clusters by sensibly managing the announcement of being CH in a distributed way. Neighbor counter and decision maker node are the key factors in designing the clusters, where neighbor counter is preferring one node over others for selection of various positions (decision maker, cluster head) at various steps, and decision maker node is for the selection of cluster head from the subsequent layer (especially in case of tie). The cluster designing process at 2nd layer is initialized with the ${Msg}_{({CL}_{init})}$ message by ${Node}_{L_1}$ . Its recipients that are not from ${Node}_{L_1}$ come in 2nd layer and are called 2nd layer nodes $({Node}_{L_2})$ . Recipients of ${Node}_{L_2}$ start their timers as soon as they receive this message and set it to $T_{wait(t_i)}$ whose value is set by the ${Msg}_{({CL}_{init})}$ message sent from ${Node}_{L_1}$ . A node may receive ${Msg}_{({CL}_{init})}$ message from more than one ${Node}_{L_1}$ . In this case, only the first $T_{wait(t_i)}$ value is considered and all others are ignored. $T_{wait(t_i)}$ value is different for different ${Msg}_{({CL}_{init})}$ messages recipient groups.

For having more practical exposure for the aforementioned proposed solution, the following example is demonstrated in detail with its depiction in Figure 8.

In a scenario, nodes Y, Z, and U are selective nodes from first layer with $T_{wait\left(t_y\right)}=\mathrm{1200}$ , $T_{wait\left(t_z\right)}=\mathrm{750}$ , and $T_{wait\left(t_u\right)}=\mathrm{450}$ . ${Msg}_{{\left({CL}_{init}\right)}_y}$ message from node Y is received by $f,g,i,k,l,a,w$ and the $a,k,l,w,m,n$ nodes receive ${Msg}_{{\left({CL}_{init}\right)}_z}$ message from node Z, while the recipients of ${Msg}_{{\left({CL}_{init}\right)}_u}$ message from node U are $n,y,p,o,r,q,v$ . Referring to Table 2, node IDs in bold are the nodes that are receiving ${Msg}_{({CL}_{init})}$ messages from more than one first-layer node. The node Y among nodes Y, Z, and U is the first node to broadcast its ${Msg}_{({CL}_{init})}$ message followed by node Z and then node U. All the recipients of ${Msg}_{{\left({CL}_{init}\right)}_y}$ message from node Y have their $T_{wait\left(t_y\right)}$ equal to 1200 μs and of node Z have their $T_{wait\left(t_z\right)}$ equal to 750 μs. In case of recipients of ${Msg}_{({CL}_{init})}$ messages from node U, $T_{wait\left(t_u\right)}$ is equal to 450 μs. Nodes receiving ${Msg}_{({CL}_{init})}$ messages from more than one first-layer node have their $T_{wait\left(t_i\right)}$ equal to that from which it receives ${Msg}_{({CL}_{init})}$ messages in first. Tabular representation of this scenario is demonstrated in Table 2.

Table 3 demonstrates 2nd-layer nodes in separate in given scenario that is also depicted in Figure 8 which are at the intersection of communication range of ${Msg}_{({CL}_{init})}$ messages from more than one 1st-layer nodes.

So, each node from ${Node}_{L_2}$ waits for $T_{wait\left(t_i\right)}$ time received in ${Msg}_{({CL}_{init})}$ messages. This equalizes the waiting time of all ${Node}_{L_2}$ to take any action ahead to cluster designing process. So, after finishing first-layer nodes' transmission, that is, completion of $1683\hspace{0.17em}\mu \mathrm{s}$ , the first node that broadcasts $Msg({DM}_{Elec})$ message in response to ${Msg}_{({CL}_{init})}$ message is the node having its $Ne{t}_{Cn{t}_{n\left(i\right)}}$ value the highest among ${Node}_{L_2}$ ; that is, it also has the lowest $T_{ne{t}_{wait}}$ value. In continuation of the abovementioned scenario, among all the listeners of $Msg({DM}_{Elec})$ messages from nodes $\left(f,g,i,k,l,a,w\right)$ , $Z\left(a,k,l,w,m,n\right)$ , and $U\left(w,m,n,y,p,o,r,q,v\right)$ , nodes f, l, and o have the same $Ne{t}_{Cn{tr}_{n_i}}$ value but greater than all other nodes. Also their cluster head election waiting time $(T_{c{h}_{elec}})$ is less than all other nodes of the same level, that is, ${Node}_{L_2}$ . Calculation of $T_{c{h}_{elec}}$ is given in Table 4 for selected nodes of ${Node}_{L_2}$ . To break the tie among nodes f, l, and o in accessing the channel, CSMA/CA algorithm is tested to be the best choice.

Let node l be given the chance to access the network. Its all listeners $\left(i,j,k,a,t,m,w,n\right)$ suppress their turn of broadcasting $Msg({DM}_{Elec})$ at their allocated time slot since their $Ne{t}_{Cn{tr}_{n\left(i\right)}}$ is lower. Now the node with next highest $Ne{t}_{Cn{tr}_{n\left(i\right)}}$ value among the remaining ${Node}_{L_2}$ senses the medium using CSMA algorithm and, on finding it free, it transmits $Msg({DM}_{Elec})$ ; say this node is node o. Its listeners $(n,y,p,s,v,q,r)$ have lesser $Ne{t}_{Cn{tr}_{n\left(i\right)}}$ value. So they suppress their turn and accept the highest degree transmitting node, node o in their footprint as their CH. This process continues until all 2nd-layer nodes are engaged into clusters. Algorithm 2 gives a step by step designing of clustering layer in the form of pseudo code. Figure 9 shows the completion of 1^st cluster in 2nd layer having one cluster highlighted with node “f” as cluster head.

Algorithm 2: E-MCDA function for clustered layer.

START

If   $Node\in {Node}_{L_2}$   Then

Set_up array of   ${Cnt}_{n_i}\in {Node}_{L_1}$

   Compare   ${Cnt}_{n_i}\in {Node}_{L_1}$

   Elect   ${Node}_{(dm)}$   having  Max   ${Cnt}_{n_i}$   among   ${Node}_{L_1}$   in  array

Set  timer  = $T_{{wait}_{t_i}}$

   If  Cnt   $[Received({Msg}_{({CL}_{init})})]>1$   Then

       Consider  only  1st

       Ignore  all  later

   End  if

Each recipient [ ${Msg}_{({CL}_{init})}]$ calculates $T_{ne{t}_{wait}}$

    ${Net\_Cntr}_{n(i)}={Cntr}_{n(i)}-{(Node(s)}_{nbr}\hspace{0.17em}\hspace{0.17em}of\hspace{0.17em}\hspace{0.17em}{Node}_{L_1})$

    $T_{c{h}_{elec}}=1-{\mathrm{l}\mathrm{o}\mathrm{g}}_{\mathrm{10}}({Ne{t}_{Cntr}}_{n\left(i\right)})$

    $T_{ne{t}_{wait}}=T_{c{h}_{elec}}+T_{wait}$

    $Msg(Rpl{y}_{D{M}_{Elec}})={Node}_{(d{m}_{id})}+{Cnt}_{n_i}$

$Msg(Rpl{y}_{D{M}_{Elec}})$   has  unique  Id

If   ${\left(T_{ne{t}_{wait}}\right)}_i<{\left(T_{ne{t}_{wait}}\right)}_j$   Then      ${\forall }_j\hspace{0.17em}\hspace{0.17em}where\hspace{0.17em}\hspace{0.17em}j=0\hspace{0.17em}\hspace{0.17em}to\hspace{0.17em}\hspace{0.17em}n\hspace{0.17em}\hspace{0.17em}and\hspace{0.17em}\hspace{0.17em}j\ne i$

   If $Cntr{\left(T_{ne{t}_{wait}}\right)}_i>1$ Then

       Randomly  select  one  based  on  CSMA/CA  algorithm

   End  if

   If $T_{ne{t}_{wait}}=true$ Then

       Selected   ${Node}_i$   from   ${Node}_{L_2}$   Broadcasts   $Msg(Rpl{y}_{D{M}_{Elec}})$   to  elected   ${Node}_{(dm)}$

   End  if

End  if

If ${Node}_{(Rx)}={Node}_{L_2}$ then

   Suppress  their  Turn  to  Broadcast   $Msg(Rpl{y}_{D{M}_{Elec}})$

End  if

If  Cnt   $[\mathrm{R}\mathrm{e}\mathrm{c}\mathrm{e}\mathrm{i}\mathrm{v}\mathrm{e}\mathrm{d}\hspace{0.17em}Msg\left(Rpl{y}_{D{M}_{Elec}}\right)]$   at   ${Node}_{(dm)}>1$   then

    ${Node}_{(dm)}$   setup  array  of   ${Cnt}_{n_i}$

   Compare   ${Cnt}_{n_i}\in {Node}_{L_2}$

Elect   $Node$   among   ${Node}_{L_1}$   having  Max   ${Cnt}_{n_i}$   in  array

Designate  the  elected  node  as  CH

Send   $Msg({Repl{y}_{Node}}_{(dm)})$   to  elected  CH

End  if

END

3.4. Cluster Member Selection

The elected cluster heads broadcast $join\_req\_msg\hspace{0.17em}({Msg}_{(joi{n}_{rqst})})$ message. This is to inform neighboring sensor nodes of their availability as $CHs$ . Recipient nodes send a consent message $join\_acpt\_msg\hspace{0.17em}{(Msg}_{(joi{n}_{acpt})})$ to become the cluster members. If ${Msg}_{(joi{n}_{rqst})}$ message is received from more than one $CHs$ , then decision of membership is based on the current load on $CH$ ; that is, $CH$ having less number of member nodes is preferred to be attached to. General trend exists in literature to affiliate the node placing at the intersection of communication range of more than one node to either closest inviter $CH$ (highest RSSI value), $CH$ with highest energy level, or cluster head with required node degree (highest or lowest among its neighbors).

Existing generic technique for cluster member selection is given in Algorithm 3.

Algorithm 3: E-MCDA function for cluster member selection.

START

If  Node =  CH  Then

   Broadcast   ${Msg}_{(joi{n}_{rqst})}$

   If   ${Node}_{(B_{T_x})}\in {Node}_{L_2}$   Then

        If   $Cnt\left({Msg}_{(joi{n}_{rqst})}\right)>1$   Then

              ${Node}_{(Rx)}$   send   ${Msg}_{(C{M}_{cn{t}_{rqst}})}$   to  invitee   $CHs$

              $CHs$   wait  for  time  interval  t

              $CH$   sends   ${Msg}_{(C{M}_{cn{t}_{rply}})}$

             Setup  array  of   $C{M}_{cnt}$   of  inviter  CHs

             Set   $CH={CM}_{({\min }_{\mathrm{cnt}})}$

             Acknowledge  only  to  selected   $CH$

        Else

             Reply   ${Msg}_{(joi{n}_{acpt})}$

   End  if

End  if

In the subsequent section, we are presenting an improved version of “required node degree based node/member affiliation algorithm” that helps much in designing near-equal size clusters. This helps in designing clusters with nearly equal load. Figure 10 is showing the said typical scenario in the E-MCDA architecture where nodes i and n are at intersection area (communication range of more than one CHs is overlapping each other) as highlighted in grey. To understand how the sensible affiliation of nodes at intersection area to the CHs helps in designing near-equal size clusters, we are proposing an algorithm which is explained with an example in subsequent paragraphs.

Let in a scenario having 3 clusters f, l, and o with ${Cntr}_{n(f)}=6$ , ${Cntr}_{n(l)}=8$ , and ${Cntr}_{n(o)}=7$ and cluster heads $CH(f)$ , $CH(l)$ , and $CH(o)$ . Two nodes i and j are at the intersection of cluster f and cluster l and two other nodes m and n are at the intersection of clusters o and l.

Node i sends ${Msg}_{(joi{n}_{acpt})}$ message to $CH\left(f\right)$ with piggybacking the ${Cntr}_{n(f)}$ value of its competitor $CH$ , that is, ${CH}_l$ . The competitor listener $CH$ decrements its ${Cntr}_{n(l)}$ value counter by 1. Since ${Cntr}_{n(f)}<{Cntr}_{n(l)}$ , ${CH}_f$ sends ${Msg}_{(joi{n}_{acp{t}_{\left(ack\right)i}})}$ message to node i with piggybacking its updated ${Cntr}_{n(f)}$ value to join it as its cluster member. Step 2 in Table 5 shows the update status of clusters at this stage. As $CH\left(l\right)$ has lost its one potential member node, it sends its latest value of ${Cntr}_{n(l)}$ to update its neighbors. Now the turn is of node m that is placed at the intersection of communication range of cluster l and cluster o. Since ${Cntr}_{n(l)}={Cntr}_{n(o)}$ , tie rises in selection between these two. On random choice, let $CH(l)$ is selected. Then node m sends ${(Msg}_{(joi{n}_{acpt})})$ message to $CH(l)$ in the same fashion as mentioned in case of Node i and receives ${Msg}_{(joi{n}_{acpt})}$ message by $CH(l)$ with piggybacking its updated ${Cntr}_{n(l)}$ value. Here, $CH(o)$ decrements its ${Cntr}_{n(o)}$ value counter by 1 due to loss of one of its potential member nodes and sends its latest ${Cntr}_{n(o)}$ value to update its neighbors. Step 3 in Table 5 shows the update status of clusters at this stage. Similar process continues until remaining two nodes j and n in the given scenario are also affiliated to the clusters having lowest current ${Cntr}_{n(i)}$ value among their inviter. Step 5 in Table 5 shows the final status of clusters f, l, and o after breaking the overlap conflict. Figure 11 shows the completion of clustering process at layer 2 with resolving of “nodes at intersection” issue. Now it seems to be near-equal sized clusters. E-MCDA function for proposed cluster member selection algorithm is given in Algorithm 4.

Algorithm 4: E-MCDA function for proposed cluster member selection algorithm.

START

If  Node  =   $CH$   Then

    ${Msg}_{(joi{n}_{req})}$   contains   ${Cnt}_{(C{H}_i)}$

   CH  broadcasts   ${Msg}_{(joi{n}_{req})}$

   If   ${Node}_{(R{x}_i)}\in {Node}_{L_2}$   and   $Cnt\left({Msg}_{(joi{n}_{rqst})}\right)\ge 1$ Then

        Set_up  array  of   ${Cnt}_{(C{H}_i)}$

        Compare   ${Cnt}_{(C{H}_i)}$

        Elect   $C{H}_i$   having   $\mathrm{Min}({Cnt}_{n_{cH}})$   in  array

        Broadcast   ${Msg}_{(joi{n}_{acpt})}$   to  elected   $C{H}_i$

        If ${Node}_{(R{x}_i)}=C{H}_{i+n}$ Then

                ${Cnt}_{n_{CH}}={Cnt}_{n_{CH}}-1$

        End  if

    $C{H}_i$   sends   ${Msg}_{(joi{n}_{acp{t}_{\left(ack\right)i}})}$   to   ${Node}_{(i)}$

   Endif

Endif

END

If we do a theoretical comparison of proposed solution with the simple solution (where the node is affiliated to the node with lowest degree for the sake of equalizing the cluster size) for affiliation of nodes that are placed at the intersection of communication range of more than one CH, then we come up with Table 6.

Table 6 shows that sample variance of simple algorithm is far greater than that of proposed solution.

The same is also drawn in Figure 12. Derived from this result, performance efficiency $(\rho )$ of proposed method over simple method is 86% using following formula:

$$\begin{array}{cc}& \rho =\mathrm{1}-\left(\frac{\text{Sample Variance of Proposed Scheme}}{\text{Sample Variance of Simple Scheme}}\right).\end{array}$$

(7)

This improved performance results in near-equal sized clusters that help in balanced load over cluster heads that result in less frequent cluster head rotation and hence better network performance and improved network lifetime.

4. Comparative Analysis of E-MCDA with State-of-the-Art Algorithms

In this section, a comprehensive discussion is made on the comparative analysis of E-MCDA with the state-of-the-art related algorithms. Demonstration for the comparison between aforesaid algorithms with respect to various performance evaluation parameters is depicted in different figures starting from Figure 13 to Figure 29. Table 7 shows the simulation parameters taken during our experimentations.

Table 7

Simulation parameters.

Parameter	Description
Routing protocols	EADUC, MCDA, and E-MCDA (proposed)
Simulation area	500 m × 500 m
Simulator	NS 2.31
Data rate	4 packets/Sec
TCP/IP layer	Network layer
Node-to-node distance	Random
Node type	Homogenous
Number of nodes	500
Propagation model	Two-ray ground
Initial energy of node	3 J

Figure 13

Total number of packets transmitted during cluster designing.

Although clustered network is the proven architecture in prolonging the network lifetime yet the prior step of this operational clustered network is formation of clusters that cost something in the form of higher energy consumption compared to setting up cost of flat network. Information collection, competition among candidate nodes to be final cluster head, and announcement of being CH are the key steps to be performed to make the network operational. Transceiver's and processor's activities (transmission, reception, calculation, waking and sleeping modes, etc.) mainly decide the cluster formation cost. The cluster formation idea in EADUC sensibly conserves the energy in its distributed cluster formation. The introduction of waiting time “t” that really decreases plenty of broadcasts and related calculations plays vital role in it. But, in contrast to this, the strategy adapted to generate unequal clusters through the calculation of competition radius $RC$ causes the network to be messy with too much broadcasting since the values of $d_{\mathrm{m}\mathrm{a}\mathrm{x}}$ and $d_{\mathrm{m}\mathrm{i}\mathrm{n}}$ are the parameters of this calculation. Each network node needs to communicate its calculated value $d(S_i,DS)$ , that is, distance from node $S_i$ to the base station $DS$ . $BS$ extracts the $d_{\mathrm{m}\mathrm{a}\mathrm{x}}$ (maximum distance to BS) and $d_{\mathrm{m}\mathrm{i}\mathrm{n}}$ (minimum distance to the BS) and communicated back to the network nodes for their use in calculation of $RC$ . This style encompasses all the drawbacks encapsulated in centralized cluster designing approach. The bigger the network size (network of 500 nodes in our case) the more the involvement of transient nodes to communicate the info for distantly placed nodes to the BS, while, in case of MCDA, this messy type of engagement of transceiver and processor for information collection and dissemination until BS is no more due to the introduction of $P(Se{q}_{no})$ , limited and optimized competing nodes $(d{m}_{id})$ , and selected listeners' response. This idea is more improved in E-MCDA where the idea of MCDA is simplified by $T_{ne{t}_{wait}}$ that further decreases broadcasts and substantially reduces the number of cluster head candidate nodes. Hence, number of packs transmissions (unicast, broadcast, etc.) is highest in EADUC compared to MCDA and it has more than E-MCDA. This comparison is depicted in Figure 13.

Moreover, Figure 14 also supports it where per node average number of packets transmission during cluster formation process is shown. Same differentiation in the form of energy consumption comparison is also reflected from Figure 15.

Figure 14

Average number of packets broadcast per node during cluster formation.

Figure 15

Energy consumption in packet transmission in cluster designing process.

Next to the pinching factor of BS in energy consumption are reception, calculation, and so forth. Considering these performance evaluation parameters, the working presentation of MCDA and E-MCDA are almost the same with little difference while EADUC shows higher energy consumption than others due to calculation of $E_a$ , t, and $RC$ which further have such calculations. Apart from it, more packets transmission/broadcast mean that more nodes are involved in packet reception as depicted from Figures 16 and 17. EADUC has higher number of packets transmissions than other two, so there is more packets reception in resultant also. Hence, Figure 16 depicts more energy consumption of EADUC during cluster formation other than BS transmission process.

Figure 16

Total energy consumption during cluster designing process.

Figure 17

Energy consumption other than packets transmission during cluster designing.

Another notable point is that while comparing Figures 16 and 15 difference in energy consumption of EADUC is about 12   $Joule\hspace{0.17em}(44-32)$ while in case of MCDA it is 6 $Joule\hspace{0.17em}(18-12)$ and in E-MCDA difference is 5 $Joule\hspace{0.17em}(15-10)$ . So, EADUC has almost double difference value compared to MCDA and E-MCDA showing the role of other factor(s) compared to transmission, that is, reception and calculation.

Figure 16 reveals this effect with the proof of the fact that packet transmission matters much in network lifetime compared to receiving and calculation factors. In support of this, there is another empirical fact that energy consumption during transmission of a packet is equal to 1000 calculations and almost the same ratio with packet reception. Consequently, the clear reflection from Figure 17 is that the main outperformance edge of E-MCDA over MCDA and EADUC is controlled transmission due to introduction of ${T_{net}}_{main}$ and very selective CH competition candidates.

The same is also intuited from Figure 18 with the representation of per node average energy consumption. Consumed energy of network nodes can also be represented in another way in order to give another backing to aforementioned claim regarding effect of broadcasting over energy consumption.

Figure 18

Per node average energy consumption during cluster formation.

In Figure 19, energy consumption is calculated in cumulative. As in E-MCDA and MCDA nodes grouping is made into layers, that is, flat layer $N_{L_1}$ , clustering layer 1 $N_{L_2}$ , clustering layer 2 $N_{L_3}$ , and so forth. In accordance with this scenario of layering of nodes, cumulative energy consumption in EADUC is calculated in the same way. As estimated counting of nodes in generated five layers (groups) are 95, 85, 120, 130, and 70 (layer 5 to layer 1, resp.) cumulative to 95, 180, 300, 430, and 500 nodes with cumulative energies as shown in Figure 19. It is reflected from the line graph that energy consumption for EADUC is inversely proportional to the proximity to BS with sharp hike in trend line, while, in case of other two competing mechanisms, MCDA and E-MCDA, energy consumption line is gradually increasing. Cumulative energy consumption line of MCDA is comparatively higher than the E-MCDA because of relatively more broadcast (more involvement of cluster head candidate nodes). Accumulation of energy consumption values are performed from last layer (layer 5 in our case) to first layer since it better represents the sharp hike in energy consumption line and load on the nodes closer to BS compared to its opposite side representation.

Figure 19

Layer-wise cumulative energy consumption.

Another aspect of load and energy consumption relationship is shown in Figure 20. In E-MCDA, energy consumption is almost consistent in all the layers except the first layer (group) because E-MCDA does not form clusters in the first layer. This flat layer (unclustered layer) does not suffer from energy loss due to cluster designing process. The same is the case with E-MCDA. Moreover, in case of EADUC in last group (layer), average energy consumption is almost the same as that of MCDA and E-MCDA. It is also intuited from the result that energy consumption in the process of cluster formation really matters to be considered which also validates and supports our research problem and research contribution. The same effect of work load and node involvement over energy consumption in resultant is shown in Figure 21 where packets transmission is more on the nodes closer to BS in contrast to the farther nodes.

Figure 20

Layer-wise average energy consumption during cluster formation.

Figure 21

Layer-wise average packets transmission during cluster formation.

Considering the residual energy factor in cluster head selection and cluster formation is not always a foresighted decision. In start of network operation almost all the network nodes have the same energy level but with the passage of time energy difference (delta energy, $\Delta E$ ) increases and ultimately at a stage this $\Delta E$ becomes very big. This situation is very inappropriate and unsuitable for considering only energy as CH decision metric.

The big drawback of this choice comes in the form of such clusters having less and sparsely placed nodes, even clusters with only one member node. On comparing the effect of E-MCDA, MCDA, and EADUC over the cluster members in Figures 22, 23, and 24, respectively, we come up with the proof of aforementioned claim. The most fluctuating trend line is of EADUC. It takes the reason that the authors did not consider the node density in generating the clusters and residual energy node is the only factor considered for CH selection/cluster formation.

Figure 22

Number of cluster members in EADUC.

Figure 23

Number of cluster members in MCDA.

Figure 24

Number of cluster members in E-MCDA.

Moreover, in EADUC cluster size is direct function to the distance to BS. Combining these two working aspects of EADUC, we come up with the result in the possibility of two extreme cases in the designed clusters: (i) small clusters with high nodal density and (ii) large clusters with lower nodal density. With this uncontrolled situation, the strategy of EADUC's authors for introducing energy awareness in distributed cluster designing becomes less effective. This uneven distribution scenario is not very uncommon in random and nonuniform deployment of nodes. The most consistent size (density) of clusters is of E-MCDA because the first priority given to the CH decision metric is of nodal density that limits the network to suffer from the same issue as in case of EADUC due to aforementioned reasons. Comparative graph of three mechanisms on number of designed clusters for 500 deployed nodes is demonstrated in Figure 25. It is also clear from the graphs that the designed clusters in MCDA and E-MCDA are almost the same but EADUC makes more clusters due to aforementioned reasons.

Figure 25

Number of clusters.

Another factor that affects the cluster density is of decision strategy relating to nodes placed at the intersecting area of adjacent clusters. Both EADUC and MCDA follow the “proximity to CH” strategy to take their joining decision. This may result in big imbalance in adjacent clusters density. This point is well explained in Cluster Member Selection of this paper. Figures 22, 23, and 24 strongly support this statement with worst to best effect of decision strategies of above issue. Reflection of near-equal size clusters of E-MCDA is better reflected from Figure 26 which has lower standard deviation value compared to MCDA while for EADUC it is highest.

Figure 26

Standard deviation of number of members per cluster.

Here we have calculated the standard deviation using “n” method with the formula $\sqrt{\sum {(x-\stackrel{-}{x})}^2/n}$ .

Clusters nearer to the BS have very small density (even they have the cluster members less than 5) compared to the clusters designed farther from BS that have cluster members even greater than 30. Strategy adopted in EADUC for unequal clusters also leads to unusual number of clusters since if a deployed node does not receive any join request from cluster head, it announces its status as CH. This leads to more clusters. The number of clusters in the network further opens a new talk for its effect on the network lifetime. In short, more clusters increases load on hotspot area and very less clusters increase the load on cluster head. Hence, there must be a moderate way on number of clusters in the network.

The same greedy strategy of cluster designing in EADUC also results in very less unclustered nodes compared to the other two as shown in Figure 27.

Figure 27

Number of unclustered nodes.

5. Conclusions

In this paper, our goal was to introduce an energy-efficient algorithm for the most energy demanding part of cluster based wireless sensor networks. Novel algorithms for time slot allocation, minimizing the cluster head completion candidates, and cluster member selection∖node affiliation to cluster head play vital roles to achieve the target. Results of our experiments of MCDA have shown that it has outperformed the two competitive mechanisms. The key performance evaluation parameters taken for this comparison were energy consumption in various operational parametric values at per node level and at layer level, number of packets broadcast, number of clusters designed, number of members per clusters, and number of unclustered nodes. Acceptance of E-MCDA over MCDA and EADUC in aforesaid performance evaluation parameters has been proved from the simulation-based experiments, since total energy conservation level of E-MCDA is 68% higher compared to EADUC. While, in comparison to MCDA, the outperform results of E-MCDA regarding the same is 17%. During the clustered designing process the messages exchange is one of the big sources of maximum energy consumption. Regarding the comparison in case of number of packets transmitted as a performance evaluation parameter, proficiency of E-MCDA is better than EADUC with the percentage of 69, whereas, competing with MCDA, E-MCDA has shown better performance with the priority value of 19%.

We have also done the comparison of energy consumption in cumulative. As in E-MCDA and MCDA nodes grouping is made into layers, that is, flat layer $N_{L_1}$ , clustering layer 1 $N_{L_2}$ , clustering layer 2 $N_{L_3}$ , and so forth. So, in accordance with this scenario of layering of nodes, cumulative energy consumption in EADUC is calculated in the same way.

For this specific case, the performance efficiency of E-MCDA over MCDA and EADUC is depicted in Figures 28 and 29. Hence, it is demonstrated from the experimentation and detailed analytical discussion that E-MCDA is a priority choice for clustered network design. The comprehensive and detailed, analytical and empirical comparative analysis of E-MCDA with its parent idea, MCDA and another state-of-the-art technique, EADUC, has also evidenced the achievement of our research goals to propose an energy-efficient algorithm for the most energy demanding part of cluster based wireless sensor networks.

Figure 28

Performance efficiency of E-MCDA over MCDA and EADUC in packets transmission.

Figure 29

Performance efficiency of E-MCDA over MCDA and EADUC in total energy consumption.

6. Future Work

Extending the work to a complete routing protocol encompassing setup phases, steady phase, and later on cluster head reselection/rotation phases is in progress. We are very much optimistic in the completion of our claim of introducing multilayer network architecture for energy-efficient routing in wireless sensor network. The comparison can also be performed on first-flat layer of E-MCDA to unequal clustering algorithms, EADUC which has smaller cluster size in the neighbor of BS to lessen the network load over these nodes. The same goal of achieving the higher network life among the two techniques motivates such sequence of comparative studies. In case of heterogeneous network, the same idea of E-MCDA can be tested with changing the cluster head election criteria such as ratio of residual energy of the node to the average energy of the neighbor nodes [17] or energy welfare formula [7]. In our idea, although we tried to present the pure network layer algorithm, the involvement of any localization algorithms or GPS enabled nodes is kept away. Yet another induction of idea in the E-MCDA can be defining the layer boundaries by transmitting the broadcast signal with varying defined levels [18]. This will further decrease the packets broadcasting that are used for selecting the decision maker nodes at the boundary of layers. Clustering architecture of E-MCDA can also be used in bioinspired algorithm [19, 20]. The proposed idea can also be improved by introducing congestion control technique [21]. Furthermore, this scheme can also be formulated in to other emerging sector such as M2M, IoT and Bigdata (classification), [16, 22–26]. As a whole there is huge scope for future work in this field of MCDA.