{'fraction_non_alphanumeric': 0.039638505977235027, 'fraction_numerical': 0.014356803752216438, 'mean_word_length': 4.248874211948364, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Energy-Efficient Cell Partition of 3D Space for Sensor Networks with Location Information

In the wireless sensor networks composed of battery-powered sensor nodes, one of the main issues is how to save power consumption on each node. The usual approach to this problem is to activate only necessary nodes (e.g., those nodes which compose a backbone network), and to put other nodes to sleep. One such algorithm using location information is GAF (Geographical Adaptive Fidelity), and GAF is enhanced to HGAF (Hierarchical Geographical Adaptive Fidelity). In this paper, we study the energy-efficient partition of a 3 dimensional sensor field into cells. Further, we give a theoretical upper bound on cell size for this problem.


Introduction
Wireless sensor networks have gained much attention in recent research and development. In the wireless sensor networks, battery-powered sensor nodes are placed on the observation area, and the sensed data is transmitted to the observer by multi-hop communication between nodes. Traditionally, the routing protocols for these networks have been evaluated in terms of packet loss rates, routing overhead, etc. However, since wireless sensor networks are usually deployed using battery-powered nodes, the optimization of routing protocol's energy consumption is also important [1][2] [3].
The usual technique for designing an energy-efficient routing protocol is to activate only necessary nodes (e.g., those nodes which compose a backbone network) and to put other nodes to sleep [4][5] [6] [7][8] [9][10] [11]. Among these protocols, in this paper we focus on GAF (Geographical Adaptive Fidelity) [11] and its extended version called HGAF (Hierarchical Geographical Adaptive Fidelity) [6] [7][8] [9]. In the GAF-based algorithms, the sensor field is partitioned by regions called cells, and the cell size affects the energy efficiency of the protocols. Table 1 summarizes the maximum cell sizes for the GAF-based methods that use regular polygon as cell shapes. As shown in Table 1, we successfully obtained the cell size of 3 3 4 ( ) R 2 [7], which is 29.9% larger than that of eHGAF whose cell size is R 2 [6]. In [9], we studied a theoretical upper bound on the cell size, and showed that the upper bound is πR 2 − Δ , where R denotes the communication range of each sensor node and In [8], we gave an algorithm that uses two types of different cell shapes, and obtained that the cell size can be 3R 2 at largest. Since the theoretical upper bound is approximately 1.91R 2 , the cell size obtained in [8] is fairly close to it.
In this paper, we extend the sensor field to 3-dimensional space, and study the power-efficient partitioning of the field into regular polyhedral cells. Further, we prove a theoretical upper bound on the cell size for this problem.
The rest of this paper is organized as follows. Section 2 introduces related works. Section 3 explains the outline of GAF and HGAF. Section 4 extends the sensor field to 3D space, and provides a theoretical upper bound on the cell size. And finally Section 5 offers concluding remarks.

Related Works
Similarly to GAF, the protocol SPAN saves power consumption by reducing the number of active nodes on the entire network [4]. In SPAN, each node makes its decisions based on the number of neighbor nodes and residual energy, and does not use geographical information. In [12], Liu et al. improved the connectivity among nodes by using honeycomb cells while maintaining the energy efficiency of GAF. In [13], Inagaki et al. extended GAF to HGAF by using a layered structure, and showed extensive simulation results. In [14], Nazrul Alam et al. examined various cell shapes for partitioning 3D sensor field, and studied the network lifetime etc. for each shape comprehensively. In [14], they focused on the number of active nodes as the metrics of energy consumption just as we do here, but their mechanism does not use the hierarchal structure for cell partition like HGAF does.

Preliminaries
Throughout the paper, as in [6][7][8] [9][11], we assume that the radio range of each node is R and is unchanged during the operation, and that every node knows its own location information. The detailed explanation about the equations in this section can be found in [11] [13].

GAF (Geographical Adaptive Fidelity)
In GAF [11], the entire sensor field is divided into virtual sub-fields called cells. In each cell, a node called active node is chosen. These active nodes have the following two missions: (I) The active nodes compose a backbone network for inter-cell data transmissions. Every data across cell-boundaries is conveyed through this backbone in multi-hop manner.
(II) Each active node acts as a gateway node of its own cell. Every transmission across the cell-boundary is via the gateway node.
Each active node is not fixed, and is properly changed over by the other node in the same cell, according to the remaining amount of battery at the time. The election is dynamically performed by the leader-election algorithm [11]. The active nodes are steadily activated, while other nodes are activated only when necessary and are being asleep most of the time. In GAF, nodes are in one of three states: sleeping, discovery, and active. A state transition diagram is shown in Figure 1. Initially, nodes start out in the discovery state. In the discovery state, a node turns on its radio and exchanges discovery messages to find other nodes within the same cell. The discovery message contains a tuple of node id, cell id, estimated node active time, and node state. In the active state, a node plays as an active node for Ta time at longest. In the sleeping state, a node turns off its radio and stays in sleep mode for Ts time. GAF leaves choices of many parameters including Td, Ta, node rank, Ts, etc. The reader should refer [11] for the details.

Figure 1. State transitions in GAF
From the viewpoint of energy consumption, it is preferable to make the cell as large as possible [6]. This is because the larger a cell becomes, the smaller the total number of active nodes in the entire sensor field is. The cell size, however, has an upper bound, and we cannot make it larger without limitation. The upper bound is subject to the communication range of each sensor nodes and the following two requirements: In GAF, the sensor field is simply divided by square shaped cells of the same size (see Figure 2). Let the size of cell be r × r . For GAF, the requirements (Req.I) and (Req.II) are respectively taken on concrete formulas as follows: The inequality (Req.I -GAF) is due to Figure 3(a), and the inequality (Req.II -GAF) is due to Figure 3(b). From these inequalities, we have and thus the following claim holds: Claim 1. [11] In GAF, the cell size is bounded above by 1 5

HGAF(Hierarchical Geographical Adaptive Fidelity)
In HGAF [6], the cell size can be 1 2 ( ) R 2 at largest, by relaxing the dominant condition The key idea is to avoid the extreme case illustrated in Figure 3(a). In HGAF, each cell is further divided into smaller squares called subcells. A cell of size r × r is divided into subcells of size d × d . For simplify the exposition, we consider only the case where r is divisible by d.
A subcell is called an active subcell if it contains an active node of the cell. In HGAF, active subcells are maintained in the same position of the respective cells, and their positions are synchronously rotated (see Figure 4). By this modification, as for (Req.I), we have only to consider the case illustrated in Figure 5. As for (Req.II), the inequality is the same as that of GAF. Hence, we have (Req.I-HGAF) (a) the case where the distance between two active nodes of adjacent cells is the largest.
(b) the case where the distance between an active node and a node in the same cell is the largest. (Req.II-HGAF) From (Req.I-HGAF), we have and r can be R at largest when we let d be infinitesimal (i.e., the partition of each cell into subcells is infinitely fine-grained). Hence, the constraint (Req.II-HGAF) becomes the dominant condition here, and thus the following claim holds: Claim 2. [6] In HGAF, the cell size is bounded above by 1 2 ( )R 2 .
■ Figure 4. Rotation of active subcells . Figure 5. An example supporting (Req.I) for HGAF. Here, the distance between two active nodes of adjacent cells is the largest.

eHGAF(extended Hierarchical Geographical Adaptive Fidelity)
In eHGAF [6], the cell size is improved and can be R 2 at largest. Here, the dominant constraint for HGAF, (Req.II-HGAF), is relaxed by keeping active subcells centered. For simplicity, we assume that r is divisible by d and that the quotient is an odd number. To place an active subcell in the center of its cell, the cell-boundaries are synchronously slid during the operation (see Figure 6). By this modification, for (Req.II), we have only to consider the case illustrated in Figure 7. As for (Req.I), the inequality is the same as that of HGAF. Hence, we have From (Req.I-eHGAF), r can be R at largest when we let d be infinitesimal. From (Req.II-eHGAF), r can be 2R at largest for infinitesimal d. Hence, the constraint (Req.I-eHGAF) becomes the dominant condition here, and thus the following claim holds: Claim 3. [6] In eHGAF, the cell size is bounded above by R 2 . ■ Figure 6. Cell-boundaries are synchronously slid during the operation so that the active subcells are kept in the center of respective cells.  between an active node and a node in the same cell is the largest.

eHGAF with Triangle Cells
In eHGAF with triangle cells [7], the upper bound on the cell size is further improved. The cell size can be approximately 1.299R 2 at largest, which is 29.9% larger than that of standard eHGAF [6].
The main idea is to change the base-shape of each cell (and subcell) to triangle cells. Previously in GAF, HGAF, and eHGAF, the cells are of square-shape. Although partitioning with squares is regular and natural, a plane can be tiled with other regular polygons such as regular triangle and regular hexagon. In GAF, the cell size can be 1 4 3 In eHGAF, however, the upper bound on the cell size can be improved up to approximately 1.299 R 2 if we use triangle cells. See Figure 8. For simplify the exposition, we assume that r' is divisible by d and that the quotient is (3c + 1) for some positive integer c (this assumption assures that an active subcell can be located in the center (barycenter) of the triangle cell). Here, when d is infinitesimal, we can think that the active subcell can be seen as the point just positioned at the barycenter of the regular triangle. In such a case, it is easy to check that the conditions (Req.I) and (Req.II) become identical, and we have the following one inequality: Since r' is the height of a regular triangle, the maximum size of triangle-shaped cell is calculated as Hence, the following claim holds: Claim 4. [7] In eHGAF with triangle cells, the cell size is bounded above by

Cell Partition of 3D Space by Regular Polyhedra
In this section, we extend the sensor field to a 3 dimensional space. Here the sensor nodes are distributed over the 3 dimensional sensor field. The 3D sensor network recently attracts attention (e.g. [14][15] [16]). Applications of such 3D sensor field include underwater, atmospheric and space applications where height of the network can be significant and nodes are distributed over a 3D space. We examine the energy efficient way of partitioning the field into cells by using regular polyhedra. It is not difficult to confirm that the same strategy used in Section 3 is applicable to the problem here.
In what follows, we consider partitioning the 3D sensor field into cells for eHGAF protocol. Similarly to the argument in Section 3.4, we calculate the upper bound on the cell size with viewing the barycenter of regular polyhedron as the active subcell, assuming that the size of subcells is infinitesimal. To fill up a 3D space with regular polyhedra, we can chose tetra-, hexa-, octa-, dodeca-, and icosahedra.
To begin with, we examine the case of regular hexahedron (regular cube), for it is natural to use cubes for filling up the 3D space. Let r denote the length of an edge of a regular cube (cell). Then, the distance between the barycenter of a cube and that of adjacent cube is given by r, and the distance between the barycenter of a cube and a vertex of the cube is 3 2 ( ) r (see Figure 9). Then, for eHGAF with cubic cells, the requirements (Req.I) and (Req.II) are respectively taken on concrete formulas as follows: Since the volume of the cube is r 3 , the cell size can be R 3 at largest. Hence, the following holds: Claim 5. In eHGAF with hexahedral cells, the cell size is bounded above by R 3 . ■ Figure 9. The distance between the barycenter of a cube and that of adjacent cube, and the distance between the barycenter of a cube and a vertex of the cube.
Next, we examine the case of regular tetrahedron. Let r denote the length of an edge of a regular tetrahedron. Then, the distance between the barycenter of a tetrahedron and that of adjacent one is given by 1 6 ( ) r , and the distance between the barycenter of a tetrahedron and its vertex is 6 4 ( ) r . Then, for eHGAF with tetrahedral cells, the requirements (Req.I) and (Req.II) are respectively taken on concrete formulas as follows: Since the volume of the tetrahedron is 2 12 ( ) r 3 , the cell size can be 3R 3 at largest, and the following claim holds: Claim 6. In eHGAF with regular tetrahedral cells, the cell size is bounded above by Similarly, we can calculate upper bounds on the cell size for eHGAF with other polyhedra. The upper bound on the cell size for eHGAF with regular octahedral cells is approximately 0.866R 3 , that of dodecahedral cells is 0.694R 3 , and that of icosahedral cells is 0.627R 3 . ISSN 1943-3581 2009 Therefore, we can say that regular tetrahedral cells are preferable for filling up the 3D sensor field.

Theoretical Upper Bound on Cell Size
In this section, we study the upper bound on the cell size for eHGAF with 3D space. We show that the cell size is asymptotically bounded above by 4π 3 Here, we do not assume the shape of sensor field or that of cells. Please note that Δ is the volume of the overlapped region of those two spheres of radius R such that the distance between their centers is R.
To begin with, we introduce the following two propositions.

■
An example for Proposition 1 is a sensor field whose shape is a sphere with radius R. An example for Proposition 2 is the one whose shape is the union of two spheres such that the radius is R for both spheres and that the distance between their centers is R. Please note that Δ is the volume of the overlapped region of two such spheres.
By generalizing the above two propositions, we can prove the following lemma. Then, the following inequality holds: where |S| denotes the volume of S. ■ Lemma 2 can be easily checked by the following observation. Let C denote the cell that is chosen at (Step 1) in Lemma 2. Then, obviously, C ≤ 4π 3 ( ) R 3 holds. On the other hand, since C has to communicate with at least one cell C' among its adjacent cells, some part of C is covered by the active node of C'. So, it is not difficult to confirm that one cannot remove the region whose volume is more than 4π 3 ( ) R 3 − Δ at (Step 2) in Lemma 2, and thus Lemma 2 holds.
To prove Lemma 1, let P(k) denote the following proposition: If a sensor field consists of k cells, the size of entire sensor field can be k 4π 3 As for the proof of inductive case for Lemma 1, if we assume that P(k) holds and that P(k + 1) does not, then we can derive a contradiction by Lemma 2.
Hence, we can derive the following theorem.

Concluding Remarks
In this paper, we showed the following: 1. The cell size of eHGAF for 3D sensor field can be 3R 3 ≈ 1.732R 3 at largest if we use regular tetrahedral cells.
2. The theoretical upper bound on the cell size of eHGAF for 3D space is asymptotically Here, R is the communication range of each sensor node. Although 1.732R 3 is far less than 2.880R 3 , it is better to use tetrahedral cells because the cell size would be much smaller if we use other polyhedral cells (e.g., R 3 if we use hexahedral cells). Since the total number of active nodes in the entire sensor field inversely relate to the cell size, for eHGAF, we can say that the regular tetrahedral shape is the best for the cell shape if we partition the 3D sensor field with regular polyhedra.
Intuitively, there is a trade-off relation between the cell size and the degree of an active node. For example, if we use tetrahedral cells for partitioning a 3D space, each active node can communicate directly with those active nodes of 4 neighboring cells, which means that the communication range of an active node is overlapped with those of 4 neighboring active nodes. If we use hexahedral (cubic) cells, then the communication range of each active node is overlapped with those of 6 neighboring active nodes, and hence the cell size should be smaller because the portion of redundantly covered area becomes larger. Therefore, if we use a cell shape whereby the degree of an active node is smaller than 4, the cell size can be larger, though the connectivity metrics of the entire network gets worse. Table 2 summaries the estimated network lifetime for each cell shape. Here, as in [14], we assume that the network lifetime is proportional to the inverse of the number of active nodes in the entire network.