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

Authors: Sohail Jabbar; Abid Ali Minhas; Moneeb Gohar; Anand Paul; Seungmin Rho
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## 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.


---

## Body

## 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. Figure2 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[0,1] with some calculated probability [9–11]. Elected CH advertisesJoin_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 introducedTwait(ti) 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 nodesNode(dm) and also in the election of cluster heads.(b)
Incorporation ofTwait(ti) 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,CHprob, is set to assume that an optimal percentage cannot be computed a priori. The value ofCHprob, 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 itsCHprob value and goes to the next iteration until itsCHprob reaches 1. Therefore, there are two types of statuses that a sensor node could announce to its neighbors: tentative status and final status. If itsCHprob 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 itsCHprob 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 (NodeL1). 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 (NodeL2) elect the node with the highest node density (node degree) as their decision maker node (Node(dm)); that is, Cntni>Cntnj∀i and j=1,2,3,…,n and n is equal to all nodes with same sequence number belonging to same group. Second layer nodes (NodeL2) communicate their nodal density (Cntni) 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 NodeL2communicates its nodal density (Cntn1) to Node(dm), it assigns sequence number (Pkt(Seq_no)) with postfix counter “0” to these packets. All the recipient nodes of NodeL2 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 Cntni 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 Cntni 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 PktSeqno 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 PktSeqno 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 roundProposed 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, T1, T2, and T3. 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 aNode_Msg message within its radio range r having node ID and its residual energy Er. 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:(1)
t
=
E
a
E
r
T
2
V
r
,
E
r
≥
E
a
T
2
V
r
,
E
r
<
E
a
,where Vr is a real value randomly distributed in [0.9,1] which is introduced to reduce the probability that two nodes sendHead_Msgs at the same time. Each node waits until this calculated time prior to broadcastHead_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 calculatedt time, decision for the nodes to be cluster head is broadcasted within their calculated radio range. If a node does not receive anyHead_Msg message until the expiry of its time t, then it broadcasts theHead Msg within radio range RCi to advertise that it will be a cluster head.Since the competition radiusRC determines the size of cluster that is based on the proximity to the BS. Each node calculates its own value for RC using the following formula:(2)RC=1-αdmax-dsi,BSdmax-dmin-β1-ErEmaxRmax,where dmax and dmin are the maximum and minimum distances from the nodes in the network to the BS, d(si,BS) is the distance from node si to the BS, α and β are weighted factors in 0,1, and RC0 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 theJoin_Msg which contains theID 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 Rcomp, 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 Rcomp value. Rcomp 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, Si. Rcomp, each node must be communicated with the dmax (maximum distance from the BS) and dmin (minimum distance from the BS) by the BS. Each tentative cluster head communicates its Nodeid and RE (Residual Energy) value to its neighbor nodes. Thus each TCH prepares its neighbor set, SCH. 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 (Figures5–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 ofMsg(CLinit) messages by NodeL1recipient nodes from NodeL2.
Selected nodes fromNodeL1
Waiting time for group of  recipient nodes ofMsg(CLinit) message Twaitti
M
s
g
(
C
L
i
n
i
t
) message recipient nodes’ group
Y
1200μs
f
,
g
,
i, k, l, a, w
Z
7500μs
a
,
k
,
l
,
w
,
m
,
n
U
450μs
w
,
m
,
n
,
y
,
p
,
o
,
r
,
q
,
vTable 3
Representation ofNodeL2 that receive multiple RqstDMElec messages from NodeL1.
Nodes receivingMsg(CLinit) messages from
Y and Z
Z and U
k
,
l
,
a
,
w
w
,
m
,
nTable 4
Calculation for net waiting timeTnetwait for NodeL2 for energy aware designing of clusters at 2nd layer (the node having the lowest net node degree Net_Cntn(i) has the highest net waiting time Tnetwait value and vice versa).
N
o
d
e
_
I
D
ith node degree (Cntni)
Neighbor fromNodeL1
N
e
t
C
n
t
n
(
i
)
T
c
h
e
l
e
c
=
1
-
log
10
⁡
(
N
e
t
C
n
t
n
(
i
)
)
T
n
e
t
w
a
i
t
∗
=
T
c
h
e
l
e
c
+
T
w
a
i
t
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
∗
T
w
a
i
t
=
T
c
h
e
l
e
c
+
T
e
s
t
t
x
+
T
G
I
×
C
n
t
(
N
o
d
e
L
1
)
=
T
c
h
e
l
e
c
+
128
μ
s
+
25
μ
s
×
11.Table 5
Function of proposed scheme for affiliation of nodes at intersection of communication range of more than one CH.
Steps
C
n
t
r
n
(
f
)
C
n
t
r
n
(
l
)
C
n
t
r
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
0Table 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
C
n
t
r
n
(
f
)
6
6
C
n
t
r
n
(
l
)
4
5
C
n
t
r
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Δtn and Twait(ti).
(a)
(b)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. Figure5 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 nodesNodeL1. All nodes broadcast beacon message (MsgBeacon) 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 (Msgsetupinit) to initiate the cluster designing process. Recipient nodes are designated as first-layer nodes (NodeL1). NodeL1 send their number of neighbors excluding their neighbors that are not from NodeL1, that is, Nodes(rem). Now the BS assigns the node IDS to NodeL1 according to their Nodes(rem) value. Total time slots allocated to the NodeL1, that is, (TotalTS), is calculated by BS as follows:(3)Δti=Δti-1+ΔtΔt=Testtx+TGITotalTS=∑i=1nΔtn+Δt.Now, ultimately, BS broadcasts flat layer initialization message (MsgFLinit) to formally initiate the designing of clustered network. Msg(FLinit) contains TotalTS, Δt, and newly allocated Nodeids. Recipient nodes of Msg(FLinit) calculate Twait(ti) as in(4)Twaitti=TotalTS-ΔtiorTotalTS-Δt×iTwait(ti) 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(NodeL2), clustering layer initialization message (Msg(CLinit)) that has the information of Twait(ti) and Cntni is broadcasted to NodeL2.Refer to Figure6; there are 11 nodes in the footprint of BS to receive this message and thus are comprising first layer. Msg(FLinit) message consists of 128 bits and transmission time for a packet is 128μs/packet(message). If Δt is the time slot allocated to a node which consists of estimated transmission time Testtx and the safe gap in the transmission of next node called guard interval TGI, then first node from NodeL1 is allocated Δt1, that is, equal to Δt as in(5)Δt=Testtx+TGI=128+25μs=153μs.The next allocated time starts right after the completion of this Δt1 and so on. Calculation for the same is given as follows based on Δti=Δti-1+Δt:Leti=1 and Δt0=0,
so,Δt1=Δt0+Δt=153μs.Ifi=2 and Δt1=153μs,
thenΔt2=Δt1+Δt=153+153μs=306μs.Ifn=i and Δt1=306μs,
thenΔt3=Δt2+Δt=306+153μs=459μs.⋮Similarly, ifi=10 and Δt1=1377μs,
thenΔt10=Δt9+Δt=1377+153μs=1530μs.And ifi=11 and Δt1=1530μs,
thenΔt11=Δt10+Δt=1530+153μs=1683μs.Hence, based on the above calculation, total transmission time TotalTS of first-layer nodes having 11 nodes in number is 1683μs; that is, (128μs+25μs)×11. Consider (6)TotalTS=128μs+25μs×11=1683μs.Since BS knows the number of nodes in the first layer as discussed previously, this all calculation of TotalTS of first-layer nodes is performed by BS and is piggybacked in Msg(FLinit) message to be sent to nodes of first layer. We are in a plan that all the NodeL2 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 calculatesTwait(ti) that is equal to TotalTS-Δti. Sample calculation for the same is also performed in subsequent paragraphs:LetTotalTS=1683 and i=1.IfΔt1=153μs,
thenTwaitt1=1683μs-153μs=1530μs.IfΔt2=306μs,
thenTwait(t2)=1683μs-306μs=1377μs.IfΔt3=459μs,
ThenTwaitt3=1683μs-459μs=1224μs.⋮Similarly, ifΔt11=1683μs,
thenTwait(t11)=1683μs-1683μs=0μs.We can have a look over the calculated values of Δtn and Twait(ti) from the succeeding process. We notice that the output is in the increasing order in case of Δtn and in decreasing order in case of Twait(ti). This is also depicted in part (a) and part (b) of Figure 7.N
o
d
e
L
1 broadcast this calculated value of Twait(ti) along with Cntni to NodeL2in Msg(CLinit) for further calculation of Tnetwait 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 NodeL2 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, NodeL1 play their role for the designing of 2nd layer, clustered layer. Extended-MCDA designates decision maker nodes from NodeL1 to break the conflict of claim of nodes for heading the nodes in its neighbors. NodeL1broadcast Msg(CLinit) message with the fields Cntrni (their node degree) and Twait(ti) (time for which the NodeRxi of MsgCLinit 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
N
o
d
e
a
l
l
broadcasts
M
s
g
B
e
a
c
o
n
N
o
d
e
a
l
l
Setup
T
a
b
l
e
(
n
b
r
)
BS  Setup
T
a
b
l
e
(
n
b
r
)
R
(
B
T
x
)
=
100 m
M
s
g
s
e
t
u
p
i
n
i
t
ContainsN
_
C
n
t
B
S
BS  broadcast
M
s
g
s
e
t
u
p
i
n
i
t
Set
N
o
d
e
R
x
=
N
o
d
e
L
1
N
o
d
e
(
R
x
)
CalculatesN
o
d
e
s
(
r
e
m
)
If  NodeidBSTablenbr=NodeidNodesTablenbr  Then
Cntnode++
End  if
N
o
d
e
s
r
e
m
=
N
o
d
e
s
T
a
b
l
e
n
b
r
-
C
n
t
n
o
d
e
N
o
d
e
(
R
x
)
Sends
N
o
d
e
s
(
r
e
m
)
to  BS
BS  Generates
L
i
s
t
(
T
x
s
e
q
)
Based  on
N
o
d
e
s
(
r
e
m
)
Sort
L
i
s
t
(
T
x
s
e
q
)
in  ascending  order
Allocate
N
o
d
e
i
d
s
to  nodes  based  on  their  values  in  sorted
L
i
s
t
(
T
x
s
e
q
)
BS  calculates
T
o
t
a
l
T
S
Δt=Testtx+TGI
Δtn=Δti-1+Δt
TotalTS=∑i=1nΔtn+Δt
M
s
g
(
F
L
i
n
i
t
)
contains
T
o
t
a
l
T
S
,
Δ
t
and  newly  allocated
N
o
d
e
i
d
s
BS  broadcasts
M
s
g
(
F
L
i
n
i
t
)
N
o
d
e
(
R
x
)
calculate
T
w
a
i
t
(
t
i
)
Δti=(Δt×i)
Twait(ti)=TotalTS-Δti
M
s
g
(
C
L
i
n
i
t
)
=
T
w
a
i
t
(
t
i
)
+
C
n
t
n
i
N
o
d
e
L
1
Broadcast
M
s
g
(
C
L
i
n
i
t
)
Set  Transceiver  of
N
o
d
e
L
1
=
Sleep  mode  for  specific  time  interval
If  recipientsMsgCLinit∉NodeL1  Then
Receive  the  packet
SetNode(Rx)=NodeL2
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(CLinit) message by NodeL1. Its recipients that are not from NodeL1come in 2nd layer and are called 2nd layer nodes (NodeL2). Recipients of NodeL2 start their timers as soon as they receive this message and set it to Twait(ti) whose value is set by the Msg(CLinit) message sent from NodeL1. A node may receive Msg(CLinit) message from more than one NodeL1. In this case, only the first Twait(ti) value is considered and all others are ignored. Twait(ti) value is different for different Msg(CLinit) messages recipient groups.For having more practical exposure for the aforementioned proposed solution, the following example is demonstrated in detail with its depiction in Figure8.In a scenario, nodesY, Z, and U are selective nodes from first layer with Twaitty=1200, Twaittz=750, and Twaittu=450. MsgCLinity message from node Y is received by f,g,i,k,l,a,w and the a,k,l,w,m,n nodes receive MsgCLinitz message from node Z, while the recipients of MsgCLinitu 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(CLinit) 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(CLinit) message followed by node Z and then node U. All the recipients of MsgCLinitymessage from node Y have their Twaitty equal to 1200 μs and of node Z have their Twaittz equal to 750 μs. In case of recipients of Msg(CLinit) messages from node U, Twaittu is equal to 450 μs. Nodes receiving Msg(CLinit) messages from more than one first-layer node have their Twaitti equal to that from which it receives Msg(CLinit) messages in first. Tabular representation of this scenario is demonstrated in Table 2.Table3 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(CLinit) messages from more than one 1st-layer nodes.So, each node fromNodeL2 waits for Twaitti time received in Msg(CLinit) messages. This equalizes the waiting time of all NodeL2 to take any action ahead to cluster designing process. So, after finishing first-layer nodes’ transmission, that is, completion of 1683μs, the first node that broadcasts Msg(DMElec) message in response to Msg(CLinit) message is the node having its NetCntni value the highest among NodeL2; that is, it also has the lowest Tnetwait value. In continuation of the abovementioned scenario, among all the listeners of Msg(DMElec) messages from nodes f,g,i,k,l,a,w, Za,k,l,w,m,n, and Uw,m,n,y,p,o,r,q,v, nodes f, l, and o have the same NetCntrni value but greater than all other nodes. Also their cluster head election waiting time (Tchelec) is less than all other nodes of the same level, that is, NodeL2. Calculation of Tchelecis given in Table 4 for selected nodes of NodeL2. 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 nodel be given the chance to access the network. Its all listeners i,j,k,a,t,m,w,n suppress their turn of broadcasting Msg(DMElec) at their allocated time slot since their NetCntrni is lower. Now the node with next highest NetCntrni value among the remaining NodeL2senses the medium using CSMA algorithm and, on finding it free, it transmits Msg(DMElec); say this node is node o. Its listeners (n,y,p,s,v,q,r) have lesser NetCntrni 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 1st 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∈NodeL2  Then
Set_up array of  Cntni∈NodeL1
Compare  Cntni∈NodeL1
ElectNode(dm)having  MaxCntniamongNodeL1in  array
Set  timer=Twaitti
If  Cnt[Received(Msg(CLinit))]>1  Then
Consider  only  1st
Ignore  all  later
End  if
Each recipient [Msg(CLinit)] calculates Tnetwait
Net_Cntrn(i)=Cntrn(i)-(Node(s)nbrofNodeL1)
Tchelec=1-log10(NetCntrni)
Tnetwait=Tchelec+Twait
Msg(RplyDMElec)=Node(dmid)+Cntni
M
s
g
(
R
p
l
y
D
M
E
l
e
c
)
has  unique  Id
If  Tnetwaiti<Tnetwaitj  Then∀jwherej=0tonandj≠i
IfCntrTnetwaiti>1Then
Randomly  select  one  based  on  CSMA/CA  algorithm
End  if
IfTnetwait=trueThen
SelectedNodeifromNodeL2BroadcastsMsg(RplyDMElec)to  electedNode(dm)
End  if
End  if
If
N
o
d
e
(
R
x
)
=
N
o
d
e
L
2
then
Suppress  their  Turn  to  BroadcastMsg(RplyDMElec)
End  if
If  Cnt[ReceivedMsgRplyDMElec]atNode(dm)>1  then
Node(dm)setup  array  ofCntni
CompareCntni∈NodeL2
Elect
N
o
d
e
among
N
o
d
e
L
1
having  Max
C
n
t
n
i
in  array
Designate  the  elected  node  as  CH
Send
M
s
g
(
R
e
p
l
y
N
o
d
e
(
d
m
)
)
to  elected  CH
End  if
END


### 3.4. Cluster Member Selection

The elected cluster heads broadcastjoin_req_msg(Msg(joinrqst)) message. This is to inform neighboring sensor nodes of their availability as CHs. Recipient nodes send a consent message join_acpt_msg(Msg(joinacpt)) to become the cluster members. If Msg(joinrqst) 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 Algorithm3.Algorithm 3:E-MCDA function for cluster member selection.
START
If  Node =  CH  Then
BroadcastMsg(joinrqst)
If  Node(BTx)∈NodeL2  Then
If  CntMsg(joinrqst)>1  Then
Node(Rx)sendMsg(CMcntrqst)to  inviteeCHs
CHswait  for  time  intervalt
CHsendsMsg(CMcntrply)
Setup  array  ofCMcntof  inviter  CHs
SetCH=CM(mincnt⁡⁡)
Acknowledge  only  to  selectedCH
Else
ReplyMsg(joinacpt)
End  if
End  ifIn 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 clustersf, l, and o with Cntrn(f)=6, Cntrn(l)=8, and Cntrn(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.Nodei sends Msg(joinacpt) message to CHf with piggybacking the Cntrn(f) value of its competitor CH, that is, CHl. The competitor listener CH decrements its Cntrn(l) value counter by 1. Since Cntrn(f)<Cntrn(l), CHf sends Msg(joinacptacki) message to node i with piggybacking its updated Cntrn(f) value to join it as its cluster member. Step 2 in Table 5 shows the update status of clusters at this stage. As CHl has lost its one potential member node, it sends its latest value of Cntrn(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 Cntrn(l)=Cntrn(o), tie rises in selection between these two. On random choice, let CH(l) is selected. Then node m sends (Msg(joinacpt)) message to CH(l) in the same fashion as mentioned in case of Node i and receives Msg(joinacpt) message by CH(l) with piggybacking its updated Cntrn(l) value. Here, CH(o) decrements its Cntrn(o) value counter by 1 due to loss of one of its potential member nodes and sends its latest Cntrn(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 Cntrn(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(joinreq)containsCnt(CHi)
CH  broadcastsMsg(joinreq)
If  Node(Rxi)∈NodeL2andCntMsg(joinrqst)≥1Then
Set_up  array  ofCnt(CHi)
CompareCnt(CHi)
ElectCHihavingMin⁡(CntncH)in  array
BroadcastMsg(joinacpt)to  electedCHi
IfNode(Rxi)=CHi+nThen
CntnCH=CntnCH-1
End  if
CHisendsMsg(joinacptacki)toNode(i)
Endif
Endif
ENDIf 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 Table6.Table6 shows that sample variance of simple algorithm is far greater than that of proposed solution.The same is also drawn in Figure12. Derived from this result, performance efficiency (ρ) of proposed method over simple method is 86% using following formula:(7)ρ=1-Sample Variance of Proposed SchemeSample Variance of Simple Scheme.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.


## 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. Figure5 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 nodesNodeL1. All nodes broadcast beacon message (MsgBeacon) 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 (Msgsetupinit) to initiate the cluster designing process. Recipient nodes are designated as first-layer nodes (NodeL1). NodeL1 send their number of neighbors excluding their neighbors that are not from NodeL1, that is, Nodes(rem). Now the BS assigns the node IDS to NodeL1 according to their Nodes(rem) value. Total time slots allocated to the NodeL1, that is, (TotalTS), is calculated by BS as follows:(3)Δti=Δti-1+ΔtΔt=Testtx+TGITotalTS=∑i=1nΔtn+Δt.Now, ultimately, BS broadcasts flat layer initialization message (MsgFLinit) to formally initiate the designing of clustered network. Msg(FLinit) contains TotalTS, Δt, and newly allocated Nodeids. Recipient nodes of Msg(FLinit) calculate Twait(ti) as in(4)Twaitti=TotalTS-ΔtiorTotalTS-Δt×iTwait(ti) 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(NodeL2), clustering layer initialization message (Msg(CLinit)) that has the information of Twait(ti) and Cntni is broadcasted to NodeL2.Refer to Figure6; there are 11 nodes in the footprint of BS to receive this message and thus are comprising first layer. Msg(FLinit) message consists of 128 bits and transmission time for a packet is 128μs/packet(message). If Δt is the time slot allocated to a node which consists of estimated transmission time Testtx and the safe gap in the transmission of next node called guard interval TGI, then first node from NodeL1 is allocated Δt1, that is, equal to Δt as in(5)Δt=Testtx+TGI=128+25μs=153μs.The next allocated time starts right after the completion of this Δt1 and so on. Calculation for the same is given as follows based on Δti=Δti-1+Δt:Leti=1 and Δt0=0,
so,Δt1=Δt0+Δt=153μs.Ifi=2 and Δt1=153μs,
thenΔt2=Δt1+Δt=153+153μs=306μs.Ifn=i and Δt1=306μs,
thenΔt3=Δt2+Δt=306+153μs=459μs.⋮Similarly, ifi=10 and Δt1=1377μs,
thenΔt10=Δt9+Δt=1377+153μs=1530μs.And ifi=11 and Δt1=1530μs,
thenΔt11=Δt10+Δt=1530+153μs=1683μs.Hence, based on the above calculation, total transmission time TotalTS of first-layer nodes having 11 nodes in number is 1683μs; that is, (128μs+25μs)×11. Consider (6)TotalTS=128μs+25μs×11=1683μs.Since BS knows the number of nodes in the first layer as discussed previously, this all calculation of TotalTS of first-layer nodes is performed by BS and is piggybacked in Msg(FLinit) message to be sent to nodes of first layer. We are in a plan that all the NodeL2 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 calculatesTwait(ti) that is equal to TotalTS-Δti. Sample calculation for the same is also performed in subsequent paragraphs:LetTotalTS=1683 and i=1.IfΔt1=153μs,
thenTwaitt1=1683μs-153μs=1530μs.IfΔt2=306μs,
thenTwait(t2)=1683μs-306μs=1377μs.IfΔt3=459μs,
ThenTwaitt3=1683μs-459μs=1224μs.⋮Similarly, ifΔt11=1683μs,
thenTwait(t11)=1683μs-1683μs=0μs.We can have a look over the calculated values of Δtn and Twait(ti) from the succeeding process. We notice that the output is in the increasing order in case of Δtn and in decreasing order in case of Twait(ti). This is also depicted in part (a) and part (b) of Figure 7.N
o
d
e
L
1 broadcast this calculated value of Twait(ti) along with Cntni to NodeL2in Msg(CLinit) for further calculation of Tnetwait 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 NodeL2 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, NodeL1 play their role for the designing of 2nd layer, clustered layer. Extended-MCDA designates decision maker nodes from NodeL1 to break the conflict of claim of nodes for heading the nodes in its neighbors. NodeL1broadcast Msg(CLinit) message with the fields Cntrni (their node degree) and Twait(ti) (time for which the NodeRxi of MsgCLinit 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
N
o
d
e
a
l
l
broadcasts
M
s
g
B
e
a
c
o
n
N
o
d
e
a
l
l
Setup
T
a
b
l
e
(
n
b
r
)
BS  Setup
T
a
b
l
e
(
n
b
r
)
R
(
B
T
x
)
=
100 m
M
s
g
s
e
t
u
p
i
n
i
t
ContainsN
_
C
n
t
B
S
BS  broadcast
M
s
g
s
e
t
u
p
i
n
i
t
Set
N
o
d
e
R
x
=
N
o
d
e
L
1
N
o
d
e
(
R
x
)
CalculatesN
o
d
e
s
(
r
e
m
)
If  NodeidBSTablenbr=NodeidNodesTablenbr  Then
Cntnode++
End  if
N
o
d
e
s
r
e
m
=
N
o
d
e
s
T
a
b
l
e
n
b
r
-
C
n
t
n
o
d
e
N
o
d
e
(
R
x
)
Sends
N
o
d
e
s
(
r
e
m
)
to  BS
BS  Generates
L
i
s
t
(
T
x
s
e
q
)
Based  on
N
o
d
e
s
(
r
e
m
)
Sort
L
i
s
t
(
T
x
s
e
q
)
in  ascending  order
Allocate
N
o
d
e
i
d
s
to  nodes  based  on  their  values  in  sorted
L
i
s
t
(
T
x
s
e
q
)
BS  calculates
T
o
t
a
l
T
S
Δt=Testtx+TGI
Δtn=Δti-1+Δt
TotalTS=∑i=1nΔtn+Δt
M
s
g
(
F
L
i
n
i
t
)
contains
T
o
t
a
l
T
S
,
Δ
t
and  newly  allocated
N
o
d
e
i
d
s
BS  broadcasts
M
s
g
(
F
L
i
n
i
t
)
N
o
d
e
(
R
x
)
calculate
T
w
a
i
t
(
t
i
)
Δti=(Δt×i)
Twait(ti)=TotalTS-Δti
M
s
g
(
C
L
i
n
i
t
)
=
T
w
a
i
t
(
t
i
)
+
C
n
t
n
i
N
o
d
e
L
1
Broadcast
M
s
g
(
C
L
i
n
i
t
)
Set  Transceiver  of
N
o
d
e
L
1
=
Sleep  mode  for  specific  time  interval
If  recipientsMsgCLinit∉NodeL1  Then
Receive  the  packet
SetNode(Rx)=NodeL2
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(CLinit) message by NodeL1. Its recipients that are not from NodeL1come in 2nd layer and are called 2nd layer nodes (NodeL2). Recipients of NodeL2 start their timers as soon as they receive this message and set it to Twait(ti) whose value is set by the Msg(CLinit) message sent from NodeL1. A node may receive Msg(CLinit) message from more than one NodeL1. In this case, only the first Twait(ti) value is considered and all others are ignored. Twait(ti) value is different for different Msg(CLinit) messages recipient groups.For having more practical exposure for the aforementioned proposed solution, the following example is demonstrated in detail with its depiction in Figure8.In a scenario, nodesY, Z, and U are selective nodes from first layer with Twaitty=1200, Twaittz=750, and Twaittu=450. MsgCLinity message from node Y is received by f,g,i,k,l,a,w and the a,k,l,w,m,n nodes receive MsgCLinitz message from node Z, while the recipients of MsgCLinitu 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(CLinit) 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(CLinit) message followed by node Z and then node U. All the recipients of MsgCLinitymessage from node Y have their Twaitty equal to 1200 μs and of node Z have their Twaittz equal to 750 μs. In case of recipients of Msg(CLinit) messages from node U, Twaittu is equal to 450 μs. Nodes receiving Msg(CLinit) messages from more than one first-layer node have their Twaitti equal to that from which it receives Msg(CLinit) messages in first. Tabular representation of this scenario is demonstrated in Table 2.Table3 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(CLinit) messages from more than one 1st-layer nodes.So, each node fromNodeL2 waits for Twaitti time received in Msg(CLinit) messages. This equalizes the waiting time of all NodeL2 to take any action ahead to cluster designing process. So, after finishing first-layer nodes’ transmission, that is, completion of 1683μs, the first node that broadcasts Msg(DMElec) message in response to Msg(CLinit) message is the node having its NetCntni value the highest among NodeL2; that is, it also has the lowest Tnetwait value. In continuation of the abovementioned scenario, among all the listeners of Msg(DMElec) messages from nodes f,g,i,k,l,a,w, Za,k,l,w,m,n, and Uw,m,n,y,p,o,r,q,v, nodes f, l, and o have the same NetCntrni value but greater than all other nodes. Also their cluster head election waiting time (Tchelec) is less than all other nodes of the same level, that is, NodeL2. Calculation of Tchelecis given in Table 4 for selected nodes of NodeL2. 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 nodel be given the chance to access the network. Its all listeners i,j,k,a,t,m,w,n suppress their turn of broadcasting Msg(DMElec) at their allocated time slot since their NetCntrni is lower. Now the node with next highest NetCntrni value among the remaining NodeL2senses the medium using CSMA algorithm and, on finding it free, it transmits Msg(DMElec); say this node is node o. Its listeners (n,y,p,s,v,q,r) have lesser NetCntrni 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 1st 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∈NodeL2  Then
Set_up array of  Cntni∈NodeL1
Compare  Cntni∈NodeL1
ElectNode(dm)having  MaxCntniamongNodeL1in  array
Set  timer=Twaitti
If  Cnt[Received(Msg(CLinit))]>1  Then
Consider  only  1st
Ignore  all  later
End  if
Each recipient [Msg(CLinit)] calculates Tnetwait
Net_Cntrn(i)=Cntrn(i)-(Node(s)nbrofNodeL1)
Tchelec=1-log10(NetCntrni)
Tnetwait=Tchelec+Twait
Msg(RplyDMElec)=Node(dmid)+Cntni
M
s
g
(
R
p
l
y
D
M
E
l
e
c
)
has  unique  Id
If  Tnetwaiti<Tnetwaitj  Then∀jwherej=0tonandj≠i
IfCntrTnetwaiti>1Then
Randomly  select  one  based  on  CSMA/CA  algorithm
End  if
IfTnetwait=trueThen
SelectedNodeifromNodeL2BroadcastsMsg(RplyDMElec)to  electedNode(dm)
End  if
End  if
If
N
o
d
e
(
R
x
)
=
N
o
d
e
L
2
then
Suppress  their  Turn  to  BroadcastMsg(RplyDMElec)
End  if
If  Cnt[ReceivedMsgRplyDMElec]atNode(dm)>1  then
Node(dm)setup  array  ofCntni
CompareCntni∈NodeL2
Elect
N
o
d
e
among
N
o
d
e
L
1
having  Max
C
n
t
n
i
in  array
Designate  the  elected  node  as  CH
Send
M
s
g
(
R
e
p
l
y
N
o
d
e
(
d
m
)
)
to  elected  CH
End  if
END


## 3.4. Cluster Member Selection

The elected cluster heads broadcastjoin_req_msg(Msg(joinrqst)) message. This is to inform neighboring sensor nodes of their availability as CHs. Recipient nodes send a consent message join_acpt_msg(Msg(joinacpt)) to become the cluster members. If Msg(joinrqst) 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 Algorithm3.Algorithm 3:E-MCDA function for cluster member selection.
START
If  Node =  CH  Then
BroadcastMsg(joinrqst)
If  Node(BTx)∈NodeL2  Then
If  CntMsg(joinrqst)>1  Then
Node(Rx)sendMsg(CMcntrqst)to  inviteeCHs
CHswait  for  time  intervalt
CHsendsMsg(CMcntrply)
Setup  array  ofCMcntof  inviter  CHs
SetCH=CM(mincnt⁡⁡)
Acknowledge  only  to  selectedCH
Else
ReplyMsg(joinacpt)
End  if
End  ifIn 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 clustersf, l, and o with Cntrn(f)=6, Cntrn(l)=8, and Cntrn(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.Nodei sends Msg(joinacpt) message to CHf with piggybacking the Cntrn(f) value of its competitor CH, that is, CHl. The competitor listener CH decrements its Cntrn(l) value counter by 1. Since Cntrn(f)<Cntrn(l), CHf sends Msg(joinacptacki) message to node i with piggybacking its updated Cntrn(f) value to join it as its cluster member. Step 2 in Table 5 shows the update status of clusters at this stage. As CHl has lost its one potential member node, it sends its latest value of Cntrn(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 Cntrn(l)=Cntrn(o), tie rises in selection between these two. On random choice, let CH(l) is selected. Then node m sends (Msg(joinacpt)) message to CH(l) in the same fashion as mentioned in case of Node i and receives Msg(joinacpt) message by CH(l) with piggybacking its updated Cntrn(l) value. Here, CH(o) decrements its Cntrn(o) value counter by 1 due to loss of one of its potential member nodes and sends its latest Cntrn(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 Cntrn(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(joinreq)containsCnt(CHi)
CH  broadcastsMsg(joinreq)
If  Node(Rxi)∈NodeL2andCntMsg(joinrqst)≥1Then
Set_up  array  ofCnt(CHi)
CompareCnt(CHi)
ElectCHihavingMin⁡(CntncH)in  array
BroadcastMsg(joinacpt)to  electedCHi
IfNode(Rxi)=CHi+nThen
CntnCH=CntnCH-1
End  if
CHisendsMsg(joinacptacki)toNode(i)
Endif
Endif
ENDIf 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 Table6.Table6 shows that sample variance of simple algorithm is far greater than that of proposed solution.The same is also drawn in Figure12. Derived from this result, performance efficiency (ρ) of proposed method over simple method is 86% using following formula:(7)ρ=1-Sample Variance of Proposed SchemeSample Variance of Simple Scheme.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 Figure13 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 JFigure 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 dmax and dmin are the parameters of this calculation. Each network node needs to communicate its calculated value d(Si,DS), that is, distance from node Si to the base station DS. BS extracts the dmax (maximum distance to BS) and dmin (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(Seqno), limited and optimized competing nodes (dmid), and selected listeners’ response. This idea is more improved in E-MCDA where the idea of MCDA is simplified by Tnetwait 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, Figure14 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 ofEa, 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 Figures16 and 15 difference in energy consumption of EADUC is about 12  Joule(44-32) while in case of MCDA it is 6 Joule(18-12) and in E-MCDA difference is 5 Joule(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.Figure16 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 Tnetmain and very selective CH competition candidates.The same is also intuited from Figure18 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 Figure19, energy consumption is calculated in cumulative. As in E-MCDA and MCDA nodes grouping is made into layers, that is, flat layer NL1, clustering layer 1 NL2, clustering layer 2 NL3, 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 Figure20. 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,ΔE) increases and ultimately at a stage this Δ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 Figures22, 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 Figure25. 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 ∑(x-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 Figure27.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 layerNL1, clustering layer 1 NL2, clustering layer 2 NL3, 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 Figures28 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.



---

*Source: 902581-2015-09-29.xml*