Connectivity-Guaranteed Hybrid Topology Management Scheme for Improving the Operational Lifetime of 3-Dimensional Wireless Sensor Networks

Abstract

The battery of limited energy operates wireless sensor nodes, it is important to increase the lifetime of the wireless sensor network. The aim of our work is to design a hybrid topology management scheme for improving the lifetime of the wireless sensor networks with guaranteed connectivity. The sensing range of the sensor node is smaller than the radio range and hence there is a large number of nodes within the coverage area of a node. Hence the network connectivity can be maintained with less number of nodes. By using this fact, we can save energy by switching off the transceiver, which consumes most of the energy. On the other hand, the sensor node spends most of the time in monitoring state and the transceiver is idle. In the idle state the transceiver consumes almost the same energy as in receiving state. Hence putting the transceiver in the sleep mode when it is idle can save the significant energy. We have designed a hybrid topology management scheme for 3-Dimensional sensor networks by making use of these facts. Our hybrid scheme improves the lifetime of the 3-Dimensional sensor network by a factor of 19.

1. Introduction

When the sensor nodes are deployed on the earth surface where the height of the network is smaller than the transmission range of the node, then it is considered as the two-dimensional sensor network. In 2-dimensional sensor networks, all the nodes of the network are assumed to be residing on the same plane. Such an assumption is not suitable for the network which has application in space, atmosphere, and ocean [1, 2] because in such applications the height is greater than the transmission range [3]. When the height of the network is greater than the transmission range of the sensor nodes, then the network becomes three-dimensional sensor network. For example, in underwater application, the sensor nodes are placed at the different depth of the water to monitor the ocean column. Similarly, in atmosphere the sensor nodes are deployed at different height to monitor the climate.

In this paper, we worked on finding the suitable shape of the cell to partition the 3-dimensional sensor network into cells. We have also proposed the suitable topology management scheme for energy conservation in 3-dimensional sensor networks. The suitable shape of the cell is the shape which covers the entire field with minimum number of cells. For example, in 2-dimensional sensor network, the hexagonal cell [4, 5] is more suitable than the square-shaped cell. In the hexagonal structure, the height factor is not considered, but in 3-dimensional sensor network, the height factor has to be included, and hence we are using, cube, hexagonal prism, and truncated octahedron over hexagonal structure.

In this paper, first we have analyzed the cell partitioning using cube-shaped cells. Then, we partition the 3D network using hexagonal-prism-shaped cells. Finally, we have tessellated the three-dimensional space using truncated-octahedron-shaped cells. We compare all the shapes and find out the most suitable one.

We also provide the Hybrid topology management scheme, which reduces the energy consumption of the scheme and thus increases the operational lifetime of the sensor network. This Hybrid topology management scheme conserves energy by exploiting both density and time. The sensor network has higher node density because the sensing range of the node is smaller than the transmission range, and hence there are larger number of nodes within the sensor field. Therefore, the network connectivity can be maintained by having very few number of nodes in the active mode and put all other nodes in the sleeping mode. The sensor nodes spend most of their lifetime in monitoring rather than transmitting. Hence, putting the radio unit of the sensor nodes in sleep mode when they are being idle can save the significant energy.

2. Related Works

The aim of the topology management scheme [6–9] is to maintain the sufficient network connectivity between the nodes such that the data can be forwarded efficiently to the sink. In Geographic Adaptive Fidelity (GAF) scheme [3, 10, 11], a virtual grid is formed throughout the deployed network, and each node is assigned to the virtual grid cell in which it resides. Only a single node from a cell in the virtual grid is chosen to be active at any given time. As the density of a network implementing GAF increases, the number of active nodes per grid cell remains constant while the number of nodes per cell increases proportionally. Analysis and simulation studies of GAF show that it can consume 40% to 60% less energy than an unmodified ad hoc routing protocol.

Sparse Topology and Energy Management (STEM) is a topology management scheme [12, 13], which reduces the energy consumption of the sensor node at the cost of latency. STEM turns off the radio when it is idle and wakes up the radio when it is needed to transmit data to the sink. Now, the problem is that the radio of the next hop in the path to the data sink is still turned off. To overcome this problem, each node periodically turns on its radio for a short time to check whether any other nodes want to communicate with it. In order to avoid the interference between the wake up and the data packet transmission, dual radio with each radio operating at different frequency bands is used.

GAF controls the node density to save energy without affecting the data forwarding capacity. STEM saves energy by putting the radio of the sensor node into the sleep mode when they are not in use. We can get better result by utilizing the advantages of both schemes [12]. Fortunately, STEM and GAF are orthogonal to each other, and hence the resulting energy gain will be the full potential of both schemes. In Hybrid scheme, the GAF manages one of the nodes in each grid as a grid head based on its available energy. STEM controls grid head between the sleep mode and the active mode.

LEACH is a cluster-based technique where cluster head is elected by threshold-based random procedure [14]. It utilizes randomized rotation of local cluster heads to evenly distribute the energy load among the sensors in the network. LEACH can achieve as much as a factor of 8 reductions in energy dissipation and double the system lifetime compared with the conventional routing protocols. Cluster head drains quickly because it spends a large amount of energy to forward the data to the sink directly. It is restricted to networks of maximum sizes given by the maximum transmission range [15] of the cluster heads.

Hybrid energy-efficient distributed (HEED) [16] clustering protocol addresses the limitation of LEACH allowing cluster heads to be more than one hop away from the sink node. It guarantees intercluster connectivity so that scalability problem of LEACH is solved. In HEED, nodes with several power levels are available. Each node uses a smaller transmission level proportional to a square cell of size “c” to create the cluster. This creates the unreachable corner problem. HEED periodically selects cluster heads according to a Hybrid of their residual energy and a secondary parameter such as node proximity to its neighbors or node degree. The square cluster shape used in the HEED cannot be used in the three-dimensional wireless sensor networks. So, after selecting the suitable cell for three-dimensional networks, the cluster heads can be selected based on the residual energy concept used in the HEED.

Extensive research has been done on topology control issues in 2D wireless and ad hoc sensor networks. There is no significant work done on topology control issues in the context of 3D network. Wang et al. studied [17] the topologies for 3D sensor networks. The first question about 3D topology control is whether there exists an embedding method mapping a 3D network into a 2D plane so that all 2D geometric topology control protocols can still be applied, but there is no such mapping method that still keeps the scale of the edge length. Consider a regular tetrahedron in 3D where the distances between any two nodes from the four end points are the same. However, in a 2D plane, there is no graph formed for four nodes where the distances between any two nodes are the same. Therefore, simply mapping 3D networks to 2D ones does not work when we want to achieve power efficiency. Different geometric topologies were proposed to achieve the sparseness of the communication networks or to guarantee the package delivery of specific routing methods. Most of this was applied to two-dimensional networks. In [17], authors have extended the two 2D geometric topologies such as Relative Neighborhood Graph (RNG) and Gabriel Graph (GG) to 3D case and proposed 3D Yao-based topologies for sensor networks. This paper is just the first step of research for 3D topology control.

Huang and Tseng studied the coverage problem in 3D networks. This problem in a 2D space is solved in [18] with an efficient polynomial-time algorithm in terms of number of sensors. In [19], Huang et al. tackled this problem in a 3D space still feasible within polynomial time. The proposed solution can be easily translated into an efficient polynomial-time distributed protocol. They have not discussed anything about the topology-related issues.

Besides topology control, there is also some other research in 3D sensor networks. For example, Salhieh et al. [20] proposed a directional source-aware routing protocol and showed that the routing method can be applied to 3D sensor networks where sensors are located in a fixed 3D grid.

Li et al. [21] addressed the load-balancing routing problems in large-scale wireless networks. This aims to solve the uneven load distribution problem of current routing protocols and eliminate the crowded center effect.

However, in our approach, the shape of the grid is truncated octahedron whose volumetric quotient is high. In [17], the authors used cone-based approach where stacking is not as perfect as in the truncated octahedron. This improper stacking leads to overlapping and unreachable problem. This limitation is addressed in the proposed approach by selecting grid structure, which is very close to sphere in three dimension as the hexagonal structure is close to circle in the two-dimensional networks. The nodes in the network have low-power radio and high-power radio. The low-power radio is used for grid head selection within the grid. Also, the cluster architecture takes care of the load-balancing problem implicitly in our approach.

2.1. Motivation

The major design challenge in any sensor network is to increase the operational lifetime of the sensor node as much as possible, because the battery of limited energy powers the sensor nodes. The available energy should be utilized efficiently. In terms of energy consumption, the wireless exchange of data between the nodes will strongly dominate the other node functions such as sensing and processing. The radio in transceiver unit consumes almost the same energy in receiving and idle states. Most of the time, the sensor network is in monitoring state and the radio is being idle. Hence, the significant energy saving can be obtained by switching off the radio when it is idle. The purpose of studying the topology management scheme in 3-dimensional sensor network is to use the sensor network effectively in applications such as space, underwater, and atmospheric applications. It is predicted that WSN technology is one of the 21st century technologies and finds place for many ground-based application, and it is expected to extend the same for the above-mentioned application, and hence it is necessary to study the topology management scheme for such application.

2.2. System Model and Problem Description

We have used the following assumptions, definitions, and notations in our model.

Assumptions Made We assume the following:

(i)

uniformly random deployment of nodes,

(ii)

fixed transmission radius,

(iii)

sensing range is less than the transmission range,

(iv)

the height or depth of the network is greater than the transmission range,

(v)

boundary effects are negligible.

Notations and Definition

“VQ”:

the volumetric quotient, which will decide the closeness of the polyhedron to the sphere. As the volumetric quotient approaches to 1, the closeness to the sphere increases

“ r ”:

radius of circumsphere of the solid

“ x ”:

the average number of nodes within the coverage volume of the node

“ F ”:

the flat face surface, like the front or top of the box

“ E ”:

an edge along which two faces come together

“ V ”:

a vertex point on a shape, a corner where several edges come together.

2.2.1. Problem Description

In this work, some of the applications like underwater communication, space, and atmospheric require 3D topology management scheme, where sensors sense most of the events. In these types of application, the height or depth factor is taken into account for the deployment scenario. More particularly, when the height or depth of the deployed network is greater than the transmission radius of the network, then the 3D topology management scheme is required. Hence, in such application, wireless sensor network poses many challenges, and one of the challenges is network lifetime, and it is the major challenge having the direct consequence of the constraint availability of the resources in wireless sensor nodes. Wireless sensor nodes are battery powered; therefore, the network lifetime depends on how wisely the energy is used. In many applications it is very difficult to change or recharge the battery, or it is important to minimize the number of times the battery needs to be changed. In order to achieve long network lifetime, it is very important to operate sensors on a very low duty cycle. Therefore, by switching the transceiver, which consumes the largest energy into sleeping mode, combining the density topology management scheme will improve the network lifetime. When the height or depth of the deployed network is greater than the transmission radius, then the network is considered as the 3-dimensional network. In this work, height is taken as one of the design parameters for lifetime analysis of wireless sensor networks. The theoretical analysis for different structural placement is carried out, and then the solution to improve the network lifetime is proposed by using the Hybrid protocol for different structure.

The remainder of the paper is organized as follows. Section 3 provides the theoretical analysis, Section 4 provides performance evaluation, and Section 5 concludes the paper.

3. Theoretical Analysis

3.1. Cube

The cube has 6 equal square faces, 12 edges, and 8 vertices as shown in Figure 1. It has 26 first-tier neighboring cells. Out of these 26 neighboring cells, 6 cells sharing the common square plane, 12 cells sharing the common line, and 8 cells sharing the common point. The largest distance between two points in the neighboring cell is in the cells sharing the common point. To make all the nodes in a cell reach all other nodes in their 26 neighboring cells, the edge is set according to neighboring cell sharing the common point. The edge length $a_{c}$ of the cube is set as

a_{c} \leq \frac{R}{\sqrt{12}}

(1)

where R is the transmission range of the sensor node.

Figure 1

Cube.

The radius of circumsphere of the cube is given by

r_{c} = \frac{\sqrt{3} a_{c}}{2}

(2)

The volumetric quotient of the cube is 0.36755. It means that the cube with circumsphere radius $r_{c}$ can cover the 36.75% of the volume of the sphere with same radius r. Hence, a larger number of cube cells are needed to cover the entire field which increases the number of active nodes. Therefore, the energy consumption of the network will be comparatively high.

3.2. Hexagonal Prism

Since the volumetric quotient of the cube is low, we consider the hexagonal prism whose volumetric quotient is expected to be high because it has two hexagonal faces instead of square faces in cube. The hexagonal prism has 2 hexagonal faces, 6 square faces, 18 edges, and 12 vertices as shown in Figure 2. The hexagonal prism has 20 first-tier neighboring cells. Out of these, 2 cells are sharing the common hexagonal faces, 6 cells are sharing the common square faces, and 12 cells are sharing the common edges. The largest distance between two points in the neighboring cell is in the cells sharing the common edges.

Figure 2

Hexagonal Prism.

The edge length $a_{h}$ of the cube is set as

a_{h} \leq \frac{R}{\sqrt{17}}

(3)

where R is the transmission range of the sensor node.

The radius of circumsphere of the hexagonal prism is given by

r_{h} = \frac{\sqrt{5} a_{h}}{2}

(4)

The volumetric quotient of the hexagonal prism is 0.4438. It means that the cube with circumsphere radius $r_{h}$ can cover the 44.38% of the volume of the sphere with same radius $r_{h}$ . The volumetric quotient of hexagonal prism is low because the hexagonal prism has larger number of square faces than the hexagonal faces.

3.3. Truncated Octahedron

Since the Hexagonal Prism has comparatively low volumetric quotient, we have taken another polyhedron, truncated octahedron, whose shape is closer too sphere.

Joining two square pyramids together at their bases to form an octahedron and then cutting all six corners at one third of the edge length from each vertex create a truncated octahedron. The resulting truncated octahedron has edges of one third of the length of the octahedron edges. The geometry of the truncated octahedron and its top view of sectioned truncated octahedron, which is tessellated, are shown in the Figures 3 and 4, respectively. truncated octahedron is a polyhedron that has 14 faces. Out of these 14 faces, 8 are hexagon and 6 are square faces. The edges of the hexagon and square are of equal length.

Figure 3

Truncated Octahedron.

Figure 4

Top view of sectioned truncated octahedron after tessellation.

The truncated octahedron has 24 vertices and 36 edges. If the edge length of the truncated octahedron is $a_{t}$ , then the volume of the truncated octahedron is given by

V_{t} = 8 \sqrt{2} a_{t}^{3}

(5)

where

V_{t}

is the volume of the truncated-octahedron-shaped cell and

a_{t}

is the length of the edge of the truncated octahedron. The truncated-octahedron-shaped cell has 14 neighboring cells. Out of these 14 neighboring cells, 8 cells are sharing the common hexagonal plane and 6 are cells sharing the common square plane.

3.4. Edge Length Calculation

The distance between two opposite square faces of a truncated octahedron cell is $2 \sqrt{2} a_{t}$ . We tessellate truncated octahedron on square and hexagonal faces. The farthest point between the neighboring cells lies in the cells sharing the common square plane as shown in Figure 5. The distance between two opposite square faces in the neighboring cell becomes $4 \sqrt{2} a_{t}$ .

Figure 5

Fixing the edge length of the truncated octahedron.

From Figure 5, the transmission range R is calculated as

R = \sqrt{34} a_{t}

(6)

The edge length $a_{t}$ of truncated octahedron is

a_{t} \leq \frac{R}{\sqrt{34}}

(7)

To make all the nodes in the grid reachable to all the nodes in their neighboring cells, the upper bound of the edge length of the truncated octahedron is set as

a_{t} = \frac{R}{\sqrt{34}}

(8)

where R is the transmission range of the sensor node.

3.5. Radius of Circumsphere

The diameter of the circumsphere which is the line joining the opposite vertex of the opposite hexagonal faces is shown in Figure 6.

Figure 6

Radius of circumsphere of truncated octahedron.

The diameter circumsphere of the truncated octahedron is calculated as

D = \sqrt{10} a_{t}

(9)

The radius of circumsphere of the truncated octahedron is given by

r_{t} = \frac{\sqrt{10} a_{t}}{2}

(10)

The volumetric quotient of the truncated octahedron is given by

{VQ}_{t} = \frac{V_{t}}{(4 / 3) π r_{t}^{3}}

(11)

Substitute (5) and (10) in (11),

{VQ}_{t} = \frac{8 \sqrt{2} a_{t}^{3}}{(4 / 3) π {(\sqrt{10} (a_{t} / 2))}^{3}}

(12)

By simplifying (12), we get

{VQ}_{t} = \frac{24}{5 \sqrt{5} π}

(13)

The volumetric quotient value of the truncated octahedron is given by

{VQ}_{t} = 0.68329

(14)

The volumetric quotient of truncated octahedron is high compared with cube and hexagonal prism. This implies that the sensor field can be covered with less number of cells. truncated octahedron has more number of hexagonal faces than the square faces compared with other polyhedrons. Because of the above-mentioned reasons truncated octahedron is more suitable in three-dimensional sensor networks.

3.6. Proposed Model

Our proposed model with truncated octahedron cells for three-dimensional sensor networks is shown in Figure 7. We have assumed that all the nodes are having two radios. The sensor nodes are deployed in a uniformly random fashion over the 3D sensor field of size $35 \times 35 \times 40$ . Hollow circles indicate the sleeping nodes, and solid circles indicate the active nodes.

Figure 7

Proposed model.

The 3D sensor field is divided into a number of truncated octahedron cells, and in each cell only one node is kept in active mode and all other nodes are kept in sleep mode. The node in active mode will act as a cell head and take part in the data-forwarding function. The responsibility of being a grid head is rotated among the nodes in the cell based on the available energy level. When the energy level of the cell head reduces below the threshold energy level, the responsibility of cell head is transferred to another node in the grid. In the simulation, we have set the threshold energy level to 25%. In order to balance the energy consumption of the nodes, the duty of the grid head is rotated among the other nodes in the grid based on the residual energy. Hence, the lifetime of the network is increased. Once all the nodes in the grid reach the threshold level, the same procedure is repeated till the entire energy is drained. During this time, it is suggested that the nodes in the grid may be replaced in order to ensure the strong connectivity in the network. When a node is forwarding the data packets, the choice of the next hop node is based on the direction in which the destination sink node is present. When Sparse Topology and Energy Management (STEM) scheme is integrated, the dual radio concept of STEM is implemented in all the nodes including the grid head.

The basic idea of STEM is to only turn on the sensing and some processing circuitries. The transceiver unit is kept in off state. When the sensor node detects an event, it will wake up its main processor to process the data in detail. It will wake up its radio when it is needed to transmit data to the sink. Now, the problem is that the radio of the next hop in the path to the data sink is still turned off. To overcome this problem, each node periodically turns on its radio for a short time to check whether any other node wants to communicate with it.

The node that wants to communicate is called initiator node, and the node it is trying to wake up is called target node. The initiator node wakes up its target node by sending a beacon. When the target node receives the beacon, it will send a response to the initiator node, and both nodes turn on their radio. Once both nodes have turned their radio on, a link is established between them and data packet is transferred. If that packet is intended for other node, the target node will act as the initiator node and send packet to the node in the next hop towards destination and the process is repeated.

In order to avoid the interference between the wake up beacon and the data packet transmission, transceiver uses dual radio, and each radio is operating at different frequency bands. The frequency band $f_{1}$ with low-duty cycle is used to transmit the wake-up messages, and hence it is called wake-up plane. Once the target node has received a wake-up message, both nodes will turn on their radio operating at frequency band $f_{2}$ . The original data packets are transmitted in this plane and hence called data plane.

3.7. Integration of STEM and GAF

GAF controls the number of active nodes to save energy without affecting the data-forwarding capacity. STEM saves energy by putting the radio of the sensor node into the sleep mode when they are not in use. The energy savings will be better when we combine the advantages of both schemes. For combining any two schemes, they have to be orthogonal to each other. STEM and GAF are orthogonal to each other and hence the resulting energy gain will be the full potential of both schemes.

In GAF, the sensor field is divided into number of virtual truncated octahedron cells and in each grid only one node is kept in active state. The node in active state will act as the grid head and take part in the data forwarding function. In the combined scheme, GAF manages one of the nodes in each cell as cell head based on its available energy. STEM controls cell head between the sleep mode and the active mode.

The energy consumption of a sensor node when there is no GAF is obtained as follows:

E_{0} = P_{0} T

(15)

where

P_{0}

is power consumption of a node and T is the time duration of power consumption.

In GAF, only one node out of $n^{'}$ node in the used grid is active at a time. Hence, the active time of the node is reduced by $n^{'}$ times.

The energy consumed by a node in GAF is obtained as follows:

E = \frac{P_{0} T}{n^{'}}

(16)

Substituting (15) in (16),

E = \frac{E_{0}}{n^{'}}

(17)

When the STEM is interacted with GAF, the power consumption of the node becomes

E = \frac{E_{data} + E_{wakeup}}{n^{'}}

(18)

where E is the energy consumption of a node with Hybrid scheme,

E_{data}

is the energy consumption of a node in data plane,

E_{wakeup}

is the energy consumption of a node in wake-up plane, and

n^{'}

is the average number of nodes in the used grid.

4. Performance Evaluation

We verify our algorithm through simulations. We deploy N number of nodes in a uniformly random fashion over the 3D field of size $35 \times 35 \times 40$ , and each node has transmission range R. For a network having large number of deployed nodes $(N)$ , the coverage density of a node is calculated from node density and coverage volume and denoted by the parameter x

x = \frac{N}{L \times B \times H} \frac{4}{3} π R^{3}

(19)

where x is the average number of neighbor, which denotes the average number of nodes within the coverage volume of the node, L, B, and H are the length, breadth, and height of the sensor field, respectively.

(4 / 3) π R^{3}

is the coverage volume of the node. The average number of sleeping nodes in the neighboring grids is around 600, and the active nodes for cube, hexagonal prism, and truncated octahedron are 26, 20, and 14 topology, respectively, that are spread over the coverage volume. These active nodes are going to share the channel. This type of network finds an application in space, atmosphere, and ocean.

4.1. Simulation Setup

In our simulation we have chosen the transmission range $R = 20$ m, and the number of nodes $(N) = 1050$ which has the radio characteristics as shown in Table 1.

Table 1

Radio characteristics.

Radio mode and its timing parameter	Power consumption and duration of timing parameter
Transmit ( $P_{Tx}$ )	14.88 mW
Receive ( $P_{Rx}$ )	12.50 mW
Idle	12.36 mW
Sleep	0.016 mW
Observation time ( $T_{obs}$ )	1000 sec
Time to receive at least one beacon ( $T_{Rx}$ )	225 mS
Wake-up interval (T)	600 mS
Setup time ( $T_{setup}$ )	375 mS

We divide the 3D field of size $35 \times 35 \times 40$ into number of cube cells of size $a \times a \times a$ , and we have simulated the GAF scheme. Then we have integrated the dual radio concept of STEM into the GAF. Then the same process is repeated with Hexagonal Prism and truncated octahedron cells.

Algorithm 1 explains the Hybrid topology management scheme using truncated octahedron cells in 3-dimensional sensor networks.

Algorithm 1: Hybrid scheme with truncated octahedron cells.

$r_{t} \leftarrow 0.2711 \times R$

// Where $r_{t}$ is the radius of the truncated octahedron cell and R is the radio range of the sensor node

Assigning the coordinates of a truncated octahedron

for $i = 1$ to 24

$x_{v} (i) \leftarrow x$ coordinate of vertex i

$y_{v} (i) \leftarrow y$ coordinate of vertex i

$z_{v} (i) \leftarrow z$ coordinate of vertex i

end

Finding cell ID of each node

for $i = 1$ to n

for $j = 1$ to m

$D_{i j}$ ← Distance from the node i to the center of cell j.

if $D_{i j} \leq r_{t}$

cell_i $d_{i} \leftarrow j$

end

End

//where $r_{t}$ is the radius of the truncated octahedron cell, n is the number of nodes and m is the total number of cells

for $j = 1$ to m

for $i = 1$ to n

if $cell_i d_{i} = j$

cell_co $n_{j} \leftarrow$ cell_co $n_{j} + 1$

end

//where cell_co $n_{j}$ is the number of nodes present in cell j, n is the number of nodes and m is the total number of cells

for $i = 1$ to n

$E_g s_{i} \leftarrow E_stem$ /cell_con ( $cell_i d_{i}$ )

End

//where $E_g s_{i}$ , $E_s t e m$ are the energy consumption of the node i under Hybrid scheme and STEM, respectively.

4.2. Simulation Results

The cell partitioning of the 3D network using cube-shaped cells is shown in Figure 8, where the sensor field is divided into number of cube-shaped cells.

Figure 8

3D network with cube cells.

Figure 9 shows the cell partitioning of the 3D network using Hexagonal-Prism-shaped cell, where the sensor field is divided into number of Hexagonal Prism-shaped cells.

Figure 9

3D network with HP cells.

Figure 10 shows the cell partitioning of the 3D network using truncated-octahedron-shaped cell, Where the sensor field is divided into number of truncated-octahedron-shaped cells. The operational lifetime of the sensor network is improved by reducing the energy consumption of the sensor nodes. The topology management scheme is implemented by dividing the sensor field into number of cells. The size of the cells is fixed based on the radio transmission range. In each cell, one node is kept in active mode and all other nodes are in sleep mode. Since the size of the cells is set such that all the nodes in their first-tier neighboring cells can reach all the nodes in a cell, it is possible to perform data forwarding function with single node in each grid.

Figure 10

3D network with TO cells.

In sleep mode, the sensing and processing units are kept on and the radio unit is switched off. Whenever the sleeping node has data to send, it will turn on its radio unit. The active node in each cell will act as the cell head and take part in the data forwarding process.

Since all the nodes are having the same energy initially, so the grid head is selected randomly in each grid. In order to balance the energy consumption of the nodes, the duty of grid head is rotated among the nodes in the cell. Successively, grid head is selected based on the residual energy technique used in the HEED. Therefore, all the nodes in the grid will be getting the chance of grid head. In GAF, only one node out of $n^{'}$ node in the used grid is active at a time. Hence, the active time of the node is reduced by $n^{'}$ times.

In cube cell, the average number of nodes per cell is 4 to 5; in the hexagonal prism, the average number of nodes per cell is 6 to 7; and in the truncated octahedron, the average number of nodes per cell is 9 to 10. Since all the nodes are having the same energy initially, grid head is selected randomly in each grid. Successively, grid head is selected based on the residual energy technique used in the HEED.

Even if every node in the grid participates in the grid head selection process, the maximum number of nodes within the grid is 9. Each and every grid is going to select its head independently, and hence this process will not take long time. The node which is not the grid head from the beginning still has got sufficient amount of energy to participate in the selection process and become a grid head.

Figure 11 shows the normalized energy consumption of the node in GAF using cube, hexagonal prism, and truncated octahedron cells. When the average number of sleeping nodes in the neighboring grid is 600, the normalized energy consumption of the sensor node is 0.31 for cube-shaped cells, 0.19 for Hexagonal Prism, and 0.15 for truncated-octahedron-shaped cell partitioning of the 3D sensor field. GAF using truncated octahedron cell consumes less energy than cube and Hexagonal Prism cells. Hence, we have taken the truncated octahedron cell for designing the Hybrid topology management scheme.

Figure 11

Energy comparison of a node in GAF using cube, HP, and TO cells.

Figure 12 shows the percentage of connectivity as the function of number of nodes deployed. The topology management scheme, which uses truncated octahedron partitioning, maintains full connectivity with less number of nodes. It is achieved because truncated octahedron has high volumetric quotient. This high volumetric quotient results in less number of grids and hence full connectivity is maintained with less number of active nodes.

Figure 12

Percentage connectivity versus nodes deployed.

Figure 13 shows that the number of active nodes required in the network to maintain full connectivity is minimized while partitioning the network using truncated octahedron cells. Since the number of active nodes required for maintaining the connectivity is less, the total energy consumed by the network is much less. Hence, the lifetime of the network is increased to a larger extent.

Figure 13

Number of active nodes required to maintain 100% connectivity.

Figure 14 shows the normalized energy consumption of the sensor node in the network under GAF, STEM, and Hybrid scheme using truncated-octahedron-shaped cell. In STEM, the energy consumption of the node is constant with respect to the average number of neighbors, because STEM works on the time domain.

Figure 14

Energy consumption of a node in GAF, STEM, and Hybrid scheme using truncated octahedron cells.

The energy consumption of a node in GAF decreases with the average number of neighbors' increases, because the GAF algorithm is related to the density domain. When STEM is integrated with GAF, we got further reduction in the energy consumption of the sensor node. When the average number of sleeping nodes in the neighboring grids is 600, the normalized energy consumption of the sensor node is 0.15 for GAF using truncated-octahedron-shaped cell partitioning in 3D sensor field and the normalized energy consumption of the sensor node is 0.054 for Hybrid topology management scheme in 3D sensor networks.

Figure 15 shows the operation lifetime extension factor of the sensor node in GAF using truncated octahedron cells and in Hybrid topology management scheme. The operational lifetime of the sensor network is improved by 7 times in GAF using truncated-octahedron-shaped cells, and the operational lifetime is improved by 19 times in Hybrid topology management scheme when the average number of sleeping nodes in the neighboring grid is 600.

Figure 15

Lifetime improvement in GAF and Hybrid scheme using truncated octahedron cells.

5. Conclusion

In this paper, we have analyzed the GAF scheme using cube, Hexagonal-Prism, and Truncated-Octahedron shaped cells, and we have found that the truncated octahedron cell gives better performance than the Cube and Hexagonal-Prism shaped cells. GAF with truncated octahedron cells reduces the consumption of the node by 7 times when the average number of sleeping nodes in the neighboring grid is 600.

On the other hand, STEM reduces the energy consumption of the sensor node by switching its radio off when it is idle. In this work we simulate STEM with wake-up interval of 600 ms, which reduces the energy consumption of the node by a factor of about 2.5.

We have integrated STEM with GAF, and the Hybrid scheme reduces the energy consumption of the sensor node by 18 times in the three-dimensional sensor networks when the average number of sleeping nodes in the neighboring grid is 600. Hence, the Hybrid topology management scheme improves the lifetime of the sensor network by 19 times.

References

Akkaya

Newell

Self-deployment of sensors for maximized coverage in underwater acoustic sensor networks

Computer Communications 2009 32 7–10 1233 1244

2-s2.0-65649114733

10.1016/j.comcom.2009.04.002

Jurdak

Baldi

Lopes

C. V.

Software-driven sensor networks for short-range shallow water applications

Ad Hoc Networks 2009 7 5 837 848

2-s2.0-60249097613

10.1016/j.adhoc.2008.07.012

Matsumae

Tsiatsis

Srivastava

M. B.

Energy-efficient cell partition of 3D space for sensor networks with location information

Network Protocols and Algorithms 2009 1 2

Liu

R. P.

Rogers

Zhou

Zic

Topology Control with Hexagonal Tessellation

February 2003

Chuan-Yu

Cheng-Wei

Jia-Shung

Reliable grouping GAF algorithm using hexagonal virtual cell structure

Proceedings of the 3rd International Conference on Sensing Technology (ICST ′08)

November-December 2008

Tainan, Taiwan

600 603

2-s2.0-63049098385

10.1109/ICSENST.2008.4757176

Akyildiz

I. F.

Sankarasubramaniam

Cayirci

A survey on sensor networks

IEEE Communications Magazine 2002 40 8 102 114

2-s2.0-0036688074

10.1109/MCOM.2002.1024422

I. M.

Yang

A survey on topology issues in wireless sensor network

The International Society for Optical Engineering

April 1999

Orlando, Fla, USA

229 237 Proceedings of SPIE

Bien

Mori

Heidemann

Estrin

Topology Control Protocols to Conserve Energy in Wireless Adhoc Networks

January 2003

Gamwarige

Kulasekere

A cluster based energy balancing strategy to improve wireless sensor network lifetime

Proceedings of the 2nd International Conference on Industrial and Information Systems (ICIIS ′07)

August 2007

Kandy, Sri Lanka

403 408

2-s2.0-51549091590

10.1109/ICIINFS.2007.4579211

10.

Heidemann

Estrin

Geography-informed energy conservation for ad hoc routing

Proceedings of the 7th Annual International Conference on Mobile Computing and Networking (MobiCom ′01)

July 2001

Rome, Italy

70 84

2-s2.0-0034772133

11.

Jiang

Agah

Topology control for secured coverage in wireless sensor networks

Proceedings of the IEEE Internatonal Conference on Mobile Adhoc and Sensor Systems (MASS ′07)

October 2007

2-s2.0-50249132548

10.1109/MOBHOC.2007.4428757

12.

Schurgers

Tsiatsis

Srivastava

M. B.

STEM: Topology Management for Energy Efficient Sensor Networks

IEEEAC paper #260, Updated September 2001

13.

Schurgers

Tsiatsis

Ganeriwal

Srivastava

Optimizing sensor networks in the energy-latency-density design space

IEEE Transactions on Mobile Computing 2002 1 1 70 80

2-s2.0-3042785191

10.1109/TMC.2002.1011060

14.

Heinzelman

W. R.

Chandrakasan

Balakrishnan

Energy-efficient communication protocol for wireless microsensor networks

Proceedings of the 33rd Annual Hawaii International Conference on System Siences (HICSS ′00)

January 2000

1 10

2-s2.0-0033877788

15.

Labrador

M. A.

Wightman

P. M.

Topology Control in Wireless Sensor Networks 2009

New York, NY, USA

Springer

16.

Younis

Fahmy

HEED: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks

IEEE Transactions on Mobile Computing 2004 3 4 366 379

2-s2.0-10944266504

10.1109/TMC.2004.41

17.

Wang

Dahlberg

T. A.

Energy-efficient topology control for three-dimensional sensor networks

International Journal of Sensor Networks 2008 4 1-2 68 78

18.

Huang

C. F.

Tseng

Y. C.

The coverage problem in a wireless sensor network

Proceedings of the ACM International Workshop on Wireless Sensor Networks and Applications (WSNA ′03)

2003

115 121

19.

Huang

C. F.

Tseng

Y. C.

L. C.

The coverage problem in three-dimensional wireless sensor networks

Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM ′04)

December 2004

3182 3186

2-s2.0-18144362070

20.

Salhieh

Weinmann

Kochhal

Schwiebert

Power efficient topologies for wireless sensor

Proceedings of the International Conference on Parallel Processing

2001

21.

Chen

Wang

Chen

Load balancing routing in three dimensional wireless networks

Proceedings of the IEEE International Conference on Communications (ICC ′08)

May 2008

Beijing, China