## 1 Introduction  
With both its computational complexity and storage space bounded by a small constant, greedy routing is known for its scalability to large networks with stringent resource constraints on individual nodes. Under most greedy routing algorithms, a node makes its routing decision by standard distance calculation based on a small set of local coordinates only. Such a salient property is imperatively needed in emerging 3D sensor networks [1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12], where the problem in routing scalability is greatly exacerbated in comparison with its 2D counterpart, due to dramatically increased sensor nodes in order to cover a 3D space. The conventional greedy routing algorithms are node-based [13; 14]. More specifically, a node always forwards a packet to one of its neighbors, which is the closest to the destination of the packet. However, such greedy forwarding is not always achievable. A node is called a local minimum if it is not the destination, but closer to the destination than all of its neighbors. Clearly, greedy routing fails at the local minimum. Such local minimums may appear at either boundary or internal nodes (as highlighted in red in Figure 1b). A node on a boundary, especially a concave boundary, usually becomes a local minimum when the source and destination nodes are located on two sides of the boundary. Although it seems anti-intuitive, an internal node can be a local minimum, too, due to local concavity under random deployment of sensor nodes. Various approaches have been developed to address the problem of local minimum in 2D networks, with primary focus on boundaries. For example, face routing and its alternatives and enhancements [13; 14; 15; 16; 17; 18; 19; 20] exploit the fact that a concave void in a 2D planar network is a face with a simple line boundary. Thus, when a packet reaches a local minimum on a boundary, it employs a local deterministic algorithm to search the boundary in either the clockwise or counter-clockwise direction, as shown in Figure 2a, until greedy forwarding is achievable. In a 3D network, however, a void is no longer a face. Its boundary becomes a surface, yielding an arbitrarily large number of possible paths to be explored (see Figure 2b) and, thus, rendering face routing infeasible. On the other hand, greedy embedding [21; 22; 23; 24; 25; 26; 27] provides theoretically sound solutions to ensure the success of greedy routing. Unfortunately, none of the greedy embedding algorithms in the literature can be extended from 2D to 3D general networks. The challenge of greedy routing in 3D networks is further revealed in [28], which proves that there does not exist a deterministic algorithm that can guarantee delivery based on local information only in 3D networks. In view of the above challenges, several approaches have been proposed for recovery from local minimums in 3D networks. First, mapping and projection are introduced to reduce routing complexity in a 3D space. For example, a 3D network is projected to a 2D plane in [4; 5] in order to apply face routing. However, face routing on the projected plane does not ensure that a packet moves out of a void in the original 3D network. A different projection scheme is proposed in [7] for load balancing, which does not guarantee delivery either. Second, guaranteed delivery can be achieved at the cost of more(non-constant-bounded) storage space. For example, a convex hull-based tree structure is introduced in GDSTR-3D [8]. A packet is greedily forwarded to its destination. If a local minimum is reached, GDSTR-3D switches to forwarding the packet along the edges of a spanning tree, guiding the packet to escape from the local minimum. GDSTR-3D offers deterministic routing. However, each node must maintain a set of convex hulls and, thus, requires a storage space proportional to network size, and some nodes (such as the roots of trees) are heavily loaded (see Figure 3). Finally, local searching may be employed to jump out of a local minimum.