A Gateway Deployment Heuristic for Enhancing the Availability of Sensor Grids

Abstract

Wireless sensor grids form a special class of sensor networks that find more applicability than their randomly deployed counterparts in many commercial applications due to innate regularity in their design and operation. In contemporary wireless sensor grids, primarily single gateway sensor grids, each node senses the information and follows a relay relationship with gateway forming a multisource single receiver paradigm and pursues an added energy consumption pattern that serves as a premier bottleneck in wireless sensor grid environment. This research focuses on statistically modeling the energy consumption of single gateway sensor grids in terms of network availability by analyzing different energy consumption phenomena with communication as a grid-wide routing problem. On the basis of our findings and results in conjunction with Moor's law of semiconductors and batteries, we propose a linear programming heuristic for multiple gateway deployment to reduce network survivability costs and optimize communication for wireless sensor grids. We then present a case study using the proposed heuristic that is augmented through a node scheduler for nearest gateway connectivity, collision avoidance, and fairness, to show the performance gain that presents an ultimate cut-through energy paradigm.

1. Introduction

In recent times wireless sensor networks have evolved in order to fit into application-specific requirements and service classes. One such classification is based upon the adopted strategy to deploy sensors in the region of interest (ROI). For example, nodes are deployed in an ad hoc manner in military applications where mission criticality takes priority over cost. Likewise, commercial applications such as factory and home automation require minimization of cost and thus a high profitability. In either of these deployments, sensor networks face a common challenge of optimizing serviceability by minimizing usage of a limited battery. Wireless sensor grid (WSG) is a derivative concept of sensor networks that assumes an embedded topological uniformity in the arrangement of sensor nodes. It has been considered as a viable business proposition due to the following advantages:

(a) Before and during Deployment

• (i)

Grids render an ease of deployment due to the exhibited regularity in the physical infrastructure of buildings, streets, and other locations.

(ii)

Grids make the simplification and tailoring of node and network operations possible. For example, routing mechanism due to in hand knowledge of nodes' locations, identification of sources and sink(s), reduces down to mere grid lattice traversal. Similarly, the assignment of sleep mode duty cycles, to implement the energy conservation, becomes a node location problem [1, 2].

(b) After Deployment

• (i)

Grids provide better coverage of ROI [3] under the constraint that the node density is minimized for communication optimization.

(ii)

Grids offer better connectivity under a coverage constraint [3].

(iii)

Grids allow an ease and relief in diagnosis while a failure has occurred.

This research presents a comprehensive analysis of energy consumption through different constituent phenomena in contemporary sensor grids. It further identifies the phenomenon that consumes the major portion of this energy expenditure and proposes a cut-through energy paradigm to minimize energy consumption for this particular sensor grid phenomena to reduce the overall energy expenditure of the sensor grid. We start with analysis of the energy consumption of the most common and widely known sensor grid deployment architecture, the single gateway sensor grid (SGSG). In such an arrangement, all the nodes in the ROI sense and relay information towards the gateway, making it a multiple source, single sink architecture. Our findings lead us to the next and a natural step of modeling, optimization of energy resources of a sensor grid as we propose a multiple gateways deployment heuristic for a sensor grid. We show through a specific scenario of multiple sources multiple sinks that such heuristic is very useful in minimizing the initial and recurrent costs of a WSG. In this paper, we focus on the energy consumption of such sensor grids.

We analyze most, if not all, aspects of WSGs that contribute towards and affect the energy consumption. Specifically, our contributions are as follows:

• (i)

The analysis of network availability in terms of energy consumption of a relay customizable in a single gateway WSG (SGWSG).

(ii)

An analysis of various performance metrics under numerous node and network parameters.

(iii)

A linear programming- (LP-) based heuristic to reduce network survivability costs. It is based on the Moore's law of semiconductors and batteries.

(iv)

A node scheduler for nearest gateway connectivity, collision avoidance, and fairness.

The paper is organized as follows. Section 2 summarizes contemporary research activities and related work. Section 3 deals with the rationale to demonstrate a typical wireless sensor grid model, formulate conditions, and make necessary assumptions to make it as much as practicable. Section 4 puts forward the derivation of a stochastic expression for determining the availability of sensor grids. In Section 5 we present a simulation-based analysis of the availability expression and reveal our findings in Section 6. A deployment heuristic is proposed as a linear programming model to deploy multiple gateways around the sensor grid in Section 7 which simultaneously contains a node scheduler. We present some numerical results from a case study in Section 8. Finally Section 9 concludes the paper along with the identification of prospective future directions.

2. Related Work

In this section, we present the contemporary research work related to energy consumption analyses of wireless sensor networks with trio dimensional approach. Primarily, the aspects in the analysis of energy consumption of wireless sensor networks in general are presented. The efforts to model and optimize various energy consumption phenomena are particularly summarized (in sensor grids) as secondary discussion phase of this section. Lastly, the energy optimization strategies through the smart deployment of sensor nodes and sinks are summed up for both random and grid deployments of sensors. We have taken into broader account the fact that the usability of individual sensor nodes is gauged by their continued operation in the form of alive and connected sensor network. This is an issue of network availability or equivalently network longevity. A number of interpretations of network availability have been identified in [4], where each has the potential to emerge into a distinct research direction in its own right. This research effort is a good rudimentary, albeit theoretical cue for proposing energy efficiency measures in WSNs. Tilak et al. [5] identify various architectural, functional, and application-oriented aspects of WSNs that may all be considered to extend the longevity of networks they form, while meeting performance objectives amicably. However, it only serves as a generalized guideline.

Zhu and Papavassiliou propose bit-level energy consumption models for sensor nodes as lifetime measure that can be shown to iteratively yield entire WSN lifetime [6]. They consider a simplifying assumption that all the nodes have the same initial energy, which is true at the network initialization time but does not manifest real network dynamics. For example, with spatio-procedural heterogeneity, the energy states soon turn temporally exponential in distribution. Rai and Mahapatra through [7] present a mathematical model for WSN lifetime by assuming multihop communication over linear and ring topologies of sensor nodes. They propose Continuous Time Markov Chain (CTMC) analysis to model WSN lifetime as an optimal routing-over-topology phenomenon. It emphasizes on multihop communication through neighboring nodes, where the transmission cost to reach each adjacent neighbor is the same. It is a rigid model because in practical topologies, radio adjacency does also incorporate transmission power and reception power variability. Another work in Markov Chain modeling of WSN lifetime has been demonstrated by Saito and Minami [8]. They define and derive network availability expression as a measure of network lifetime. It is the most practicable expression in the sense that it subsumes topological connectivity in addition to establishing a relationship among sensor nodes' states (active or inactive), sensor network parameters, and the network availability. This research endeavor is however constrained in various ways. For example, their expression is for a linear arrangement of sensor nodes only. Consequently, there is no consideration given to the communication phenomena arising in planar topologies including routing, variable transmission, and reception models, intermediate node failures in planar topologies, and consequent retransmissions.

Duarte-Melo and Liu [9] present a lifetime estimate for cluster-based heterogeneous ad hoc sensor networks with an avid focus on the energy consumption imbalance between normal sensor nodes and cluster heads. Since their primal focus is on network heterogeneity, their lifetime expression is tightly coupled with rounds. Their lifetime expression, however, does not incorporate the effect of the placement of such cluster heads within the topology. In the domain of WSN energy optimization and balancing strategies, Schurgers et al. [10] suggest a scheme to adjust the sleep-awake periods of sensor nodes for energy optimization using two radios, one for waking up a sleeping node and another for data transmission. Together, they extend the operational lifetime of WSNs. The mathematical expression for inferring the operational lifetime of a sensor node and hence WSN is the energy consumption model. Their expression embodies the radio aspects including on-off scheduling for waking up a node and data transmission. However, the expression does not include the practical considerations where either (a) dual radio interfaces are not available in sensor node hardware or (b) wakeup failures occur and consequently retransmissions take place, all adding to the energy consumption of sensor nodes.

Liu and Li [11] establish a relationship between node transmission power control and network-wide connectivity by suggesting topology control algorithms and protocols. They assert that network-wide connectivity is an indirect, yet a good measure of network life time. Nonetheless, there is no mathematical substantiation to this effect. Assuming most of the ad hoc deployments, the studies of randomly deployed sensor nodes and networks seldom, or even never, consider exploiting prior knowledge (e.g., node IDs, location information of sensor nodes, and location of sinks) in order to maximize objective functions, such as to improve communication performance and optimize energy and reduce delays. It is unarguably true that sensor networks, when placed as a lattice, such as in a rectangular grid make network planning significantly simpler than pure random placement. For example, in smart homes telematics applications and for military applications (surveillance, etc.), it would allow flexibility and simplification in design and deployment due to a fair amount of in hand knowledge about the environment [12]. Exceedingly complex and computationally expensive schemes for sensor networks may therefore be reduced into their light-weight equivalents by utilizing such a knowledge base.

Zhang and Hou show in [3] that deterministic deployment of sensor nodes such as grid deployment yields better coverage and connectivity than their random counterparts. This work is merely a geometric analysis of geographical coverage favoring grid deployment over random deployment. Issues related to communicating over grids are not addressed here. Biagioni and Sasaki have computed the number of nodes in grids and other topologies deterministically in [13]. Their considerations include the transmission range, coverage of sensed region, and the degree of a node, which is the number of nodes within its transmission range. Their work however falls short of presenting sink node placement strategies for these regular topologies. Shakkottai et al. [14] compute the upper bounds on the number of hops that broadcast messages traverse during route discovery in sensor grids. Their work focuses on the numerical modeling on drawing the conditions for necessity and sufficiency. They do not propose or advance any algorithmic aspects of sensor grids.

Yu et al. [1] and Xu et al. [2] determine that nodes that know their geographical locations which can actually use this information to conserve energy. They put forward the concept of a virtual grid such that sensors are divided into subrectangular regions under a constraint that the maximum distance between any communicating nodes in adjacent grids is less than their effective transmission range. Their energy conservation strategy is based on the notion of a leader, which is the only awake node in a subrectangular region. Their concept is significantly different from a physical sensor grid which adopts lattice traversal for routing and a sleeping node can actually be an isolate part or whole of the network. In [15], Huang et al. highlight the role of adjusting transmission power dynamically to make a sensor grid resilient to node failures and the resulting routing holes problem. Their work provides basis for dynamic power control only in large deployments of sensor grids wherein redundant routes towards the sink are also possible. Finally in [16], Haenggi presents a range of strategies to adjust the sensing, routing, and compression evenly across the grid such that the nodes wither out at the same rate, ensuring connectivity as far as possible. Their proposals are rudimentary and lack performance evaluation through numerical results. Figure 1 shows some of the example sensor grids with neighbor degrees as four, six, and eight, respectively.

Figure 1

Some examples of grid topologies.

In gateway deployment strategies, Hu et al. [17] and Li and Cao [18] propose Integer Linear Programming (ILP) based heuristics to deploy sensor networks as nonregular topologies that include resource-rich devices (called microservers) and resource-impoverished devices in capacitated networks. The heterogeneity has been exploited to attain longevity, yet cost effectiveness is ensured by insisting on reducing the number of microsensors. Likewise, [12, 19] present the same problem formulation to form a sensor grid with a limited number of class A nodes (cluster head or nodes with more transmission power) to ensure sufficiency (in terms of coverage and connectivity) for a given number of class B nodes. While the former presents a deployment heuristic that later figures out deterministic worst-case bounds. However, in practical deployment scenarios, though sensor nodes might be deployed in regular topologies within the region of interest (ROI), the deployment of sinks in ROI is impractical. It is due to the fact that the data processing units with command and control centers are usually farther away from the ROI and that the sinks are too costly to be deployed at such unsafe and unmanned areas. In [20] single sink placement strategies are suggested for single and multihop networks. Separate schemes are proposed for life prolonging and least energy consumption requirements. The idea is to place sink at the center for least energy consumption and also to place sink in highly dense area for prolonging life of network. These solutions are very trivial. Ant routing mechanism is used but it does not provide collision avoidance. Moreover, the proposed schemes are applicable for single sink networks.

This research effort simultaneously embodies analysis of lifetime modeling of sensor grids, proposes practical deployment strategies for their longevity, and provides scheduling framework for their effective operations and usage.

3. Network Model

As given in Figure 2, consider a reference topological model with a total of $n\times k$ sensor nodes that are distributed on a planar surface. Each node has an index as $(\mathrm{1,1}),\dots ,(i,j),\dots ,(n,k)$ that serves as a sensor node ID, making them aware of their relative location [3]. The following assumptions are made in order to realize a routing operation in such a sensor grid:

• (a)

Every node in the sensor grid senses an event and sends it towards the gateway. Intermediate nodes relay it downstream towards the gateway. The last node in the relaying activity is the collector that finally collects all of the sensed and relayed information before relaying to the gateway.

(b)

Whenever a sensing node transmits data, it is overheard by all its neighboring nodes that are one hop away according to disk model. Here the range of a successful transmission (the hop distance) may be restricted to a transmission range of either d or $1.41\times d$ as shown in Figure 2. In the former case if the transmission power is T, it is $2T$ for the latter case.

(c)

Either of the two relay models may be obtained by (b): in the first model, a node $(i,j)$ can only receive data from its upstream neighbors if their node IDs increment by one $[(i+1),j]$ and $[i,(j+1)]$ , but not simultaneously $[(i+1),(j+1)]$ . This results in paths that comprise links only to the laterally adjacent neighbors that is from right-to-left $(\to )$ if gateway is placed at left corner or left to right $\left(\leftarrow \right)$ if sink is placed at right corner or (and) up-to-down $(\downarrow )$ . It is called the staircase walk [21]. In the second model, we include diagonally adjacent neighbors $[(i+1),(j+1)]$ in the neighbor set for path forming as well giving diagonal links $(\swarrow )$ . It is called the Delannoy number walk.

(d)

In Delannoy number walk there are nodes at the left and bottom edges of a sensor grid that do not have diagonal neighbors. Such nodes do not need to transmit at $2T$ . Instead these nodes can transmit at T. This edge effect gives rise to two variants of Delannoy number walk, namely, fixed and variable transmission power Delannoy number walk.

(e)

A sensing node relays data to a neighboring node for onwards delivery to the collector node, only if the neighbor is closer to the collector as compared to the sending node; that is, it is a downstream neighbor.

(f)

The grid nodes and network may be vulnerable to failures and transmission losses. These transmission losses are represented as the probability of error, $P_e$ . In case, sensed data is not sent to the gateway, a notification mechanism (whether implicit or explicit is beyond the scope of our discussion) lets the sensing node retransmit. Thus we may say that the total transmissions in the network are governed by an additional factor due to retransmissions.

(g)

The energy cost for overhearing neighbor's transmissions is kept negligible by assuming cut-through processing [22].

(h)

The sensing process is a random memory less process that takes place whenever an event occurs. We have assumed the occurrence of an event to be Poisson distributed with mean ${\lambda }_{ij}$ .

(i)

Sensing and relaying activities where sensing includes detection of an event and sending it while relaying consists of both reception and forwarding of an event are assumed to take place after an event occurs; that is, energy consumption of node $(i,j)$ for sensing and relaying is independent of the past sensing and relaying activities. Owing to mathematical treatment, an intricate equivalence relationship exists between Poisson distribution as an arrival process (with mean λ) and exponential distribution (with mean $1/\lambda$ ) for interarrival times [7]. We, therefore, assume that energy consumptions due to the sensing and relaying activities are considered to be exponentially distributed with mean $1/{\beta }_{ij}$ and $1/{\gamma }_{ij}$ , respectively.

(j)

$h_{ij}$ is the initial energy of the sensor node $(i,j)$ battery at the starting reference time $t_0$ , distributed exponentially for all the nodes with mean $1/{\eta }_{ij}$ .

(k)

Interference model: in this paper, we have assumed a disc model as a path loss model in free space. Nonetheless, collocated nodes experience co- and cross channel interference which is not reflected in our model. Incorporating this expression in the network availability expression is more natural and practicable extension to our work. Phenomena such as local node contention and network congestion can be modeled on top of an interference model.

(l)

Packet delivery delay: for a typical sensor grid, a packet experiences the following delays when delivered from source node towards the collector:

$$\begin{array}{cc}& T_{\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}}=T_{\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{p}\mathrm{o}\mathrm{g}\mathrm{a}\mathrm{t}\mathrm{e}}+{\displaystyle \sum }_{e=\mathrm{1},f=\mathrm{1}}^{i,j}{T}_{{\mathrm{Q}\mathrm{u}\mathrm{e}\mathrm{u}}_{ef}}+{N\ast T}_{\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{e}\mathrm{v}},\end{array}$$

(1)

 

where (i) $T_{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{p}\mathrm{o}\mathrm{g}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}}$ = end-to-end propagation delay, (ii) ${\sum }_{e=1,f=1}^{i,j}{T}_{{\mathrm{Q}\mathrm{u}\mathrm{e}\mathrm{u}}_{ef}}$ = sum of the queuing delays from node $i,j$ to gateway, (iii) N = number of intermediate nodes between $i,j$ to gateway, and (iv) $T_{\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{e}\mathrm{v}}$ = packet reception and transmission delay per node.

Figure 2

A contemporary wireless sensor grid.

In our analysis of network availability, we assume all the delays to be alike for both staircase walk and Delannoy number walk traversal with certain level of approximation. For example, our assumption is plausible for $T_{\mathrm{Q}\mathrm{u}\mathrm{e}\mathrm{u}\mathrm{e}}$ because we have not considered an interference model. Similarly, for sensor grids with spatial coverage up to 500 m², $T_{\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{p}\mathrm{a}\mathrm{g}\mathrm{a}\mathrm{t}\mathrm{e}}$ does not vary significantly. Lastly, $T_{\mathrm{T}\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{s}\mathrm{c}\mathrm{e}\mathrm{i}\mathrm{v}\mathrm{e}}$ would not change considerably for the two schemes due to relatively small packet sizes. For example, in IEEE802.15.4-standard based sensor networks, a packet size of 128 bytes can have a transmission delay of 4 ms on 20 kbps links per hop [23].

The energy efficiency-versus-delay remains a conundrum from the view point of the network availability. At the first sight it may seem that allowing packets to stay in the network for lesser time periods (shorter end-to-end delays) results into network-wide energy conservation. However, a second look at this approach might signify the strain experienced by sensor nodes that render least delay paths and eventually leads towards making them dead and letting network availability void. In [24], the authors have considered energy-delay tradeoff as a cross-layer design problem. They conclude that at times elongated routing paths may be optimal to deliver certain bits with delay constraints between transceivers when rate adaptation is permissible. At all the other times, shorter routing paths may yield smaller delays and smaller energy consumptions.

4. Numerical Modeling of Energy Consumption for Single Gateway Sensor Grid (SGSG)

We denote $z_{ij}$ as the total energy consumed by sensor node $(i,j)$ in sensing, relaying, and idle mode. The total energy consumption by a sensor node includes (i) A constraint drain of battery to keep transceivers and processing hardware energized while there is no occurrence of events. We call it the energy consumption in the withering state, denoted by $w_{ij}$ for a sensor node $ij$ , and (ii) the energy consumption in the wake of an event. Therefore, $z_{ij}=x_{ij}+w_{ij}t$ . Let $x_{ij}$ denote the energy consumption when an event occurs. It has two parts: (i) energy consumption when a node senses an event and (ii) energy consumption to relay an event towards the gateway by a node $(i,j)$ . The joint probability density function (pdf) of energy consumption of all nodes in the grid may then be defined as a differential difference equation, discussed at length in [25] and also in [13]. Keeping in view the network model discussed in Section 3, let $x_i$ be the energy dissipated in sensing and relaying by node I; then $X=\left(x_{\mathrm{11}},x_{\mathrm{12}},\dots ,x_{ij},\dots ,x_{\left(n\right)(k-\mathrm{1})},x_{nk}\right)$ will be the joint probability of energy dissipation in sensing and relaying of all nodes in the network. Further to this, it is worth taking into account that we have the following:

• (1)

Since ${\lambda }_{ij}$ is the birth rate of Poisson arrivals at node $ij$ , it shows that the probability of sensing data at the node $ij$ is given as

$$\begin{array}{cc}& P_{ij}={\lambda }_{ij}\Delta t.\end{array}$$

(2)

(2)

Energy consumptions due to sensing and relaying activities are considered to be exponentially distributed with mean $1/{\beta }_{ij}$ and $1/{\gamma }_{ij}$ , respectively. However we multiply ${\gamma }_{ij}$ with ( $1+P_e$ ), where the factor $P_e$ includes the notion of additional energy consumption during relaying and retransmission in case of error.

(3)

${\beta }_{ij}\exp \left[{-\beta }_{ij}\left(x_{ij}-y_{ij}\right)\right]$ is the probability density function of energy consumption during sensing by node $ij$ .

(4)

When sensor node $ij$ senses some data its energy consumption is $x_{ij}-y_{ij}$ , and since this data needs to be relayed to a gateway, a path of relaying nodes is established in which sensor nodes 11 through $(i-1)(j-1)$ consume energy to relay the data sensed by node $ij$ to a gateway.

(5)

${\gamma }_{lm}\left(1+P_e\right)\mathrm{e}\mathrm{x}\mathrm{p}\left[{\gamma }_{lm}\left(1+P_e\right)\left(x_{lm}-y_{lm}\right)\right]$ is the probability density function of energy consumption for relaying sensed data by downstream nodes lm. Energy consumption due to relaying is $\left(x_{lm}-y_{lm}\right)\mathrm{\hspace{0.17em}\hspace{0.17em}}$ random variable with mean $\mathrm{1}/{\gamma }_{ij}\left(\mathrm{1}+P_e\right)$ and total energy consumption in relaying is sum of all values of lm, where lm ranges over all the possible indices chosen by the routing scheme.

(6)

Now, we combine all the factors discussed in $(1)$ through $(5)$ and modify Laplace Stieltjes transform joint energy consumption as given in [26] for one-dimensional case to obtain expression for two-dimensional network structure can be given as

$$\begin{array}{cc}& Z_t\left(s\right)=\mathrm{e}\mathrm{x}\mathrm{p}\left[\left(-{\displaystyle \sum }_{i=\mathrm{1}}^n\hspace{0.17em}{\displaystyle \sum }_{j=\mathrm{1}}^k{\lambda }_{ij}-{\displaystyle \sum }_{i=\mathrm{1}}^n\hspace{0.17em}{\displaystyle \sum }_{j=\mathrm{1}}^k{w}_{ij}+{{\displaystyle \sum }}_{i=\mathrm{1}}^n{{\displaystyle \sum }}_{j=\mathrm{1}}^k\left(\frac{{\beta }_{ij}}{s_{ij}+{\beta }_{ij}}\right){\displaystyle \prod }_{\forall l,m}\frac{{\gamma }_{lm}\left(\mathrm{1}+P_e\right)}{s_{lm}+{\gamma }_{lm}\left(\mathrm{1}+P_e\right)}\right)t\right],\end{array}$$

(3)

$$\begin{array}{cc}& z_{ij}=x_{ij}+w_{ij}t,\end{array}$$

(4)

 

where   $z_{ij}$ is the energy consumption of sensor node $ij$ and $w_{ij}$ is the withering state energy. This energy consumption keeps on increasing under the assumption of unlimited battery life and as given by the relation.

The network availability of a linear-only sensor network, $A_t$ , is defined in [27] as the probability that how long a single chain of sensor nodes can remain usable under a certain set of fixed conditions and variable factors. When a network is fully available (say at the initialization time), $A_t$ is unity. It decreases as a function of how the energy resources are drained. We now calculate the expression for $A_t$ . To this end, we recall that energy in the battery of a sensor node is exponentially distributed with mean value $\mathrm{1}/{\eta }_{ij}$ , so

$$\begin{array}{cc}& A_t={{\displaystyle \int }}_{h_{\mathrm{11}}}^{\infty }\cdots {{\displaystyle \int }}_{h_{nk}}^{\infty }{{\displaystyle \int }}_{z_{\mathrm{11}}}^{h_{\mathrm{11}}}\cdots {{\displaystyle \int }}_{z_{nk=\mathrm{0}}}^{h_{nk}}{\displaystyle \prod }_{\begin{array}{c}\mathrm{1}\le j\le k\\ \mathrm{1}\le i\le n\end{array}}^{}{\eta }_{ij}{e}^{{-\eta }_{ij}{h}_{ij}}{p}_{t\left(z_{\forall ij}\right)}{dz}_{\mathrm{11}}\cdots {dz}_{nk}{dh}_{\mathrm{11}}\cdots {dh}_{nk}.\end{array}$$

(5)

Using (3), the above expression can be written as

$$\begin{array}{cc}& A_t=Z_t\left({\eta }_{\mathrm{11}},\dots ,{\eta }_{ij},\dots ,{\eta }_{nk}\right)\end{array}$$

(6)

which amounts to replace all $\mathrm{\hspace{0.17em}\hspace{0.17em}}{s}_{ij}\mathrm{\hspace{0.17em}\hspace{0.17em}}$ with $\mathrm{\hspace{0.17em}\hspace{0.17em}}{\eta }_{ij}\mathrm{\hspace{0.17em}\hspace{0.17em}}$ in (3), yielding

$$\begin{array}{cc}& A_t=\mathrm{e}\mathrm{x}\mathrm{p}\left[\left(-{\displaystyle \sum }_{i=\mathrm{1}}^n\hspace{0.17em}{\displaystyle \sum }_{j=\mathrm{1}}^k{\lambda }_{ij}-{\displaystyle \sum }_{i=\mathrm{1}}^n\hspace{0.17em}{\displaystyle \sum }_{j=\mathrm{1}}^k{\eta }_{ij}{w}_{ij}+c\right)t\right],\end{array}$$

(7)

where

$$\begin{array}{cc}& C={\displaystyle \sum }_{i=\mathrm{1}}^n\hspace{0.17em}{\displaystyle \sum }_{j=\mathrm{1}}^k{\lambda }_{ij}\left(\frac{{\beta }_{ij}}{{\eta }_{ij}+{\beta }_{ij}}\right)\left(\frac{{\gamma }_{lm}\left(\mathrm{1}+P_e\right)}{{\eta }_{lm}+{\gamma }_{lm}\left(\mathrm{1}+P_e\right)}\right).\end{array}$$

(8)

Our argument for the steadiness of the paper is that (7) is the network availability of a two-dimensional grid predominantly as a relaying problem. Just like its linear-only counterpart, $A_t$ is indeed a function of various factors including network size (n rows and k columns), battery size $({\eta }_{ij})$ , withering state energy consumption $(w_{ij})$ , arrival rate of events $({\lambda }_{ij})$ , energy consumption to sense such events $({\beta }_{ij})$ , and the error probability $(P_e)$ . However, the energy consumption $({\gamma }_{lm})$ to relay such data towards the gateway is the most significant factor in determining the network availability. Relaying is comprised of reception and transmission activities performed by the nodes with subscripts where l and m are referring to row and column numbers of all the nodes with the lexicographical relationship, $\{l,m\}<\{i,j\}$ . $1/{\gamma }_{lm}$ that is the function of lattice traversal schemes which are adopted according to different communication models discussed in the next section.

5. Communications Models: A Combinatorial Theoretic Perspective

In this section, we define various lattice traversal models that affect ${\gamma }_{lm}$ so that we may evaluate numerical expression of $A_t$ for a variety of parameters. Following are some considerations that must be taken for formulating such lattice traversal models.

• (a)

As mentioned in statement (a) of Section 3, communication in sensor grids is gateway-oriented.

(b)

Communication may be either unicast or multicast. It means that each sensor node may relay data from its one-hop upstream neighbor or all the one-hop upstream neighbors.

(c)

The traffic load at such a node is dependent upon the relay model as specified in statement (b) and (c) of Section 3.

(d)

Usually depending upon the hardware and deployment, the ratio of transmission and reception energy consumptions may vary from 1 : 1 to a more diverging ratio say 2 : 1. Therefore, relay load per node may be considered as either one or unity energy consumption per node or a more fine grained description of relay load may be considered, such as taking a linear summation of reception energy consumption and transmission energy consumption. In the former case, we measure relay load in terms of hop count to transmit traffic between a sensor node and sink. In the latter case, we consider reception and transmission energy consumptions as two distinct activities while transmitting traffic between a sensor node and sink.

Therefore, communication models for a sensor grid are defined as shown in Table 1 which shall be used for analysis in the rest of the paper.

Table 1

Communication models for sensor grid.

⁢ $\mathrm{T}\mathrm{x}=\mathrm{R}\mathrm{x}$		⁢ $\mathrm{T}\mathrm{x}\ne \mathrm{R}\mathrm{x}$
Unicast	(i) Staircase	Unicast	(i) Staircase
	(ii) Delannoy number walk		(ii) Delannoy number walk
Broadcast	(i) Staircase	Broadcast	(i) Staircase
	(ii) Delannoy number walk		(ii) Delannoy number walk

Depending upon the communication models for sensor grid, relay energy varies as number of nodes that are actually traversed to relay transmission towards the gateway changes. By modifying network availability formula according to the communication models for sensor grid, we find following results.

6. Numerical Analysis

In the following, we compare availability expression for different communication models against each other and against node and network parameters. Unless otherwise stated, the abscissa is time (approx. 4 months [9]). Figures 3(a) and 3(b) compare the network availabilities for two lattice path traversal schemes, namely, staircase walk and Delannoy number walk under unequal $(\mathrm{R}\mathrm{x}\ne \mathrm{T}\mathrm{x})$ and equal $(\mathrm{R}\mathrm{x}=\mathrm{T}\mathrm{x})$ energy consumptions for transmission and reception, respectively. In both of these cases, staircase walk consumes lesser energy as compared to Delannoy number walk for smaller topologies (such as 25).

Figure 3

Network availability under two energy consumption models.

However, when the topology size increases, the network availabilities in Delannoy number walk equalize its counterpart, mainly due to the lesser hops. It is interesting to note in Figures 3(a) and 3(b) that an increase in topology size from 25 to 100 affects the network availability more than the equal energy consumption. It is due to the fact that more transmission power reduces network availability considerably. Due to efficiency of staircase walk, we analyze the network availability for staircase walk in Figures 4, 5(a), and 5(b).

Figure 4

Fixed transmission power.

Figure 5

(a) Effect of broadcast versus unicast. (b) Effect of retransmission.

Figure 4 shows the network availability if the edge effect gives rise to fixed and variable transmission powers. While all the nodes transmit at the same transmission power in the former case, a total of $(n+k-1)$ edge nodes halve their transmission powers, giving a visible gain in network availability. Although the detrimental effect of broadcast storms on network lifetime is unarguable. Intuitively, it can be visualized in terms of network availability in Figure 5(a) for a topology size of 25. A ready effect of channel impairments is the likelihood of an unsuccessful transmission or probability of error $(P_e)$ . The effect on network under $P_e$   range of  10⁻⁵~10⁻¹ is shown in Figure 5(b). The severity of effect is more obvious for the large topology because the retransmissions increase the relay load considerably for the longer of the sensor-to-gateway chains.

In this subsection, we consider the effects of other node and network parameters that contribute to the network availability. The first parameter that affects it is dependent upon the sensing radius of each node as shown in Figure 6(a). We assume it to be the same as the transmission range to provide maximum coverage along with connectivity [28].

Figure 6

(a) Effect of sensing energy. (b) Effect of data rate. (c) Effect of battery size.

The effect of data rate, shown in Figure 6(b), is more pronounced in larger topologies due to heavier relaying load for the longer of the sensor-to-gateway chains. As shown in Figure 6(c), the effect of all the factors on network availability whether directly or indirectly may be strongly neutralized when the battery size and its cost are considered no more a constraint.

Considering the 8~10% growth per year in battery energy within limited form factors computing power, the idea of battery energy following Moore's law is farfetched idea, if not impossible [29, 30]. Therefore any strategy for extending network availability has to reduce the network traffic as much as possible.

Summarizing the factors that were analyzed in Figure 6(a) through Figure 6(c), it is significantly obvious that it is the communication (in different variants) that undermines network availability the most. Some of these parameters are hardware specific while others are specific to deployment scenarios. In either case, relaying is the most significant activity and any performance optimizing measure must address it in particular. In the next section, we suggest a mechanism that deploys multiple gateways to optimize communication at an added capital cost. The “added” capital cost is considered viable by considering a cut down in recurring battery replacement cost for sensor nodes, a gain in unattended and unmanned sensor grid lifetime.

7. A Heuristic for Multiple Gateway Deployment: A Special Case of P-Median Problem

In this section, first we present the justification of deploying multiple gateways around the ROI. Then we present a heuristic for their deployment. Finally, we present a numerical result that shows the gain in network availability for a 4 × 4 sensor grid. The plausibility of deploying multiple gateways across the ROI is derived from the following.

Fact 1.

Homogeneous sensor nodes once deployed in an unattended sensor grid are difficult or sometimes impossible to reenergize. Therefore, additional nodes with unconstrained batteries may be deployed only at the outskirts of sensor grids.

Fact 2.

The cost of the gateway depends upon the design, complexity, and operation of target user applications. These tasks may vary between tasks as simple as communication between dissimilar networks to user specified data operations such as filtering, aggregation, and beam forming. For the heuristic that we propose, a more restricted role of gateways is assumed.

Lemma 1.

The cost disparity between gateways and groups of sensors becomes asymptotic as the sensor grid size increases.

Fact 3.

In a single gateway topology, transmission paths for all the sensor nodes are all wireless up to the penultimate hop. In a multiple gateway topology, there exist wireless-cum-wired paths for every sensor node, which reduce the drainage of battery per unit of energy per bit (or equivalently per packet). These facts motivate us in various ways. For example, Fact 1 motivates us to deploy gateways to reduce relay load. Fact 2 ensures the cost viability of these gateways. Lastly, Fact 3 motivates us to exploit out of sensor grid perimeter rout-ability.

7.1. A Heuristic for Multiple Gateway Deployment

The deployment of multiple gateways around the ROI is aimed at achieving maximum network availability. This activity involves each of the $(n,k)$ sensor nodes to locate and choose the nearest of $2\times (n+k-2)$ gateways deployed at the outskirts to reduce relaying cost. It also involves the relaxation of assumption (c) in Section 3 that the routing is done on the basis of node IDs. Instead, henceforth, the routing is done to the nearest gateway. Such kind of problem formulation is termed as NP-complete [29]. This problem is specifically a P-median problem [31] because (a) the formation of gateways is around the ROI, not within it, and (b) gateways must be aligned in front of either a row or a column to follow staircase walk, instead of Delannoy number walk, a Vertex Center problem. Reference [32] showed that at least one optimal solution exists for such P-median problems. The linear programming for deployment heuristic is given as follows:

$$\begin{array}{cc}& \mathrm{M}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{z}\mathrm{e}\hspace{1em}{\alpha }_{\mathrm{1}}\times C_{\mathrm{G}\mathrm{W}}+{\alpha }_{\mathrm{2}}\times Y_{\left(ij\right)\left(i^{’}{j}^{’}\right)}\end{array}$$

(9a)

$$\begin{array}{cc}& \mathrm{S}\mathrm{u}\mathrm{b}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\hspace{0.17em}\hspace{0.17em}\mathrm{t}\mathrm{o}\hspace{1em}{\displaystyle \sum }_{i^{’}{j}^{’}}{Y}_{\left(ij\right)\left(i’j’\right)}=1\hspace{1em}\forall i^{\prime }{j}^{\prime }\end{array}$$

(9b)

$$\begin{array}{cc}& \hspace{1em}{\displaystyle \sum }_{i^{’}{j}^{’}}{X}_{\left(i^{\prime }{j}^{\prime }\right)}=\mathrm{g}\mathrm{w}\end{array}$$

(9c)

$$\begin{array}{cc}& \hspace{1em}{Y}_{\left(ij\right)\left(i^{\prime }{j}^{\prime }\right)}-X_{\left(i’j’\right)}\le 0\hspace{1em}\forall \left(ij\right)\left(i^{\prime }{j}^{\prime }\right)\end{array}$$

(9d)

$$\begin{array}{cc}& \hspace{1em}{X}_{\left(i^{\prime }{j}^{\prime }\right)}=\mathrm{0,1}\hspace{1em}\forall \left(ij\right)\end{array}$$

(9e)

$$\begin{array}{cc}& \hspace{1em}{Y}_{\left(ij\right)\left(i^{\prime }{j}^{\prime }\right)}=\mathrm{0,1}\hspace{1em}\forall \left(ij\right)\end{array}$$

(9f)

$$\begin{array}{cc}& \hspace{1em}{\alpha }_1+{\alpha }_2=1\end{array}$$

(9g)

such that the relaying hops across the network are minimized, yet cost of the gateways is reduced whereas the decision variables for Figure 9 are defined as follows:

•  

  $X_{ij}=\mathrm{1}$ ,  if we locate the gateway at candidate site $i^{\prime }{j}^{\prime }$ ; $X_{ij}=\mathrm{0}$ ,  if not.

•  

  $Y_{\left(ij\right)\left(i^{\prime }{j}^{\prime }\right)}=\mathrm{1}$ ,  if demand at node $ij$ is served by a gateway at site $i^{\prime }{j}^{\prime }$ ; $Y_{\left(ij\right)\left(i^{\prime }{j}^{\prime }\right)}=\mathrm{0}$ ,  if not.

•  

  N, k  are sensor grid size in terms of rows and columns, respectively.

•  

  $(n+k-\mathrm{2})-\mathrm{g}\mathrm{w}\ge \mathrm{1}$ is number  of  gateways.

•  

  $C_{\mathrm{G}\mathrm{W}}$ is cost of gateway.

•  

  $\left(\begin{array}{c}\mathrm{2}\times \left(n+k-\mathrm{2}\right)\\ \mathrm{g}\mathrm{w}\end{array}\right)$   are possible arrangements of gw gateways around the $\mathrm{2}\times (n+k-\mathrm{2})$ ROI positions.

The objective function in (9a) consists of two parts. The first part minimizes the relay hops (implicitly maximizing the total network availability of sensor grids). The second part minimizes the cost of the gateways. Overall, it optimizes the coverage of gateways to as many nodes as possible and connectivity of sensor nodes through as minimum hops as possible. The constraint (9b) ensures that at most one gateway is occupied by each sensor node. The constraint (9c) ensures that exactly $\mathrm{g}\mathrm{w}$ out of $2\times (n+k-2)$ number of gateways are to be located. The constraint (9d) links each sensor node to the gateways. It states that traffic at a node $ij$ can only be routed to a gateway at location $i^{\prime }{j}^{\prime }$ if the gateway is located at $i^{\prime }{j}^{\prime }$ . Integrality conditions are defined in the constraint (9f)-(9g).

The number of gateways that can be deployed around the grid is a combinatorial problem. If a total of gateways are to be deployed among the available $2(n+k-2)$ locations then the number of distinct choices is given by the binomial coefficient:

$$\begin{array}{cc}& \left(\begin{array}{c}\mathrm{2}\left(n+k-\mathrm{2}\right)\\ i^{\prime }{j}^{\prime }\end{array}\right).\end{array}$$

(10)

Since the total number of gateways may vary from 1 to $2(n+k-2)$ , we take a sum over the index:

$$\begin{array}{cc}& {\displaystyle \sum }_{i^{\prime }{j}^{\prime }=\mathrm{1}}^{\mathrm{2}\left(n+k-\mathrm{2}\right)}\left(\begin{array}{c}\mathrm{2}\left(n+k-\mathrm{2}\right)\\ i^{\prime }{j}^{\prime }\end{array}\right)={\mathrm{2}}^{\mathrm{2}\left(n+k-\mathrm{2}\right)}-\mathrm{1}\simeq {\mathrm{2}}^N-\mathrm{1}=\mathrm{0}\left({\mathrm{2}}^N\right).\end{array}$$

(11)

It becomes quite obvious now that the optimal deployment of gateways takes complexity of the form $O(2^n)$ . Since there are an exponential number of paths, it may therefore be impractical to enumerate all the possible paths. Since most of the variables are nonbasic, in the following subsection, we suggest a delayed column generation problem that is aimed at reducing computational complexity.

7.2. Column Generation Problem

Let U be the union of all possible paths for all the number of gateways. We observe that such all-paths union contains optimal, suboptimal, and nonoptimal paths. Since we are only interested in optimal paths, we assume that a subset $U^{\prime }$ of U exists that enlists only the minimum-hop paths. Replacing U by $U^{\prime }$ yields the restricted linear programming whose solutions contain the shortest paths. Then, we may write the optimality condition as a delayed column generation problem as follows:

$$\begin{array}{cc}& \left|i^{\prime }-i\right|+\left|j^{\prime }-j\right|-{\gamma }_{lm}\ge \mathrm{0}:\end{array}$$

(11h)

No of hops for node ij to reach X_i′j′, gateway.

Problem (11h) finds the shortest path routing as the total number of hops needed to connect a node $ij$ to the gateway $i^{\prime }{j}^{\prime }$ the Euclidean distance between the two.

7.3. G Wave

G Wave is a node scheduler for nearest gateway connectivity, collision avoidance, and fairness. In this subsection, we first present numerous multisource multidestination routing schemes that schedule communication within the network and towards the gateway in order to prevent collisions and ensure fairness and optimality. We then identify the most appropriate scheme for wireless sensor grids.

Zhang and Shi have discussed various energy efficient protocols in [25]; however they do not consider the multiple sink scenario. Their routing protocols are tightly coupled with their definition of network availability, time till the first node breaks down. Hence it does not exploit the multiple gateway model as considered in this research effort. A routing scheme has been proposed in [33] which maps the multisink multisource routing problem to the well-established multicommodity network design problem. This scheme focuses on minimizing the number of paths and links being used. It does so by maximizing the extent of overlap between new paths to be created and the paths already being used by the network. Using the same path that is already being used by the network, the extra overhead is avoided (which would be necessary if routing is to be done on a new path). Using the scheme per se into the wireless sensor grid might save collisions in path discovery and data transmissions. However, it would result into reduced network longevity, because aggregating neighboring traffic along a singular path would wear out the batteries too much and too quick. Utilizing the information about remaining battery life as part of the cost metric may provide a route scheduling solution that is well-suited for energy starved wireless sensor grids.

A novel routing framework called P Wave routing has been proposed in [34] which proposes and then establishes an isomorphism between a communication network and an electrical network, in order to handle multisource multisink routing in wireless sensor networks. Herein, Liu et al. consider the network as a graph $G=(N,E)$ , where N is the set of nodes and E is the set of symmetric edges. Between two neighbors, a resistance is attached whose value is a measure of cost along that edge. Each node is assigned with a potential which determines the direction of data flow such that data may only flow from a higher potential to a lower potential.

A zero potential is assigned to a gateway node so that it behaves as a sink node under normal conditions and that all the data within the network eventually flows towards the gateway. When a gateway wishes to broadcast or anycast,  the potential of the gateway is raised to an arbitrarily agreed upon maximum value and it starts to behave like a source node. Interestingly, raising the potential of a gateway to a maximum value would automatically cause the incoming traffic to divert to a different gateway, naturally offering a mechanism to avoid collisions. P Wave being a good candidate for multiple source-multiple sink sensor grids is constrained in fulfilling the following requirements. (R1.1) the gateway deployment heuristic (Section 7.1) necessitates that each sensor node must relay the data in the least number of hops. P Wave uses a localized rule to route intermediate data flows between the neighboring nodes, across the whole topology. Consequently, it does not ensure that each sensor node forward data towards the nearest gateway. Figure 8 shows two nodes transmitting at the same time. Due to the potential raise by node 1, node 2 diverts its transmissions towards a farther gateway.

(R1.2) Sensor nodes wishing to transmit must have simultaneous paths to their respective gateways if their destinations are disjoint and (R2) sensor nodes wishing to transmit over overlapping paths must avoid collisions. Since P Wave uses equilibrium potential fields in routing using the localized rule to ensure loop freedom only, collisions have not been addressed, for both disjoint and overlapping paths.

Consider Figure 9, where hidden terminal problem occurs due to simultaneous potential raise from 1, 3, and 4 towards 2, preventing nodes 1, 3, and 4 from successful transmission.

In the remainder of this section, we present the operation of G Wave while laying a specific emphasis on addressing R1.1, R1.2, and R2.

Nearest gateway connectivity: in order to address R1.1 and R1.2, we propose the idea of visualizing wireless sensor grid that uses multiple gateways as a number of subnetworks. Each of such subnetworks would have a gateway at its root handling all the traffic of the child nodes. This would turn our network into disjoint graphs, where each subnetwork along with its gateway and child nodes maintains its singularity. Each gateway now advertises its ID in addition to the zero potential to attract traffic from respective sensor nodes. This mechanism not only satisfies R1.1 but also provides traffic isolation among the disjoint subnetworks (R1.2). Now, G Wave algorithm executes separately on these isolated subnetworks with each transmission tagged with its subnetwork number.

In Figure 9, the dotted line shows the isolation achieved through the incorporation of gateway IDs. To initially tag the nodes with their closest gateways, the hop count field is set as a threshold, beyond which the node cannot transmit to a certain gateway and hence is required to join a different gateway. Again, if we assume a uniform density of our sensor grids, the hop count metric would naturally translate into the physical distance between a gateway (root node) and its child nodes. Please note that now the transmissions from node 1 and node 2 both bound to Gateway 1 collide in the wake of simultaneous transmissions. In the following, we present collision avoidance mechanism that also ensures fairness. Collision avoidance and fairness: the contention among competing nodes belonging to the same subnetwork can be resolved using timers. The design of timers follows the discipline as follows:

• (a)

The value of the timer at every node is dependent upon its location such that the node closest to the gateway has the longest Wait Time. Conversely, as the hop count from the gateway increases, the Wait Time decreases. For instance, node 2 (internal node) would have a shorter Wait Time as compared to node 1 (collector node). This results into the network becoming capable of aggregating traffic towards the sink.

(b)

For those nodes with the same hop count, Distributed Inter Frame Spacing (DIFS) [20] parameter is preassigned for left, right, and bottom/up neighbors such that their transmissions are isolated in distinct epochs, avoiding collisions (as shown in Figure 10).

7.4. Performance of the Heuristic

The results for the minimized objective function from Figure 7 are obtained for a 4 × 4 sensor grid by considering the LP as shown in Table 1.

Figure 7

Suboptimal path selection.

Figure 8

Hidden terminal problem.

Figure 9

Inclusion of gateway IDs to isolate traffic.

Figure 10

Satisfaction of R2 through the inclusion of timers.

Different values of ${\alpha }_1$ and ${\alpha }_{\mathrm{2}}$ refer to the weight-age (or equivalently penalty) that we introduce for deploying gateways and resulting hop count, respectively. The $\mathrm{m}\mathrm{i}\mathrm{n}\{\mathrm{O}\mathrm{b}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{v}\mathrm{e}\mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{f}\mathrm{u}\mathrm{n}\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{\hspace{0.17em}\hspace{0.17em}}(\mathrm{g}\mathrm{w},\mathrm{h}\mathrm{o}\mathrm{p}\mathrm{s}\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t})\}$ is shown in bold. For an extreme form of penalty such as $({\alpha }_{\mathrm{1}}=\mathrm{0.1},\hspace{0.17em}\hspace{0.17em}{\alpha }_{\mathrm{2}}=\mathrm{0.9})$ , the minimized objective function is obtained for 12 gateways because we underrate the cost of each gateway. Likewise, the choice $({\alpha }_{\mathrm{1}}=\mathrm{0.9},\hspace{0.17em}\hspace{0.17em}{\alpha }_{\mathrm{2}}=\mathrm{0.1})$ assigns a lot of significance to the cost of gateways, resulting in a minimized objective function for a single gateway. A careful choice of ${\alpha }_{\mathrm{1}}=\mathrm{0.7}$ , ${\alpha }_{\mathrm{2}}=\mathrm{0.3}$ shows that deploying 3 gateways gives the minimized objective function from both the viewpoint of gateway cost and minimum hops.

Figure 11(a) shows only some of the possible gateway deployment scenarios for a 4 × 4 grid. Figure 11(b) shows the difference in network availabilities under various gateway deployments. The difference is highlighted for two time epochs: first epoch is at the start of network lifetime and second epoch is when the network availabilities become asymptotic. The deployment of 3 gateways gives a consistent gain of 20% at the first observation epoch and 3% at the second epoch observation.

Figure 11

Multiple gateway deployments and their respective availabilities plotted as a difference.

8. Case Study

We present the network availability of a practical scenario to show how much is the performance gain that we actually get by deploying gateways according to the heuristic that we have presented. We consider the deployment of an optimal number of gateways around a 4 × 4 sensor grid that comprises sensor devices of a specific type (Table 3). These devices conform to IEEE802.15.4 standard [20]. The specifications used in obtaining the network availability are summarized along with plot in Table 2 and Figure 12.

Table 2

Minimized objective functions for a 4 × 4 sensor grid.

Number of GWs	Min. hops	Max. hops	Avg. hops	Minimized objective function
				${\alpha }_{\mathit{1}}=\mathit{0.1}$   $${\alpha }_{\mathit{2}}=\mathit{0.9}$$	${\alpha }_{\mathit{1}}=\mathit{0.2}$   $${\alpha }_{\mathit{2}}=\mathit{0.8}$$	${\alpha }_{\mathit{1}}=\mathit{0.3}$   $${\alpha }_{\mathit{2}}=\mathit{0.7}$$	${\alpha }_{\mathit{1}}=\mathit{0.4}$   $${\alpha }_{\mathit{2}}=\mathit{0.6}$$	${\alpha }_{\mathit{1}}=\mathit{0.5}$   $${\alpha }_{\mathit{2}}=\mathit{0.5}$$	${\alpha }_{\mathit{1}}=\mathit{0.6}$   $${\alpha }_{\mathit{2}}=\mathit{0.4}$$	${\alpha }_{\mathit{1}}=\mathit{0.7}$   $${\alpha }_{\mathit{2}}=\mathit{0.3}$$	${\alpha }_{\mathit{1}}=\mathit{0.8}$   $${\alpha }_{\mathit{2}}=\mathit{0.2}$$	${\alpha }_{\mathit{1}}=\mathit{0.9}$   $${\alpha }_{\mathit{2}}=\mathit{0.1}$$
1	1	12	4	0.908	0.817	0.725	0.633	0.602	0.450	0.358	0.267	0.175
2	1	4	2.75	0.635	0.583	0.531	0.479	0.240	0.375	0.323	0.271	0.219
3	1	3	2.125	0.503	0.475	0.447	0.419	0.184	0.363	0.334	0.306	0.278
4	1	3	2	0.483	0.467	0.450	0.433	0.183	0.400	0.383	0.367	0.350
6	1	3	1.75	0.444	0.450	0.456	0.463	0.181	0.475	0.481	0.488	0.494
8	1	2	1.5	0.404	0.433	0.463	0.492	0.138	0.550	0.579	0.608	0.638
12	1	2	1.25	0.381	0.450	0.519	0.588	0.140	0.725	0.794	0.863	0.931

Table 3

Sensor devices specifications.

Data rate		250 kbps
Packet size		128 bytes
Energy consumption	Idle	5 μ joules/s
	Sense	300 joules
	Transmit	187 joules
	Receiving	212 joules
Battery size	0.06 mAH

Figure 12

Network availability under optimal gateway deployment versus single gateway deployment along with parameter list.

According to Figure 12, the deployment of three gateways according to the heuristic (Section 7) around the sensor grid results in a performance gain due to reduction in the number of hops for transmissions from sensor nodes to the gateways. The average gain across all the time scale is 0.128; it means that approx. 13% of the resources (coverage and connectivity) are available additionally to the optimal deployment under all the times.

9. Conclusion

In this paper, we study and analyze the energy consumption pattern followed by single gateway sensor grids. Further to this, we analyze the network availability of sensor nodes deployed across a two-dimensional space. We conclude that the energy consumption in sensor network grids can be optimized through the deployment of multiple gateways. It is also concluded that the effective network availability of a two-dimensional sensor network is dependent on the number of sensor nodes, their topological distribution, the transmission model adopted, and the node parameters. We present a linear programming heuristic for multiple gateway deployment to optimize communication through optimized relaying activity across the sensor grid. Our work shows practical utility for the design and implementation of wireless sensor grids as cut-through energy paradigms.