Optimal Placement of Relay Nodes in Wireless Sensor Network Using Artificial Bee Colony Algorithm

I. Introduction

• Relay nodes can reduce sensor energy use but are more expensive than ordinary sensor nodes, making cost and connectivity important constraints in 3-D deployment.The wide 3-D search space yields different connectivity levels at different positions, motivating careful optimization.Source: §I · p. 2
• ILDCC uses a two-phase ABC-based deployment in 3-D: the first phase connects the backbone with few relays, and the second searches for lifetime-improving positions while maintaining connectivity.The paper frames the placement problem as NP-hard and describes the two-phase approach as a way to circumvent this complexity.Source: §I · p. 2

II. Related Work

• Earlier approaches address disconnections through grid placement, redundancy, mobility, or grid-cell relay selection, while O3DwLC uses MST initialization and second-phase semidefinite optimization.The cited grid-cell selection problem is described as NP-hard.Source: §II · p. 3
• Unlike cited work focused on optimal sensor placement, this study targets network lifetime through optimal relay-node deployment and describes its algorithm as less complicated than existing solutions with similar objectives.The cited comparison includes Udgata et al. (2011), Mini et al. (2014), Abidin et al. (2014), and Liu and He (2014).Source: §II · p. 3

A. Assumptions

• Sensor nodes occupy the lower layer, while cluster heads, relay nodes, and the base station form the upper layer of the hierarchy.The formulation centers on the heterogeneous network devices and their separation into two layers.Source: A. Assumptions · pp. 3–4
• Lower-layer sensors send measurements to an RN or CH over short distances and sleep when not sensing or transmitting; upper-layer devices relay data toward the base station.Upper-layer devices are described as having better capabilities and longer transmission and reception ranges.Source: A. Assumptions · p. 4
• The formulation assumes sensor nodes have sufficient resources and counts communication energy, treating sensing and packet encapsulation costs as much smaller.The two-layer architecture is used to decouple upper- and lower-layer energy consumption.Source: A. Assumptions · p. 4
• All nodes are assumed static.Source: A. Assumptions · p. 4
• The application is assumed to gather data periodically, with sensors sending to their CH and CHs forwarding to another CH or relay node.Source: A. Assumptions · p. 4
• Communication is assumed to be multi-hop, with all CHs sharing one transmission range and all relay nodes sharing range r.Source: A. Assumptions · p. 4
• The MAC layer is assumed ideal, with no collisions or retransmissions.Source: A. Assumptions · p. 4

B. Energy Consumption

• The adopted energy model uses hardware parameters, packet length, transmitter–receiver distance, and path-loss exponent to describe transmission energy, alongside receiver energy.The prose identifies β, ϵ1, and ϵ2 as transceiver hardware parameters, L as packet length, d as Euclidean distance, and γ as path-loss exponent.Source: B. Energy Consumption · p. 4
• Node energy accounting includes packet arrival rates for transmission, reception, and aggregation, along with initial energy and per-packet energy costs.T, R, and A denote transmitted, received, and aggregated packet arrival rates per round; Jtx, Jrx, and Ja are per-packet energy costs.Source: B. Energy Consumption · p. 4
• Relays near the sink consume energy faster because they forward other nodes’ data more often, and the model represents traffic handled due to other nodes with k.Source: B. Energy Consumption · p. 4

C. Network Lifetime Definition

• Lifetime runs from relay-node deployment until network partition, which occurs when algebraic connectivity falls below a threshold because depleted RNs or CHs can no longer relay data.The adopted cutoff uses total backbone energy rather than individual node energy; the threshold may vary with application and backbone electronics.Source: C. Network Lifetime Definition · p. 4

D. Problem Statement

• The problem takes grid locations of sensor nodes, cluster heads, and the base station as fixed inputs.The sensing task has prespecified device locations.Source: D. Problem Statement · p. 4
• Relay-node locations must maximize network lifetime while satisfying cost-budget and connectivity constraints.Source: D. Problem Statement · p. 4
• The proposed solution determines grid positions for second-phase relay nodes to enhance overall network lifetime.Source: D. Problem Statement · p. 4

IV. The Proposed Deployment Strategy

• ILDCC is an adaptive, heuristic Artificial Bee Colony approach for two-phase relay-node deployment in 3-D space.Source: §IV · p. 5
• The paper uses a two-layer architecture to address the NP-hard deployment setting.Source: §IV · p. 5
• The deployment adopts SP3D’s cubic grid model, while grid vertices may also be arranged in regular shapes such as pyramids.Source: §IV · p. 5

A. First Phase of the ILDCC

• The minimum spanning tree constructs the backbone with first-phase relay nodes, and is used for comparison with SP3D.The text says MST ensures connections among relay nodes, cluster heads, and the base station.Source: A. First Phase of the ILDCC · p. 5
• The backbone is represented by a Laplacian matrix whose off-diagonal entries are −1 for connected node pairs and whose diagonal entries give node degrees.The matrix is described as symmetric and semidefinite.Source: A. First Phase of the ILDCC · p. 5
• The second-smallest Laplacian eigenvalue is the algebraic connectivity; a value of zero means the backbone is totally disconnected.The text gives λ2 = 0.1764 for its 10-node, 12-link example and notes that removing node 3 can partition the network.Source: A. First Phase of the ILDCC · p. 5
• Algorithm 1 starts with the closest pair of input nodes, connects them with the minimum required relays, then repeatedly joins the remaining node using the smallest relay requirement.The algorithm outputs cluster-head, base-station, and relay coordinates forming the backbone.Source: A. First Phase of the ILDCC · p. 5
• The Wiener index is defined from graph-vertex distances, and the average distance µ(G) is derived from it with a vertex-pair normalization.The factor 1/2 compensates for counting each path between two vertices twice.Source: A. First Phase of the ILDCC · p. 6
• The revised average-distance expression includes deviations from the real value, and the paper says this makes the solution robust across practical scenarios.Source: A. First Phase of the ILDCC · p. 6
• The uncertainty term may include energy wasted through collisions and retransmissions, but its upper bound must be established to guarantee a good solution.Source: A. First Phase of the ILDCC · p. 6

B. Second Phase of the ILDCC

• Second-phase relay positions are optimized to minimize the backbone’s µw(G), subject to a constraint on the number of relays deployed.Source: B. Second Phase of the ILDCC · p. 6
• The paper relates deployment cost directly to the number of second-phase relays, favoring solutions with fewer relays.Source: B. Second Phase of the ILDCC · p. 6
• The lifetime derivation defines initial rounds after first-phase deployment and accounts for extra energy and extra rounds from adding second-phase relays.The passage introduces the overall lifetime as a total number of rounds.Source: B. Second Phase of the ILDCC · p. 6

• Employed and onlooker bees search for solutions, while scout bees control the search process; food-source position represents a solution and nectar quality its objective value.Source: C. Implementation of the ABC Algorithm · pp. 6–7
• Connectivity is modeled as the probability that devices separated by distance d can communicate, with distance and site obstacles or terrain affecting that probability.Source: C. Implementation of the ABC Algorithm · p. 7
• ABC minimizes an objective under cost and λ2 constraints by optimizing off-diagonal Laplacian entries as 0 or -1 and updating the diagonal entries.Source: C. Implementation of the ABC Algorithm · p. 7
• The algorithm randomly searches candidate SPRN positions, updates the Laplacian matrix, and discards solutions whose eigenvalue falls outside the predefined range.Source: C. Implementation of the ABC Algorithm · pp. 7–8
• The selected solution is evaluated for average distance from its best eigenvalues, and the updated Laplacian matrix shows connected neighboring nodes.Source: C. Implementation of the ABC Algorithm · p. 8

V. Simulation Results

• The first simulation uses 9 CHs and 1 BS, varies relay nodes from 10 to 50, and assesses cost by relay count and lifetime by connected rounds.Lifetime is the rounds the network remains operational after relay deployment.Source: §V · p. 8
• The simulations set normalized ∆µ(G) to 0.1 and use normalized average internode distance, lifetime, and connectivity for a global energy-efficiency picture.Absolute lifetime depends on factors including area, active-sensor density, data-generation rate, and relayed data volume.Source: §V · p. 8
• Across eight runs with different initial populations, average results were close to individual-run values, which the authors describe as robust despite 200 ABC iterations.For network size 20, the objective function changed little near 200 iterations.Source: §V · p. 8
• Overall connectivity stays within the specified range, while average distance in the connected backbone decreases as relay nodes increase in both strategies.Figure 7 charts connectivity against number of nodes.Source: §V · p. 9, Figure 7 · p. 11
• At N = 40, ILDCC achieves around 50% decrement in normalized average distance than SP3D.Figure 4 plots normalized average distance against number of nodes.Source: §V · p. 9, Figure 4 · p. 10
• At 600 ppr, at least 50 relay nodes must be deployed to handle that traffic level and achieve a network lifetime of at least 10 rounds.As traffic increases, energy used for transmitting and receiving packets increases.Source: §V · pp. 10–11

VI. Conclusion

• The deployment sets up the network backbone with a minimum spanning tree protocol, then uses Artificial Bee Colony to optimize SPRN positions for lifetime maximization.The authors describe the strategy as cost effective and easy to implement.Source: §VI · p. 11
• Increasing relay-node numbers elevates the possibility of collision and interference, which data-link-layer protocols can minimize.Source: §VI · p. 11
• The proposed technique is slated for benchmarking against other ABC-based algorithms on complexity and convergence, while base-station mobility is future work.Source: §VI · p. 11