Triangular Energy-Saving Cache-Based Routing Protocol by Energy Sieving

Abstract

In wireless ad hoc networks, designing an energy-efficient routing protocol is a major issue since nodes are energy limited. To address energy issue, we proposed a triangular energy-saving cached-based routing protocol by energy sieving (TESCES). TESCES offered a grid leader election by energy sieving (GLEES), a cache-based grid leader maintenance (CGLM), and a triangular energy-saving routing discovery (TESRD). In GLEES, only few nodes join in grid leader election to be elected as a grid leader. New grid leader is elected directly by cache without sending extra control packets in CGLM. TESRD selects an energy-efficient path to transmit data packets. Hence, TESCES could save more energy for transmitting packets and prolong routing lifetime. Simulation results showed that TESCES could reduce 31% of energy consumption, prolong 67% of routing lifetime, and increase 19% of survival ratio of nodes. Furthermore, TESCES may be more outstanding as the number of nodes increased.

1. Introduction

Mobile ad hoc networks (MANETs) had attracted much attention recently. It consisted of a set of mobile nodes that can communicate with others through multiple hops without base stations. Packets sent by the source node are relayed by several intermediate nodes before arriving at the destination node [1–6].

Since battery technology is not likely to progress as fast as computing and communication technologies, designing an energy-efficient protocol to construct energy-efficient routing path becomes an important issue in MANETs [7–10]. The work in [11] indicated the fact that a protocol's behavior does have a significant impact on energy consumption of nodes. A node should tune its wireless interface card into doze mode whenever the node will not lower its own and the network's performance.

Among existing routing protocols, grid-based routing protocols are often used for energy-saving by tuning nodes into doze mode [12–16]. In grid-based routing protocols, once node is elected as a grid leader in its grid. Routing is conducted in a grid-by-grid manner through neighboring grid leaders. Only grid leaders must keep in active mode. Other nodes are tuned into doze mode to save energy without demoting network connectivity.

When the remained energy of the current grid leader will be insufficient for grid management or data transmission, nodes in the same grid need to wake up and tune into active mode once receiving control packets for a grid leader election. However, some of these woken nodes with lower remained energy may consume more redundant energy for grid leader election. For routing discovery, grid-based routing protocols often select the route with minimum hops for transmitting packets without considering the required energy dissipation, such as AODV (ad hoc on demand distance vector routing protocol) [2] or DSR (dynamic source routing protocol) [1].

To address the above issues, we proposed a triangular energy-saving cached-based routing protocol by energy sieving (TESCES) in this paper. In TESCES, a grid leader election based on energy sieving (GLEES), a cache-based grid leader maintenance (CGLM), and a triangular energy-saving routing discovery (TESRD) are constructed. In GLEES, only few nodes need to join in grid leader election by GLEES. Hence, nodes with lower remained energy need not tune into active mode for saving energy. In CGLM, a node is directly to be elected as a new grid leader without broadcasting extra control packets. TESRD builds an energy-efficient routing path for transmitting packets. TESCES therefore could reduce more energy consumption and prolong the lifetime of routes compared with a fully energy-aware and location-aware protocol (FPALA) and an energy-saving cache-based routing protocol (ESCR).

To evaluate and compare the performance of TESCES, FPALA, and ESCR clearly, we provide the mathematical formulas of energy consumption for grid leader election and maintenance. Simulation results showed the efficiency of TESCES. The rest of the paper is in the following sections. Section 2 presented the related work. Section 3 stated TESCES. Section 4 presented simulation results. Section 5 concluded this paper.

2. Related Works

Grid-based routing protocol is a kind of geographic routing protocols based on grid architecture. It partitions the network area into several square/hexagon grids by the location information such as global position system (GPS) [12, 13, 17–19], as shown in Figure 1. Routing is performed in a grid-by-grid manner. One node is elected as a grid leader in its grid. The responsibility of a grid leader includes (i) issuing routing discovery requests to its neighboring grid leaders, (ii) propagating data packets to its neighboring grid leaders, and (iii) maintaining routing paths which pass the grids. Nonleader nodes are not responsible for these jobs unless they are destinations of (i) and (ii) and sources or destinations of (iii). To reduce the unrequired collisions, the communication of nodes is divided into intragrid and intergrid modes. Routing discovery and maintenance could be modified from any of the following protocols: source routing and next-hop routing [14, 17].

Figure 1

(a) Square grid, (b) Hexagon grid.

However, most of grid-based routing protocols concentrated on routing discovery and maintenance without considering energy issues. To address energy issues, a fully energy-aware and location-aware routing protocol (FPALA) [12, 13] and an energy-saving cache-based routing protocol (ESCR) [14] were proposed. FPALA built a power mode management mechanism for grid leader election to save energy. All nodes need to wake up for joining a grid leader election. The node with the maximal remained energy in its grid is elected as the grid leader. Non-leader nodes then tune into doze mode to save energy without demoting the connectivity of network. For grid leader maintenance, FPALA restarts a new grid leader election whenever the remained energy of the current grid leader is insufficient. Nodes thus could save energy in grid leader elections. However, in FPALA, all nodes still need to tune into active mode to be elected as the grid leader by broadcasting extra control packets. Hence, nodes have to extra consume the redundant energy. To address this issue, energy-saving cache-based routing protocol (ESCR) was proposed [14] by us.

ESCR built a cache table in the first grid leader election. While the remained energy of current grid leader is not enough, a candidate node could be elected as a new grid leader directly from cache without broadcasting any controlled packets. ESCR thus could save more energy than FPALA in grid leader maintenance.

However, nodes with lower remained energy still have to broadcast extra control packets in active mode to consume the unnecessary energy for grid leader election. Moreover, FPALA and ESCR both adopt the existing source routing or next-hop routing to build routing paths without considering the energy constrained for routing discovery. We therefore proposed a triangular energy-saving cached-based routing protocol by energy sieving (TESCES) in this paper.

3. Triangular Energy-Saving Cache-Based Routing Protocol by Energy Sieving

Triangular energy-saving cached-based routing protocol by energy sieving (TESCES) is a kind of energy-aware and location-aware grid-based routing protocols in MANETs. TESCES partitions the network area into several square grids based on GPS. One node in each grid is elected as a grid leader. For grid-based area, $r=2\sqrt{2}l,l$ is the side length of grid and r is the radio transmission radius of a grid leader, as shown in Figure 2 [17].

Figure 2

Relation between l and r in grid.

The minimum of value r implies that a grid leader is capable of talking to any one of its 8 neighboring grid leaders. Each node is set with a cache table to record $gi{d}_i,\hspace{0.17em}\hspace{0.17em}i{d}_i$ , and $E_i$ . The $gi{d}_i$ denotes the grid coordinates of node $i,i{d}_i$ denotes the identity of node I, and $E_i$ denotes the remained energy of node i. The gid is defined as ( $X_i^g,Y_i^g$ ) based on the location information from GPS. When the location of node i is at ( $X_i,Y_i$ ), $X_i^g$ and $Y_i^g$ are calculated as $\lfloor X_i/l\rfloor$ and $\lfloor Y_i/l\rfloor$ , respectively. Each node has a unique $id$ , such as MAC address.

In TESCES, routing is performed in a grid-by-grid manner through several grid leaders. Communication is divided into intra-grid and inter-grid modes. In intra-grid mode, node communicates directly with others with the same grid through its grid leader in one hop. In inter-grid mode, node communicates with one in different grid via its grid leader in multiple hops.

For routing discovery, TESCES uses a triangular energy-saving routing discovery (TESRD) to replace a traditional routing discovery, such as AODV [2]. In TESRD, nodes on the selected route could consume less energy by adjusting the transmission energy according to the required transmission distance while forwarding packets to next one.

3.1. Grid Leader Election by Energy Sieving

In grid-based routing protocols, the grid leader is responsible for routing, relaying packets, and maintaining correct operations of grids. Hence, an efficient grid leader election is needed.

However, in traditional grid leader election, all nodes in a grid need to turn into active mode for transmitting election packets. Some nodes thus may consume unnecessary energy because the remained energy is much lower than others in the same grid. For example, $E_1,E_2,E_3$ , and $E_4$ are 40 J, 38 J, 35 J, and 10 J, respectively. Node 4 is impossible to be elected as a grid leader, but it must still consume the un-required energy for election.

Hence, in TESCES, a grid leader election by energy sieving (GLEES) is proposed to address this issue. In GLEES, each node is equipped with a GPS to get its location information. Power energy consumption of nodes could be adjusted by tuning the transmission radius. The full energy of each node is denoted as $E_F$ .

GLEES defined a threshold value of joining in grid leader election ( $E_{\text{join}}$ ). Initially, $E_{\text{join}}$ is set to $E_F\times 0.9$ . Before joining in grid leader election, each node in the same grid compares its remained energy $E_i$ with $E_{\text{join}}$ . While $E_i$ is larger than $E_{\text{join}}$ , node i tunes into active mode and joins the grid leader election. Otherwise, node i is kept in doze mode. Hence, only few nodes join the leader election. Other nodes with lower energy are kept in doze mode to save energy. Process of GLEES is stated as follows.

• (1)

First, node i compares $E_i$ with $E_{\text{join}}$ . While $E_i$ is larger than $E_{\text{join}}$ , node i broadcasts a BID( ${gid}_i,{id}_i,E_i$ ) packet. Otherwise, node i is kept in doze mode.

(2)

While node j receives a BID packet, node j compares $E_j$ with $E_i$ listed in the received BID packet. If $E_j$ is larger than $E_i$ , node j replaces $E_i$ with $E_j$ . Then, node j broadcasts the updated BID packet with $E_j$ to its neighboring nodes in its grid; otherwise, node j stops broadcasting.

(3)

When the last node i does not get any BID packet in a predefined time ( $T_{\text{pre}}$ ), node i transfers itself into the grid leader. Then it declares its existence by broadcasting a GATE( $gi{d}_i,i{d}_i$ ) packet to all nodes in its grid.

(4)

When node k receives a GATE packet, it replies a BID_E( $gi{d}_k,gi{d}_k,E_k$ ) packet to its grid leader.

(5)

The grid leader sorts its cache table in a descending way by $E_k$ recoreded in BID_E packets from all nodes.

GLEES could avoid no grid leader to be elected in grid leader election. When no grid leader is elected after $T_{\text{pre}},E_{\text{join}}$ is decreased to be multiplied by 0.9, and then GLEES restarts.

For example, $E_F$ is set to 40 (J); thus $E_{\text{join}}$ ( $E_F\times 0.9$ ) is 36 (J), initially. The remained energy of 11 nodes is shown in Figure 3. Without GLEES, each node needs to consume k (J) to join a grid leader election by broadcasting a packet. The total energy consumption for joining in grid leader election is $11\times k$ . In GLEES, only nodes 1, 2, and 10 need to join the grid leader election since $E_1,E_2$ , and $E_{10}$ are larger than $E_{\text{join}}$ . The total energy consumption thus reduces to be $3\times k$ .

Figure 3

Example of GLEES.

3.2. Cache-Based Grid Leader Maintenance

Routing maintenance is to keep the lifetime of a routing as long as possible. Under TESCES, except the source and destination nodes, each intermediate node is the grid leader. Therefore, the grid leader maintenance in each grid is an important issue for routing maintenance. To address this issue, cache-based grid leader maintenance (CGLM) was proposed. When the remained energy ( $E_{\text{rem}}$ ) of current grid leader is lower than the threshold energy ( $E_{\text{th}}$ ) of retired grid leader, the grid leader maintenance is started. Process of CGLM is as follows.

• (1)

When $E_{\text{rem}}$ of grid leader is lower than $E_{\text{th}}$ , the grid leader retrieves the candidate $id$ from the first row in its cache table. Then it unicasts a GATE_E( $gid,id,NT,CT$ ) packet to the new grid leader directly, where $NT$ is the neighboring grid leader table and $CT$ is the cache table. The former grid leader then could transfer itself into an ordinary node.

(2)

The new grid leader broadcasts a GATE packet to declare its existence and then deletes the first row in its $CT$ .

(3)

While $CT$ becomes empty, $CT$ has to be reestablished by GLEES.

In CGLM, new grid leader is elected directly without broadcasting any extra control packets. CGLM thus could save more power energy for data transmission.

For example, assume that $E_F$ is 40 (J), $E_{\text{th}}$ is set to 15 (J), and node 5 is the current grid leader, as shown in Figure 4. Once $E_5$ is less than $E_{\text{th}}$ , new grid leader has to be elected. In FPALA, all nodes need to join in grid leader election. The total energy consumption thus is $10\times k$ for election. In CGLM, only node 5 needs consuming k (J) to unicast a packet to node 2 that becomes the new grid leader directly. Other nodes tune into doze mode to save energy. Hence, CGLM could save more energy than FPALA.

Figure 4

Example of CGLM.

3.3. Triangular Energy-Saving Routing Discovery

In traditional grid-based routing protocols, minimum hop routing discovery is often used through several grid leaders without considering the energy constrain [12, 17]. To address this issue, we proposed a triangular energy-saving routing discovery (TESRD) by integrated HCB model [8, 9, 20] with GPSR [21].

TESRD is a two-phase process. In the first phase, packets are marked with their destinations' locations by their originator. A forwarding grid leader makes a locally optimal choice to decide the next packet's hop. The locally optimal choice of next hop is the neighboring leader that is geographically closest to the next packet's destination. Forwarding packets in this regime follows the closer geographic hops until the destination is reached.

In the second phase, TESRD adopts a greedy algorithm to compute global near-optimal power-efficient routings based on the local optimal choice for the next forwarding node. In TESRD, let s be the sending node and r the next receiving node along the routing path. The distance d is measured from s to r. Transmission energy consumption is proportional to $d^{\alpha }$ for $\alpha \ge 2$ based on HCB model [20]. Before s forwarding RREQ (route request) to $r,s$ finds an intermediate node i from its neighboring leaders to r in one hop. If ${\overline{si}}^2+{\overline{ir}}^2<{\overline{ir}}^2$ , s utilizes the intermediate leader i to forward a packet instead of sending the packet directly to r, where $({\overline{si}}^2+{\overline{ir}}^2)<({\overline{sj}}^2+{\overline{jr}}^2)$ as shown in Figure 5.

Figure 5

Example of TESRD.

To reduce energy consumption, TESRD could select a more energy-saving path based on the changes of gid of next intermediate node. Assume that the gid of node s and r are ( $X_s^g,Y_s^g$ ) and ( $X_r^g,Y_r^g$ ), respectively. In case 1, if $X_s^g\ne X_r^g$ and $Y_s^g\ne Y_r^g$ , TESRD selects the two intermediate grid leaders located at ( $X_s^g,Y_r^g$ ) and ( $X_r^g,Y_s^g$ ) to find a more energy-saving path, as shown in Figure 6.

Figure 6

Case 1 in TESRD.

In case 2, if $X_s^g=X_r^g$ and $Y_s^g\ne Y_r^g$ , apply the four intermediate grid leaders in ( $X_s^g-1,Y_r^g$ ), ( $X_s^g-1,Y_s^g$ ), ( $X_s^g+1,Y_r^g$ ), and ( $X_s^g+1,Y_s^g$ ) to find an energy-saving path, as shown in Figure 7.

Figure 7

Case 2 in TESRD.

In case 3, if $X_s^g\ne X_r^g$ and $Y_s^g=Y_r^g$ , TESRD selects the four intermediate grid leaders in ( $X_s^g,Y_s^g-1$ ), ( $X_s^g,Y_s^g+1$ ), ( $X_r^g,Y_s^g-1$ ), and ( $X_r^g,Y_s^g+1$ ) for finding a more energy-saving path, as shown in Figure 8.

Figure 8

Case 3 in TESRD.

3.4. Medium Access Control Channel Assignment

In TESCES, routing is conducted in two levels: intra-grid and inter-grid. The former is supported by the point coordination function (PCF) of IEEE 802.11, and the latter is supported by the distributed coordination function (DCF) of 802.11. The time interval is divided evenly into a sequence of superframes for all nodes participating in the networks. We appendixed BID_E and GATE_E packets to the modified superframe based on FPALA. The inter-grid and intra-grid routing phases are under the superframe, as shown in Figure 9.

Figure 9

Superframe of TESCES.

In the leader phase, all nodes must be awake. Only leaders have right to access their channels. If no leader exists in a grid, the next phase becomes an election phase for nodes to compete to be a grid leader. If E of the leader is below $E_{\text{th}}$ , the next phase becomes a maintenance phase to generate a new grid leader. In the intra-grid phase, the leader polls its nodes in a round-robin manner. In the inter-grid phase, only leaders can send/receive packets. Since more than one node may try to compete as a grid leader, the BID packets are broadcasted in a contention basis. In TESCES, superframes need to be synchronized among all grids.

For the intra-grid routing, if a packet is targeted at a node resident in the same grid, this packet is sent to the node directly during the intra-grid phase. For the inter-grid routing, a packet is forwarded in a grid-by-grid manner during the inter-grid phase. An inter-grid routing could be modified based on the protocols: source routing or next-hop routing. However, these protocols do not address the energy issue. Hence, we proposed a triangular energy-saving routing discovery (TESRD) in TESCES.

To avoid channel interference among neighboring grids, totally night channels are needed in TESCES, as shown in Figure 10. The number (1–9) in each grid represents the channel to be used by that grid. The channels based on frequency reuse form a pattern, called a cluster that appears repeatedly in a regular way.

Figure 10

Channel Assignment in TESCES.

3.5. Energy Consumption Formula

To evaluate the performance effectively, the notations in the energy formula were defined as listed in Table 1. We formulated the energy consumption of grid leader election in TESCES, $E_{\text{ele}}^{\text{TES}}$ , in (1) including $N_G^i,\hspace{0.17em}{P}_J(0\le P_J\le 1$ ), $P_B(0\le P_B\le 1$ ), $L_{\text{BID}},\hspace{0.17em}\hspace{0.17em}{L}_{\text{RTS}},\hspace{0.17em}\hspace{0.17em}{L}_{\text{CTS}},\hspace{0.17em}\hspace{0.17em}{T}_{\text{ele}},\hspace{0.17em}\hspace{0.17em}{T}_{\text{lea}},\hspace{0.17em}\hspace{0.17em}{T}_{\sup \hspace{0.17em}},D,\hspace{0.17em}\hspace{0.17em}{E}_t$ , and $E_d$ . In FPALA, $E_{\text{ele}}^{\text{FPA}}$ , its energy consumption of a grid leader election is defined as (2). In ECSR, its energy consumption of a grid leader election, $E_{\text{ele}}^{\text{ESCR}}$ , is calculated as (3). Since $P_J$ equals 1 in FPALA and ESCR, $E_{\text{ele}}^{\text{TES}}$ is not larger than $E_{\text{ele}}^{\text{FPA}}$ and $E_{\text{ele}}^{\text{ESCR}}$ :

$\begin{array}{cc}\hfill E_{\text{ele}}^{\text{TES}}& =\left(\begin{array}{c}\lceil \frac{N_{\text{G}}^i\times P_J\times \left(L_B+L_{\text{RTS}}+L_{\text{CTS}}\right)}{T_{\text{ele}}\times D}\rceil \\ +\hspace{0.17em}{N}_G^i\times \lceil \frac{L_G}{T_{\text{lea}}\times D}\rceil \end{array}\right)\hfill \\ \hfill & \hspace{1em}\times T_{\sup }\times E{C}_a\hfill \\ \hfill & \hspace{1em}+\left(\lceil \frac{N_G^i\times \left(1-P_J\right)\times (L_B+L_{\text{RTS}}+L_{\text{CTS}})}{T_{\text{ele}}\times D}\rceil \right)\hfill \\ \hfill & \hspace{1em}\times T_{\sup }\times E{C}_d,\hfill \end{array}$

(1)

$\begin{array}{cc}\hfill E_{\text{ele}}^{\text{FPA}}& =\left(\begin{array}{c}\lceil \frac{N_G^i\times \left(L_B+L_{\text{RTS}}+L_{\text{CTS}}\right)}{T_{\text{ele}}\times D}\rceil \\ +\hspace{0.17em}{N}_G^i\times \lceil \frac{L_G}{T_{\text{lea}}\times D}\rceil \end{array}\right)\hfill \\ \hfill & \hspace{1em}\times T_{\sup }\times E{C}_a,\hfill \end{array}$

(2)

$\begin{array}{cc}\hfill E_{\text{ele}}^{\text{ECSR}}& =\left(\begin{array}{c}\lceil \frac{N_G^i\times \left(L_B+L_{\text{RTS}}+L_{\text{CTS}}\right)}{T_{\text{ele}}\times D}\rceil \\ +N_G^i\times \lceil \frac{L_G}{T_{\text{lea}}\times D}\rceil \\ +\lceil \frac{N_G^i\times (L_{BE}+L_{\text{RTS}}+L_{\text{CTS}})}{T_{\text{lea}}\times D}\rceil \end{array}\right)\hfill \\ \hfill & \hspace{1em}\times T_{\sup }\times \hspace{0.17em}E{C}_a.\hfill \end{array}$

(3)

Table 1

Notations of mathematical formula.

Name	Description
$E_{\text{ele}}^{\text{TES}}$	Energy consumption of grid leader election in TESCES
$E_{\text{ele}}^{\text{FPA}}$	Energy consumption of grid leader election in FPALA
$E_{\text{ele}}^{\text{ESCR}}$	Energy consumption of grid leader election in ESCR
$E_{\text{mai}}^{\text{TES}}$	Energy consumption of grid leader maintenance in TESCES
$E_{\text{mai}}^{\text{ESCR}}$	Energy consumption of grid leader maintenance in ESCR
$E_r^{\text{TES}}$	Energy consumption of routing in TESCES
$E_r^{\text{FPA}}$	Energy consumption of routing in FPALA
$E_r^{\text{ESCR}}$	Energy consumption of routing in ESCR
$N_G^i$	Total nodes in the ith grid
$P_J$	Probability of nodes joining a grid leader election
$P_B$	Probability of nodes broadcasting a BID packet in a grid leader election
$L_B$	Length of BID packet
$L_{BE}$	Length of BID_E packet
$L_G$	Length of GATE packet
$L_{GE}$	Length of GATE_E packet
$L_{\text{RTS}}$	Length of RTS packet
$L_{\text{CTS}}$	Length of CTS packet
$L_{\text{data}}$	Length of DATA packet
$L_{\text{RREQ}}$	Length of RREQ packet
$L_{\text{RREP}}$	Length of RREP packet
$T_{\text{ele}}$	Time interval of election phase
$T_{\text{lea}}$	Time interval of leader phase
$T_{\sup \hspace{0.17em}}$	Time interval of a superframe
$T_{\text{tra}}$	Time interval of intra-grid phase
$T_{\text{ter}}$	Time interval of inter-grid phase
D	Transmission data rate
$\text{E}{\text{C}}_a$	Energy consumption in active mode
$\text{E}{\text{C}}_d$	Energy consumption in doze mode
$E_a^{si}$	Energy consumption from sender to intermediate leader i
$E_a^{ir}$	Energy consumption from intermediate leader i to receiver
$E_a^{sr}$	Energy consumption from sender to receiver
$N_{\text{data}}$	Number of data packets along the routing
$N_{\text{lea}}$	Number of total leaders along the routing
$\overline{sr}$	Distance from sending node to receiving node
$\overline{si}$	Distance from sending node to intermediate node i
$\overline{ir}$	Distance from intermediate node to receiving node i

The formula of energy consumption of the grid leader maintenance of TESCES is calculated as (4). For FPALA, the formula of energy consumption of grid leader maintenance is the same as $E_{\text{ele}}^{\text{FPA}}$ . In ECSR, the formula of energy consumption of the grid leader maintenance is calculated as (5). Because the energy consumption of doze mode is much lower than that of active mode, it proves that TESCES could save more energy than that of FPALA and ESCR for the grid leader election and maintenance by (1)–(5):

$\begin{array}{cc}\hfill E_{\text{mai}}^{\text{TES}}& =N_G^i\times \lceil \frac{L_{GE}}{T_{\text{lea}}\times D}\rceil \times T_{\text{lea}}\times E_a\hfill \\ \hfill & \hspace{1em}+N_G^{\text{i}}\lceil \frac{L_{GE}}{T_{\text{lea}}\times D}\rceil \times \left(T_{\text{ele}}+T_{\text{tra}}+T_{\text{ter}}\right)\times E_d,\hfill \end{array}$

(4)

$\begin{array}{cc}\hfill E_{\text{mai}}^{\text{ESCR}}& =N_G^i\times \lceil \frac{L_{GE}}{T_{\text{lea}}\times D}\rceil \times (T_{\text{lea}}+T_{\text{ele}})\times E_a\hfill \\ \hfill & \hspace{1em}+N_G^{\text{i}}\lceil \frac{L_{GE}}{T_{\text{lea}}\times D}\rceil \times \left(T_{\text{tra}}+T_{\text{ter}}\right)\times E_d.\hfill \end{array}$

(5)

Energy consumption of routing discovery is calculated based on time of transmitting packets. Hence, examining the total superframes is to obtain transmitting time for TESCES, FPALA, and ESCR. Assume that the number of grid leaders along the routing is $N_{\text{lea}}$ . In TESCES, it needs a RREP packet, a RREQ packet, and data packets ( $N_{\text{data}}$ ) to build a routing path and transmit data packets. Total lengths of these packets are $L_{\text{data}}\times N_{\text{data}}+(L_{\text{RREQ}}+L_{\text{RREP}})$ . Since routing discovery is performed in inter-grid phase, the number of superframes could be computed as $L_{\text{data}}\times N_{\text{data}}+(L_{\text{RREQ}}\hspace{0.17em}+\hspace{0.17em}{L}_{\text{RREP}})$ divided by $(T_{\text{ter}}\times D)$ . Because TESCES needs an intermediate node to consume less energy to forward packets, the energy consumption of routing discovery in TESCES ( $E_r^{\text{TES}}$ ) is defined as (6). Since FPALA and ESCR do not use intermediate nodes to forward packets, the energy consumption of routing in both are the same as (7) and (8). Based on HCB model [20], the energy consumption $E_a^{si}$ and $E_a^{ir}$ are defined as (9) and (10). Because ${\overline{si}}^2+{\overline{ir}}^2<{\overline{sr}}^2$ in TESCES, $E_r^{\text{TES}}$ must be less than or equal to $E_r^{\text{FPA}}$ and $E_r^{\text{ESCR}}$ . By (6)–(8), formulas showed that TESCES could reduce more energy consumption of routing discovery than FPALA and ESCR:

$\begin{array}{cc}\hfill E_r^{\text{TES}}& =\lceil \frac{L_{\text{data}}\times N_{\text{data}}+(L_{\text{RREQ}}+L_{\text{RREP}})}{T_{\text{ter}}\times D}\rceil \hfill \\ \hfill & \hspace{1em}\times N_{\text{lea}}\times T_{\sup }\times \left(E_a^{si}+E_a^{ir}\right),\hfill \end{array}$

(6)

$\begin{array}{cc}\hfill E_r^{\text{FPA}}& =\lceil \frac{L_{\text{data}}\times N_{\text{data}}+(L_{\text{RREQ}}+L_{\text{RREP}})}{T_{\text{ter}}\times D}\rceil \hfill \\ \hfill & \hspace{1em}\times N_{\text{lea}}\times T_{\sup }\times E_a^{sr},\hfill \end{array}$

(7)

$\begin{array}{cc}\hfill E_r^{\text{ESCR}}& =\lceil \frac{L_{\text{data}}\times N_{\text{data}}+(L_{\text{RREQ}}+L_{\text{RREP}})}{T_{\text{ter}}\times D}\rceil \hfill \\ \hfill & \hspace{1em}\times N_{\text{lea}}\times T_{\sup }\times E_a^{sr},\hfill \end{array}$

(8)

$\begin{array}{cc}\hfill E_a^{si}& =E_a^{sr}\times \frac{{\overline{si}}^2}{{\overline{sr}}^2}\hfill \end{array},$

(9)

$\begin{array}{cc}\hfill E_a^{ir}& =E_a^{sr}\times \frac{{\overline{ir}}^2}{{\overline{sr}}^2}\hfill \end{array}.$

(10)

4. Simulation Results

Performance of TESCES was measured and compared with those of FPALA and ESCR by simulations coded in a C# language. First, we described the simulation environment and performance metrics and then analyzed the experimental results. The simulation parameters are listed in Table 2. The time ratio of the intra-grid phase to the inter-grid phase is 1 : 4. Energy consumption could be adjusted based on the transmission radius of nodes [12, 14].

Table 2

Simulation parameters.

Name	Value
Simulation area	$1000\times 1000$  m2
Number of grids	$10\times 10$
Number of nodes ( $N_n$ )	100, 200, 400
Side length of grid (d)	100 m
Transmission radius of a radio signal (r)	$200\sqrt{2}$  m
Data rate (D)	11 Mbits/s
Time interval time of a superframe ( $T_{\sup \hspace{0.17em}}$ )	200 ms
Time interval of leader phase ( $T_{\text{lea}}$ )	1 ms
Time interval of election phase ( $T_{\text{ele}}$ )	4 ms
Transmission rate	200 packet/s
Size of packet	1500 bytes
Full battery energy of a node ( $E_F$ )	40 J
Threshold value of retirement ( $E_{\text{th}}$ )	8 J
Energy consumption in active mode ( ${\text{EC}}_a$ )	280 mW
Energy consumption in doze mode ( $\text{E}{\text{C}}_d$ )	10 mW

4.1. Performance Metrics

We evaluate the routing lifetime ( $T_r$ ), average energy consumption ( $E_{\text{avg}}$ ), and ratio of survival nodes ( $R_s$ ) under TESCES, FPALA, and ESCR, respectively. $T_r$ is defined as the time span from that the routes are living to that no path is between the source and destination nodes. $E_{\text{avg}}$ is defined as the total energy consumption ( $E_t$ ) divided by $T_r$ . $R_s$ denotes the radio of survival nodes being with higher energy than $E_{\text{th}}$ to the total nodes in the initial networks.

4.2. Experimental Results

TESCES improves 67% and 84% of $T_r$ more than ESCR and FPALA, respectively, for $N_n$ is 100, as shown in Figure 11. While $N_n$ is 400, TESCES improves 90% and 2 times of $T_r$ more than ESCR and FPALA, respectively.

Figure 11

Routing Lifetime.

Figure 12 showed that TESCES reduces 31% of $E_t$ compared with $E_t$ of ESCR and 40% with $E_t$ of FPALA when the simulation time is around 620 seconds. $T_r$ is different among TESCES, ESCR, and FPALA, and we further evaluate $E_{\text{avg}}$ , as shown in Figure 13. Figure 13 showed that TESCES could reduce more $E_{\text{avg}}$ , as $N_n$ is increased.

Figure 12

Total energy consumption ( $N_n=400$ ).

Figure 13

Average energy consumption ( $N_n=\mathrm{100,200}$ , and 400).

TESCES increases 9% of $R_s$ in ESCR and 13% of $R_s$ in FPALA, while $N_n$ is 100 and simulation time is 200 seconds, as shown in Figure 14. While $N_n$ is 400 and simulation time is 600 seconds, TESCES increases 11% of $R_s$ in ESCR and 19% of $R_s$ in FPALA, as shown in Figure 15. Figures 14 and 15 also showed that the utilization of TESCES is higher than that of FPALA and ESCR, because no path is between the sending and receiving nodes, while the unused alive nodes of FPALA and ESCR both are still over 90% of total nodes.

Figure 14

Survival ratio of nodes ( $N_n=100$ ).

Figure 15

Survival ratio of nodes ( $N_n=400$ ).

Energy consumption evaluation is consisted of the energy consumption of grid leader election, grid leader maintenance, and routing discovery. Hence, the formulas (1)–(8) are used in constructing these figures.

Simulation is ended off when no path exists between the source and destination nodes. The available routing paths in FPALA and ESCR both are broken earlier than TESCES. The curves for ESCR and FPALA thus do not continue for whole simulation time, as shown in Figures 12, 14, and 15.

To avoid most of nodes to consume redundant energy, $E_{\text{join}}$ is set to $E_F\times 0.9$ , initially. If no grid leader is elected in the first time, $E_{\text{join}}$ is further decreased to be multiplied by 0.9. Different $E_{\text{join}}$ , however, may affect $E_t$ of TESCES. We vary $E_{\text{join}}$ that decreased to be multiplied from 0.9 to 0.1 for evaluating $E_t$ in 200, 400, and 800 of $N_n$ , respectively, as shown in Figures 16, 17, and 18.

Figure 16

Energy consumption with different $E_{\text{join}}$ ( $N_n=200$ ).

Figure 17

Energy consumption with different $E_{\text{join}}$ ( $N_n=400$ ).

Figure 18

Energy consumption with different $E_{\text{join}}$ ( $N_n=800$ ).

In Figures 16, 17, and 18, $E_t$ in different $E_{\text{join}}$ and $N_n$ are all the same before the half of the longest simulation time. For example, in Figure 16, the largest simulation time is around 1000 (s), $E_t$ in different $E_{\text{join}}$ are the same before 500 (s). This is caused that the remained energy of most nodes are the same approximately before the half of simulation lifetime. Hence, the number of nodes joined in grid leader election is around the same even in different $E_{\text{join}}$ . After the half of routing lifetime, the difference of remained energy among all nodes is increased. The number of nodes joined in grid leader election with different $E_{\text{join}}$ is different gradually. $E_t$ in different $E_{\text{join}}$ thus are getting different obviously. As s result, we focus on $E_t$ after the half of simulation time.

In Figure 16, TESCES has largest $E_t$ with $E_{\text{join}}=E_{\text{join}}\times 0.3$ , while $N_n$ is 200. TESCES has largest $E_t$ with $E_{\text{join}}=E_{\text{join}}\times 0.3$ , as $N_n$ is 400, as shown in Figure 17. However, TESCES has largest $E_t$ with $E_{\text{join}}=E_{\text{join}}\times 0.1$ , as $N_n$ is 800, as shown in Figure 18. In Figures 16, 17, and 18, TESCES does not have the worst case for energy consumption in fixed $E_{\text{join}}$ . This is caused that the remained energy of nodes may be the same or much different compared with that of others in each time of GLEES and CGLM.

In Figures 16, 17, and 18, TESCES in $E_{\text{join}}=E_{\text{join}}\times 0.9$ had the least $E_t$ or less $E_t$ than in other $E_{\text{join}}$ . It proved that $E_{\text{join}}=E_{\text{join}}\times 0.9$ is the best or better value to reduce more energy consumption for TESCES. Once selecting the wrong or different $E_{\text{join}}$ , TESCES may consume more energy.

5. Conclusions

Since the power energy of mobile nodes are limited, designing an efficient energy-saving routing protocol becomes an important issue in wireless ad hoc networks. To address this issue, many energy-aware routing protocols were proposed. Among these protocols, grid-based routing protocol is the general solution because nodes could be tuned into doze mode to save energy. The grid-based routing protocol is composed of grid leader election, grid leader maintenance, and routing discovery.

In grid leader election, each node has to consume energy to be elected as a grid leader. However, some nodes are unsuitable to be the grid leader because its remained energy is much lower than that of others. Nodes with lower remained energy need not consume the redundant energy in grid leader election.

In grid leader maintenance, each node needs to be in active mode for a grid leader election when the remained energy of current grid leader is insufficient for forwarding packets.

In routing discovery, most of grid-based routing protocols concentrated on robustness and minimum hop count of routes but ignored the required energy consumption. Nodes thus may consume more energy to transmit data.

To address the above issues, a triangular energy-saving cache-based routing protocol by energy sieving (TESCES) was proposed in this paper. In TESCES, a grid leader election by energy sieving (GLEES), a cache-based grid leader maintenance by cache (CGLM), and a triangular energy saving routing discovery (TESRD) are constructed.

In GLEES, only some nodes need to join a grid leader election to be elected as a grid leader, and other nodes are turned into doze mode to save energy. In CGLM, the new grid leader is appointed from cache table directly without broadcasting control packets to save energy while the remained energy of current grid leader is lower than the threshold. TESRD selects an energy-efficient routing path compared with the on-demand routing discovery. Therefore, TESCES could save more energy for data transmission and prolong the time of routing.

To measure and compare the performance of TESCES, FPALA, and ESCR, we conducted some simulations for evaluating grid leader election, grid leader maintenance, and routing discovery. Simulation results proved that TESCES could save more power energy than FPALA and ESCR.

Experimental results showed that TESCES prolongs 67% of ESCR and 84% of FPALA, respectively. For energy consumption, TESCES reduces 31% of ESCR and 40% of FPALA. For survival ratio of nodes, TESCES increases 11% of ESCR and 19% of FPALA.

Furthermore, the routing lifetime, energy consumption, and survival ratio of nodes may be better in TESCES as the number of mobile nodes is increased.