Geographical model-derived grid-based directional routing for massively dense WSNs

This section considers the cost functions which are isotropic and only depends on position. Reference [24] discussed the relationship between the transmission energy as the cost and the node density ψ. Note that referring to [25], the energy consumption per unit of information is proportional to \({r}^{\alpha _{\textit {rf}}}\phantom {\dot {i}\!}\) in which r is the distance between the sender and receiver and the RF attenuation exponent α _rf is typically in the range of 2 to 5. Additionally, the average inter-distance between nodes is proportional to \(1/\sqrt {\psi }\), which leads to \(\mathcal {C}\propto 1/\psi ^{\alpha _{\textit {rf}}/2}\).

As pointed out in [26], while considering the capacity of wireless communications, the throughput of each node at (x,y) cannot be fully utilized and is only proportional to \(1/\sqrt {\psi (x,y)}\) [3]. Therefore, the optimum total throughput at (x,y) can only be proportional to \(\sqrt {\psi (x,y)}\); that is, \(\mathcal {C} \propto 1/\sqrt {\psi }\) corresponds to a network in which the objective is to maximize the throughput.

Several other possible forms of \(\mathcal {C}\) are also listed in [5]. For example, if the objective is to minimize the number of hops, \(\mathcal {C}\) may be taken to be proportional to 1/r, in which communication is constrained between the nearest neighbors. Thus, \(\mathcal {C} \propto \sqrt {\psi }\). In addition, the case that \(\mathcal {C}\) is a constant corresponds to a setting where routing is equally costly at all parts of the network. Thus, the objective is to minimize the length of routes. The relationships between \(\mathcal {C}\) and ψ for the above objectives are summarized in Table 2.

It is infeasible to directly find the minimum cost routing path under massively dense networks. One possible approach to reduce the problem scale is to divide the ROI into equally spaced grids which compose a grid point network, referring to Fig. 1. We then find the minimum cost path between each grid point and sink (e.g., using Dijkstra’s method) under the grid point network. The routing direction of a grid point will be the direction pointing to the next grid point on the minimum cost path under the grid point network. For the example of Fig. 1, the direction from to is the routing direction of . Here, we denote as the grid point located at the ith column and the jth row, and say a node belongs to if its closest grid point in the ROI is ; for example, all nodes in the dark gray region belong to . Therefore, a node belonging to may use the direction from to as guidance to determine the next forwarding node [10].

Note that the routing direction of derived by grid approximation Dijkstra’s method (GADM) always points to one of s four adjacent grid points. Such a restriction is the main reason that GADM cannot approximate continuous paths well (i.e., the minimum cost routing paths under massively dense networks), which thus yields less optimum routing paths.

We first present numerical results, illustrated in Figs. 5 and 6, to compare the effectiveness of GADM and FM. The settings of both scenarios, as summarized in Table 3, are similar except the number of sinks. Furthermore, the cost function \(\mathcal {C}\) considered is a constant; thus, the minimum cost path is the one with the shortest length.

If the information is currently routed to a node, denoted as v, belonging to , we use \(\widetilde {\mathbf {u_{f}}}_{{i},{j}}\) and the following mechanism adopted in [10] to determine the next forwarding node (i.e., the second stage of the grid-based directional routing algorithms).

Note that due to the characteristics of wireless communication [3], it is preferred to use multiple short-range transmissions for optimal power consumption and communication capacity. Therefore, we gradually increase the communication range R _c of v in searching for the next forwarding nodes to avoid long distance transmissions. The values of R _c and ΔR _c are also listed in Table 3.

Figure 5 a depicts the routing directions derived by FM. Figure 5 b, c illustrate the routing paths via the routing directions derived by GADM and FM. The route lengths listed in Table 4 show that FM may derive shorter routing paths than GADM. Note that GADM and FM may result in different routes to bypass the hole for the same source node, as illustrated in Fig. 5 c. Similar results may be found for the second scenario, referring to Fig. 6 and Table 4. In addition, GADM and FM may result in routing to different sinks for the same source node, as illustrated in Fig. 6 c.

The reason that FM outperforms GADM is that the minimum cost path derived under the grid point network may not approximate the actual minimum cost path well. In addition, the routing direction of a grid point always points to the neighbors of (that is, the four adjacent grid points of in our simulations). Though this problem may be alleviated by extending the neighbor set (for example, adding the diagonal grid points to the neighbor set), the direction restriction (the routing direction always points to one of the neighbors) cannot be removed. On the other hand, (5) used in Algorithm 1 approximates |∇T| well, and the routing direction (via using \(\widetilde {T}\)s and (7)) has no such direction restriction.

Figure 7 illustrates how node density may affect routing paths for the optimization objectives listed in Table 2 with α _rf =4. Twenty thousand nodes are randomly deployed according to ψ(x,y)∝(3.5×10⁻⁵ y ²+0.02). Note that routing directions are solved (i.e., the first stage of the grid-based directional routing algorithms) using only the macroscopic parameter, ψ, but not the detailed position of each node. Thus, FM derives the same routing directions under the same density distribution regardless of the node positions. The node positions are merely used to determine the next forwarding node (i.e., the second stage) from the routing directions using the approach described earlier in this section.

The results show that routing should utilize the nodes in the sparse area to minimize the number of hops and use the nodes in the dense area to increase the throughput and to avoid long distance transmissions for less energy consumption. Of course, routing should use the straight line to the sink for minimizing the route length.

We also conducted simulations to compare the routing cost of \(\widetilde {\mathbf {u_{f}}}_{{i},{j}}\) obtained from FM and GADM with the optimum routing cost determined by applying a shortest path algorithm to the connectivity graph of the WSN shown in Fig. 7, which basically is a microscopic routing approach. The results illustrated in Fig. 8 reveal that \(\widetilde {\mathbf {u_{f}}}_{{i},{j}}\) obtained from FM may lead to a reasonable routing cost; the average cost is 5 % more than the average optimum cost. On the other hand, \(\widetilde {\mathbf {u_{f}}}_{i,j}\) obtained from GADM may have a routing cost up to 28 % more than the optimum cost. In Fig. 8, the mean of the routing cost is the average cost of all nodes to the sink. The relative mean of FM (or GADM) is defined as the mean of the routing cost of FM (or GADM) divided by the mean of the optimum routing cost.

This section considers the case in which \(\mathcal {C}(x,y)= \lambda (x,y)^{2}\left |\mathbf {D}(x,y)\right |\); here, λ is the energy cost e, normalized to the initial energy E, for transmitting one unit of information, i.e., λ=e/E. As pointed out in [2], in the context of a massively dense network, routing paths can be considered as continuous lines, instead of sequences of discrete nodes, and D may be considered differentiable. Thus, the fact that information is conservative (i.e., at each location, the net amount of traffic is equal to the amount of information generated) can be formulated as [29]:

Thus, from Theorem 2, if (8) holds, the geodesic problem (2) with \(\mathcal {C}(x,y)=\lambda (x,y)^{2}\left |\mathbf {D}(x,y)\right |\) is equivalent to the optimization problem which finds the vector field D(x,y) to minimize:

Note that the variance of λ|D|, \(\int _{A}\left (\lambda (x,y)\left |\mathbf {D}(x,y)\right |-\overline {\lambda \left |\mathbf {D}\right |}\right)^{2}\mathrm {d}x\mathrm {d}y\), is positive; here, \(\overline {\lambda \left |\mathbf {D}\right |}\) is the average of λ(x,y)|D(x,y)|. Since: in which area(A) is the area of A; minimizing (9) not only minimizes the difference of each location’s λ|D| but also inherently reduces \(\overline {\lambda \left |\mathbf {D}\right |}\).

Since λ is the normalized communication energy cost per unit of information, λ(x,y)|D(x,y)| is the normalized total communication energy consumption. Thus, it is not difficult to reason that keeping λ|D| the same everywhere in A is equivalent to exhausting the energy of each location in A simultaneously. In other words, the objective of the geodesic problem (2) with \( \mathcal {C}(x,y)=\lambda (x,y)^{2}\left |\mathbf {D}(x,y)\right |\) is to achieve global load-balancing (by minimizing the difference of each location’s λ|D|, i.e., the variance) and reduce the total communication energy consumption (by reducing \(\overline {\lambda \left |\mathbf {D}\right |}\)).

As mentioned in [30], the necessary condition for deriving the minimum value of (9) is the existence of a scalar function Φ called potential that satisfies:

in which J=1/λ ². In addition, there is no information flow from the outside of A; that is, there is no traffic along the inward pointing normal direction at the boundary of A, denoted as ∂A, which leads to the following boundary condition:

in which \(\hat {\mathbf {n}}\) is the unit inward pointing normal vector to ∂A.

Therefore, the minimum cost routing problem with the cost \( \mathcal {C} (x,y)=\lambda (x,y)^{2}\left |\mathbf {D}(x,y)\right |\) can be transformed into a set of partial differential equations that we call load-balancing routing equations, (8), (10), and (11). We may combine these equations into the following single equation called the weak formulation of the load-balancing routing equations:

Note that there is no differential term of D in (12), and the a priori differentiability requirement of D is weakened. Thus, the weak formulation allows us to consider irregular problems in which true solutions cannot be continuously differentiable [9], e.g., the problems in which ψ or ρ are jump functions in A. For the sake of brevity, the derivation of (12) is given in Appendix 2.

The relationship between J and the node density distribution ψ may be further established if the transmission energy consumption model is given. For example, we may adopt the energy consumption model in [25], in which the energy consumption per unit of information (denoted as e) is proportional to \(r^{\alpha _{\textit {rf}}}\phantom {\dot {i}\!}\). Here, r is the sender-to-receiver distance and the RF attenuation exponent α _rf is typically in the range of 2 to 5. Since the average inter-distance between nodes is proportional to \(1/\sqrt {\psi }\), \(r \propto 1/\sqrt {\psi }\) and hence \( e\propto {\psi}^{-{\alpha}_{rf}/2} \). In addition, suppose that the nodes have an equal amount of initial energy; thus, the initial energy E is proportional to ψ, which leads to:

Equation (12) can be solved numerically by FEM in which (12) is locally approximated (posed over small partitions called elements of the entire ROI) and a global solution is built by combining the local solutions over these elements [9]. Similarly, referring to Fig. 2, we may divide the ROI into equally spaced grids and then use these grid points to form the elements (i.e., the gray hexagon on the x–y plane illustrated in Fig. 9).

Consider the set of basis functions, μ _i,j with , defined on the A such that μ _i,j has the following properties:

and

Here, \((x_{i^{\prime }}, y_{j^{\prime }})\) is the position of We then approximate Φ, J, and ρ, respectively, by:

in which \(\widetilde {\Phi }_{{i},{j}}=\Phi (x_{i}, y_{j})\), \( {\overset{\sim }{J}}_{i,j}=J\left({x}_i,{y}_j\right) \), and \(\widetilde {\rho }_{{i},{j}}=\rho (x_{i}, y_{j})\) (i.e., the values of Φ, J, and ρ at the grid point , respectively). By substituting (15), (16), and (17) into (12), we obtain the following set of linear equations:

One possible set of candidate functions satisfying (14) are pyramids with peaks at grid points as illustrated in Fig. 9. That is:

Here, \({_{i_{1},j_{1}}}\triangle {^{i_{2},j_{2}}_{i_{3},j_{3}}}\) is the triangle formed by and if all , and are in the ROI. If any of these three grid points is not in the ROI, \({_{i_{1},j_{1}}}\triangle {^{i_{2},j_{2}}_{i_{3},j_{3}}}\) is an empty region. That is:

With the linear basis functions (19), the coefficients, \(K^{i^{\prime },j^{\prime }}_{i,j}\) and g _i,j , in (18) can be derived:

and: in which δ _i,j is defined in (6) and:

Note that it is not difficult to verify that \(K^{i^{\prime },j^{\prime }}_{i,j}=K^{i,j}_{i^{\prime },j^{\prime }}\). For the sake of brevity, the detailed computation of \(K^{i^{\prime },j^{\prime }}_{i,j}\) and g _i,j is given in Appendix 3.

The Gauss-Seidel iteration (GSI) may solve (18) for \(\widetilde {\Phi }_{{i},{j}}\) via iteratively updating each \(\widetilde {\Phi }_{{i},{j}}\) in lexicographical order from the most updated \(\widetilde {\Phi }\) value at other grid points until the update change \(\left |\widetilde {\Phi }_{{i},{j}}^{(k)}-\widetilde {\Phi }_{{i},{j}}^{(k-1)}\right | \leq \varepsilon \) for all That is, \(\widetilde {\Phi }_{{i},{j}}^{(k)}\) are computed sequentially by:

in which \( \mathcal {O}_{L}(i,j)\) defines the lexicographical order; that is:

In GSI, only one \(\widetilde {\Phi }\) is updated in one iteration (21). We say GSI has gone through one sweep when each \(\widetilde {\Phi }\) has been updated once. \(\widetilde {\Phi }_{{i},{j}}^{(k)}\) is the value of \(\widetilde {\Phi }_{{i},{j}}\) after the kth sweep.

Note that if and . Thus, only \(\widetilde {\Phi }_{{i},{j-1}}^{(k)}\), \(\widetilde {\Phi }_{{i-1},{j}}^{(k)}\), \(\widetilde {\Phi }_{{i+1},{j}}^{(k-1)}\), and \(\widetilde {\Phi }_{{i},{j+1}}^{(k-1)}\) are needed to compute \(\widetilde {\Phi }_{{i},{j}}^{(k)}\) via (21). In other words, as long as \(\widetilde {\Phi }_{{i},{j-1}}^{(k)}\) and \(\widetilde {\Phi }_{{i-1},{j}}^{(k)}\) are computed, \(\widetilde {\Phi }_{{i},{j}}^{(k)}\) can be computed.

Accordingly, the distributed routing algorithm, DGSI-FEM, is proposed to coordinate sensors to solve \(\widetilde {\Phi }\)s from (18) in parallel using (21). In DGSI-FEM, a nearby node is selected as the grid head for each grid point to compute the value of \(\widetilde {\Phi }\). The grid head of may update \(\widetilde {\Phi }_{{i},{j}}\) as long as the most updated \(\widetilde {\Phi }_{{i},{j-1}}\) and \(\widetilde {\Phi }_{{i-1},{j}}\) are known; it does not need to wait for the grid heads of all the grid points with lexicographical order less than \(\mathcal {O}_{L}(i,j)\). Note that only these grid heads are involved in the computation of \(\widetilde {\Phi }\)s, resulting in low overhead for a massively dense network. For the sake of brevity, we simply describe the operations of grid points without explicitly mentioning that the operations are actually executed by grid heads.

Since the termination condition is that all the changes made by a sweep fall below a size threshold ε, each grid point needs to know all these changes. To achieve this, DGSI-FEM uses two state packets, PRECISE and DONE, for each grid point, which represent the convergence status and the termination decision, i.e., whether the update changes are small enough and whether the iteration should terminate, respectively. In addition, DGSI-FEM uses two phases (namely, a forward sweep followed by a backward sweep) to propagate the termination decision (via the state packet DONE) and collect the convergence status (via the state packet PRECISE) of all \(\widetilde {\Phi }\)s. Detailed DGSI-FEM is illustrated in Algorithm 2. Note that \(K_{i,j}^{i^{\prime },j^{\prime }}\) and \(\delta _{i^{\prime },j^{\prime }}\) for all and are known in advance. This may be done by letting each grid point discover its adjacent grid points and, once found, exchange \( {\overset{\sim }{J}}_{i,j} \) with them. Additionally, the algorithms for sending and waiting for messages are depicted in Algorithms 3 and 4, respectively. Both algorithms will check whether the communication counterpart is in the ROI and wait will return 〈0,true〉 if not.

After initialization (Lines 1–2), the iteration for will proceed as follows, referring to Fig. 10 for the sequence diagram of DGSI-FEM iteration:

Note that will set PRECISE _i,j as true if the update made by itself is small enough and the PRECISEs of its top and right grid points are true (Lines 31–33). The PRECISEs collected by the \(\mathcal {O}_{L}\)-initiator, which has no bottom and left adjacent grid points (e.g., the grid point with the smallest lexicographical order), indicate whether the update changes of all \(\widetilde {\Phi }\)s are small enough and are used to determine the termination by the \(\mathcal {O}_{L}\)-initiator.

In addition, will set DONE _i,j as true based on the following rules:

After \(\widetilde {\Phi }_{{i},{j}}\)s are solved from (18), \(\widetilde {\mathbf {D}}_{{i},{j}}\) may be approximated by the following formulae, which are derived by using (15) to approximate (10): in which \(\widetilde {\mathbf {D}}_{{i},{j_{x}}}\) and \(\widetilde {\mathbf {D}}_{{i},{j_{y}}}\) are, respectively, the x and y components of \(\widetilde {\mathbf {D}}_{{i},{j}}\). For the sake of brevity, the derivation is given in Appendix 4. Once \(\widetilde {\mathbf {D}}_{{i},{j}}\) is computed, \(\widetilde {\mathbf {u_{f}}}_{{i},{j}}\) can be determined by \(\widetilde {\mathbf {u_{f}}}_{{i},{j}}=\widetilde {\mathbf {D}}_{{i},{j}}/\left |\widetilde {\mathbf {D}}_{{i},{j}}\right |\) and then used as guidance to find the next forwarding nodes for routing information.

We present several numerical results to demonstrate the effectiveness of DGSI-FEM for different scenarios, namely the ROI with holes, the ROI with a nonuniform information generation rate, and the ROI with a nonuniform density. The simulation settings for these scenarios are listed in Table 5. Twenty thousand sensors are randomly deployed based on the density distribution ψ and generate information based on ρ except for the sink which will consume all the information generated. Similarly, routing directions are solved using only the macroscopic parameters, ψ and ρ, but not the detailed position of each node. The node positions are merely used to determine the next forwarding node from the routing directions. In addition, the energy consumption per unit of information is proportional to \(r^{\alpha _{\textit {rf}}}\phantom {\dot {i}\!}\) with α _rf =2 and thus J=ψ ⁴ as indicated in (13).

The routing directions obtained by DGSI-FEM are depicted as arrows in Fig. 11. The arrows provide the routing guidance for load-balancing. For example, Fig. 11 a reveals that information may be forwarded in a direction which deviates from a straight line to the sink to bypass the holes in advance. Thus, unlike many hole-bypassing algorithms [15, 31‐33], using routing directions may alleviate the excess energy consumption of the boundary sensors.

The routing directions shown in Fig. 11 b indicate that, to achieve load-balancing, information may be forwarded to the sensors outside the high- ρ region and then to the sink, instead of being delivered straight to the sink by the sensors in the high- ρ region. Particularly, some nodes around the bottom-right corner of the high- ρ region may forward packets in the opposite direction to the sink in order to avoid using nodes in the high- ρ region. Note that the sensors in the high- ρ region generate more events and potentially have more loading.

The routing directions shown in Fig. 11 c, d indicate that the information traffic tends to flow into the high-density regions and bypass the low-density regions to achieve load-balancing. Similar to Fig. 11 b, Fig. 11 d depicts that some nodes along the bottom-left boundary of the low-density region may forward packets in the opposite direction to the sink in order to avoid using nodes in the low-density region. In the last two scenarios, the ρs are uniform; thus, the sensors in the high-density (or low-density) region generate fewer (or more) events and potentially have less (or more) loading.

We then conducted simulations to compare the energy consumption of the routing directions obtained from DGSI-FEM with that of a microscopic routing algorithm, namely greedy perimeter stateless routing (GPSR) [31]. We used the approach described in Section 4.4 to route the information via the routing directions. Note that GPSR normally works as GF [12]; that is, the next forwarding node will be the one closest to the destination among the current sender’s neighbors. However, if GF fails to find the node making any progress in delivering information, the node to the left in a planar subgraph of the connectivity graph of the WSN will be selected as the next forwarding node until GF recovers. The planarization used here is RNG [34].

We also conducted comparative simulations for another microscopic routing algorithm, namely geographical and energy aware routing (GEAR) [35], which attempts to achieve load-balancing by considering both the distance to the sink and the energy consumption. If a node has neighbors closer to the sink, GEAR will choose among these neighbors the one with the smallest weighted sum of the distance to the sink and the energy consumed as the next forwarding node; otherwise, the neighbor with the smallest weighted sum is the next forwarding node.

Figure 12 depicts the means and standard deviations of the energy consumption of DGSI-FEM and GEAR, normalized to the energy consumption of GPSR. Referring to Fig. 11 a, DGSI-FEM may forward information in a direction which deviates from a straight line to the sink to bypass the holes in advance, while our GPSR implementation uses the left-hand rule to forward information, thus resulting in excess energy consumption along the holes. Hence, DGSI-FEM may achieve better load-balancing with less energy consumption than GPSR for the ROI with holes.

Furthermore, GPSR is degenerated to GF for the ROIs without holes and thus exhibits a lower average energy consumption for the scenarios shown in Fig. 11 b–d. On the other hand, DGSI-FEM will avoid the nodes in the high- ρ and low-density region and utilize the nodes in the high-density region for load-balancing. Thus, the routing paths will bypass the high- ρ and low-density regions or bend into the high-density region.

In addition, though GEAR strives to achieve load-balancing by considering the distance and energy factors, the best next forwarding node is still a local optimum; thus, GEAR provides less effective load-balancing than does DGSI-FEM. The standard deviation results in Fig. 12 b indicate that the routing directions solved by DGSI-FEM can effectively achieve load-balancing, particularly for the ROIs having holes.