# Introduction ireless sensor networks constitute sensor nodes that are deployed over a topological area. Sensor nodes are independent, low resource devices possessing processing units, sensing devices, communication bandwidth, power resources and radio trans-receiver systems. Network life time, accurate data aggregation, and overhead reduction are desired characteristics of sensor network deployments. Network design is critical to construct efficient wireless sensor networks. Sensor networks are used for varied applications like unforeseen disaster relief [1] and [2], underwater sensor networks [3], monitoring activities [4], surveillance in military applications [5], medical monitoring systems [6] and many more. Network design is critical in sensor network deployments to achieve the desired goals [7]. Considering the varied application domain of sensor networks, it can be stated that the deployment methodology and the geographic deployment environments greatly vary. Wireless sensor network design, deployments of sensor nodes and analyzing the resources to be allocated to the sensor nodes is a major problem that exists. The shape of wireless sensor network deployments generally considered are usually in the shapes of a square or oval which is not the case in actual deployments [8]. Moreover researchers generally consider 2D topologies or 3D projections schemes to model the surface coverage which lead to inaccuracies and deviations from realistic environments [9]. In real word applications, sensor network deployments are complex 3D spaces. Generally researchers use a simple 2D ideal plane [10,11] or a 3D full space models [12,13] for the environment which are inadequate to achieve realistic results. A recent study conducted by Linghe Kong et al. [9] highlights the surface coverage problems for deployments of sensor networks in the idealistic world. In Ref. [9], the authors ascertain that the field of interest is neither 2D nor 3D but consists of complex surfaces, with the help of the Tungurahua volcano monitoring project [14] shown in Fig. 1. Furthermore, the authors in Ref. [9] define a coverage dead zone that exists in adopting a 2D surface coverage model described in Fig. 2 of this paper. Let us consider a set of seven sensor nodes termed Node A -Node G as shown in Fig. 3. The sensor nodes appear to be deployed in an elevated 3D terrain or a hill sort of a terrain. The 2D representation of the similar topology is presented in Fig. 4. While considering 2D topologies, nonexistent or impractical links are established as shown by a thick grey line in the figure. This error generally occurs in the network and the physical layer modeling. From the above mentioned examples, it is evident that the 2D models that currently exist may not be applicable to real world scenarios. In the research work presented, the authors propose to consider 3D complex surface models for modeling sensor network deployments. Skeleton extraction techniques have been extensively studied in the areas of image processing [15], medical image processing [16], computer graphics [17] and computer vision [18] and [19]. The use of skeleton extraction to represent the shape properties is well established. The skeleton extraction algorithms discussed above cannot be directly applied to wireless sensor network topologies as wireless sensor network topologies are discrete in nature and not continuous. Also the skeleton of wireless sensor networks depends on the network connectivity of the sensor nodes and not on the topological position alone. Wireless sensor networks are noisy by nature owing to the fact that the hop based approach is used to compute distances and not the Euclidean distance. The effect of noise tends to inaccurate skeleton extraction proved in Ref. [21]. In post skeleton node identification, the skeleton node connectivity also poses another challenge as the skeleton connectivity is physical layer based and not discrete. The use of skeleton extraction techniques to represent wireless sensor network topologies and thus enhance the performance is proposed by researchers in Ref. [20][21][22]. However, the application to the 3D topologies is still limited. The research work presented here considers sensor network deployments in 3D complex spaces. This paper introduces a skeleton extraction algorithm applicable to 3D wireless sensor network topologies where the coverage of the network is considered as a complex 3D function. In order to extract the skeleton, transmissions are initiated from each sensor node to all the other sensor nodes recursively and are modeled as transmission vectors. An energy utilization function is defined to identify the skeletal links. The skeleton is represented as a graph and the root node is computed using the frequency based weight assignment function. The skeleton nodes are extracted from the skeletal links. The skeleton graph construction is achieved by layered topological sets that represent decomposed clusters of the topology. The distance function is defined to organize the position of the skeleton nodes in the skeleton graph. The remaining manuscript is organized as follows. The literature is reviewed in section two of this paper. The proposed skeleton extraction algorithm is presented in the third section. The experimental study is described in the subsequent section. The conclusions of the research work are drawn in the last section of this paper. # II. # Literature Review The skeleton extraction algorithms proposed by researchers can be broadly classified into four categories namely thinning and boundary propagation, distance field-based, geometric based, and generalfield function based methods [18]. In the thinning and boundary based methods, the skeleton is represented as a thin line describing the topology. It is usually achieved by recursively shrinking of objects to a core thin line representing the topology [23]. To reduce the processing time which is a major drawback of the thinning and boundary based methods, researchers have also proposed parallel implementations of the thinning algorithms in 3D objects [24]. Most of the distance field based algorithms adopt a three step approach to extract the skeleton. The primary step constitutes in obtaining the ridge points of the object. Then a pruning methodology is applied followed by the connectivity phase to construct the skeleton. For connectivity, many algorithms like the shortest path ( D D D D D D D D ) technique [25,26], minimum spanning tree [27,28], LM path technique [29] or other geometric techniques are utilized. The advantage of distance field methods is that they are computationally lighter when compared to the other methods and is very effective in the case of tubular objects. The major drawback of the distance field algorithms is that on application to arbitrary objects, the skeleton extraction is not accurate. In the geometric based methods of skeleton extraction the objects are represented as sets of scatter points or structures of polygonal meshes. Voronoi diagram representations [30][31][32] is a popular example for geometric based methods for skeleton extraction. The polyhedral geometric method to represent 3D structures is discussed in Ref. [33,34]. The drawbacks of the geometric methods are that they are computationally more expensive when compared to the thinning and boundary based methods and they produce medial surfaces rather than the skeleton curve. In the general field generation based methods, varied functions are utilized to represents fields and these functions are utilized to generate skeleton curves. Potential field functions [35,36], visible repulsive force functions [37], electrostatic field functions [38], radial basis functions [39] are a few considered by researchers. The field generation algorithms are less sensitive to noise and produce better results when compared to the geometric methods. As the field generation functions are first or second order functions, they are computationally heavy to solve and are considered unstable. The skeleton extraction methodologies may not be applicable to wireless sensor network topologies directly, which is the purpose of the research work proposed here. Skeleton extraction in wireless sensor networks pose many challenges as discussed in the previous section of the paper. The migration of topology shapes to geometrical ones and the use of a dynamic medial axis model to present these geometric shapes are used for skeleton extraction in Ref. [40]. A medial axis based naming and routing protocol for wireless sensor networks is proposed in Ref. [21]. The methodology proposed in Ref. [21] consists of two protocols, namely, the medial axis construction protocol and the medial axis based routing protocol. In the medial axis construction protocol, the skeleton nodes are identified and the skeleton of the wireless sensor network topology is constructed. The medial axis based routing protocol achieves efficient load distribution during routing through the sensor networks due to the local decision capacities while routing. In Ref. [8], a connectivity based skeleton extraction algorithm applicable to wireless sensor network topologies is proposed. The coarse skeleton graph is extracted by boundary partitioning to identify the skeletal sensor nodes, generating the skeletal arcs, extending connectivity amongst the skeletal arcs. This coarse skeleton is finally refined to give the skeleton graph. The network topology. A distance transform based skeleton extraction algorithm for large scale wireless sensor networks is proposed in Ref. [22]. The algorithm proposed by Wenping Liu et al. [22] is more applicable to the practical applications as it does not require accurate or complete boundaries of sensor network topologies, exhibits lower communication overheads and is robust to noise. In Ref. [22], the coarse skeleton is generated by constructing the node map based distance transform of the sensor network; using the distance map the skeleton nodes are identified and the arcs are connected using a controlled folding scheme. The coarse skeleton is refined using the shortest path trees to construct the skeleton graph. The drawbacks of the skeleton extraction algorithms for wireless sensor networks discussed here is that the authors have considered the surface coverage in only 2D topologies and not the complex 3D topologies of wireless sensor networks that practically exist and proved in Ref. [9]. # a) Preliminary Notations Let us consider a 3?? wireless sensor topology ?? be represented as a graph ð?"¾ð?"¾ (?? , ??), where ?? represents the sensor node set and ?? is the wireless link set. The location wireless sensor node ?? ?? ? ?? described by Cartesian coordinates is represented by ?? ?? ?? = ??? ?? ?? , ?? ?? ?? , ?? ?? ?? ?(1) The skeleton or critical nodes to be identified in the sensor network topology ð?"¾ð?"¾ is defined by a set ?? and the remaining nodes are defined by the set ?? . ?? = ?? ? ??(2) Let the transmission radius of the sensor node be represented as ?? ?? and the sensing radius be represented as ?? ?? . As 3D topologies in complex spaces are considered, the coverage of the ?? sensor nodes [9] can be defined as © 2013 Global Journals Inc. (US) algorithm proposed in Ref. [8] accurately preserves the network topology and is robust to the noisy sensor A Novel Skeleton Extraction Algorithm for 3d Wireless Sensor Networks III. Proposed System -Skeleton Extraction Algorithm For 3d Wireless Sensor Networks ( D D D D D D D D ) Year 1 ? ?1 ? ??(?? ?? ?? ?? ? )(2?? 2 ?? 2 2??(???? 2 + ?? ?? ) + 2?????? ?? ? )((?? ?? + ?? ?? ?? + ???? 2 ) cos ?? ?? (?? ? ?? + ?? ?? ?? + ???? 2 ) ? )? ?? ? ??(?? ? ?? +?? ?? ??+???? 2 )(3) Where ?? ?? represents the area ?? ?? is the perimeter ?? is the sensor deployment intensity ?? ?? is the angle between ?? ?? and ?? ?? plane and ?? ? ?? is the area of the ?? plane projection of ?? ?? . The skeleton of the 3D wireless topology ?? can be considered to represent a graph ð?"¾ð?"¾ ?? (?? , ?? ?? ), where ð?"¾ð?"¾ ?? ? ð?"¾ð?"¾ and ?? ?? is a set of skeleton links amongst ?? ?? and ?? ?? . ?? ?? represents the set of the extreme sensor nodes in the topology ??and ?? ?? represents the sensor node which is common to all the skeleton links ?? ?? . In order to extract the skeleton of sensor networks generally a transmission based scheme is adopted [41] [42], in which each sensor node initiates a transmission to the other nodes and then the response messages or the route reply messages are used to derive ð?"¾ð?"¾ ?? and hence the authors of this paper adopt a similar mechanism. The major drawback of such mechanisms already adopted is that the network energy utilized associated with the transactions is established heuristically and are not applicable to 3D sensor networks. In order to overcome this drawback, the research work presented here does not consider the heuristic mechanism generally adopted and introduces a novel energy utilization function represented as ð?"¢ð?"¢(??) to compute the energy utilized during transmissions. The energy utilization function is derived in a manner such that if energy utilization of path between a set of sensor nodes is the least, then the link ?? ? ?? ?? . b) Energy Utilization Function ð?"¢ð?"¢(??) for Skeleton Extraction Let ?? be a skeleton node and ?? represent a nonskeleton node. Let ð?"£ð?"£(??) represent a frequency based weight assignment function that assigns skeleton nodes with higher values than the non-skeleton nodes. In other words, ð?"£ð?"£(??) > ð??"ð??"(??). Let's consider sensor node ?? ?????? at a location ?? ?? ?????? ? ?? ?? transmitting some data to the sensor node ?? ?????? located at ?? ?? ?????? ? ?? ?? . If the energy utilized in obtaining the optimal link route is defined as ?(?? ?????? ) = ?? â??" ?? ?? ?????? ?? ?????? ? ð?"¢ð?"¢ ???(??)????? ?? ?????? ?? ??????(4) Where ??(??) ? [0, ?) ? ?? ?? is the function that computes the optimal energy route. ð?"¢ð?"¢ represents the energy utilized The energy utilized in obtaining the optimal route can also put forth the least time interval for any active transmission from ?? ?????? to ?? ?????? when the physical radio layer transmission speed is ??, i.e., | ??( ?? ?????? ) | × ??( ?? ?????? ) = 1(5) The energy utilized ð?"¢ð?"¢ with respect to the radio layer transmission rate can be therefore defined as ??( ?? ?????? ) = 1 ð?"¢ð?"¢( ?? ?????? ) ?(6) The generalized form of the above equation can be defined as ??( ??) = 1 ð?"¢ð?"¢( ??) ?(6a) Where ??( ??) is the radio layer speed function defined as ??( ??) = ???ð?"£ð?"£(??)?(7) The skeleton of a 3D sensor network topology consists of a set of nodes ?? and a set of links connecting these skeleton nodes ?? ?? represented as a graph ð?"¾ð?"¾ ?? ? ð?"¾ð?"¾ . Let (?? ?? , ?? ?? ) represent a sensor node pair. The node pair ??? ?? , ?? ?? ? ? ?? if the energy utilization function is defined as ð?"¢ð?"¢( ??) = ?? ???ð?"£ð?"£(??)(8) where ?? > 0 and is defined as ?? > (1 ?? ? ) ln ??(?? 2 ?? + ?? 2 ?? + ?? 2 ??) ?? â??" (????, ????, ????) ? ? Where ???? , ???? , ???? is the spacing, ?? â??" is the minimum function and ?? is the minimum value of the absolute difference between the neighboring sensor nodes. # c) ?? ?? point computation In the research work presented here, the authors adopt the contour or snake model introduced in Ref. [43] to obtain the skeleton nodes of the 3D wireless sensor network topology ?? . The snake or vector of the tran-smissions that propagate through ?? can be defined as ?? ?? (??) = [ ?? ?? (??) ?? ?? (??) ?? ?? (??) ] ??(9) The snake ?? ?? (??) minimizes the energy function defined as Eq. ( 10), yet maintaining topology features where ð??"ð??" ?? (??) is the edge map derived, ?? = (??, ??, ??) and the parameter of regularization is represented as ?? . ? ?? (?? ?? ) = ?(?? ( |??? ?? (??)| 2 + |??? ?? (??)| 2 + |??? ?? (??)| 2 ) ) + ( |ð??"ð??" ?? (??)| 2 |?? ?? (??) ? ?ð??"ð??" ?? (??)| 2 ????)(10) The energy function ? ?? of the snake of the ?? ?? is dominated by the partial derivatives of or the primary term in the case where ?ð??"ð??" ?? (??) is small. In the case where ?ð??"ð??" ?? (??) is large, ? ?? (?? ?? ) is greatly dominated by the second term and the energy involved can be minimized by assuming ?? ?? = ?ð??"ð??" ?? (??). The use of generalized diffusion equations [44,45] is considered to find the solution of the snake ?? ?? (??) . The ?? ?? (??) of the ?? ??? node is computed from the remaining node points in the topology ?? by utilizing a diffusion based procedure and these computations converge to a set of skeleton links ?? ? ?? ?? . The diffusion based procedure is slow by nature and converges towards the center of the topology and in order to compute ð?"¾ð?"¾ ?? , we define the frequency based weight assignment ð?"£ð?"£(??) as follows where ?? ? is the max function and ?? â??" is the min function. ð?"£ð?"£(??) = 1 ? ((|?? ?? (??)| ? ?? â??" |?? ?? | ) (?? ? |?? ?? | ? ?? â??" |?? ?? |) ? ) ð??"ð??"(11) The parameter ð??"ð??" represents the strength and is assigned values between 0 and 1 . The parameter ð??"ð??" is assigned empirically. The weight assignment function defined above enables faster computations and convergence. The ?? ?? point is a skeleton node that belongs to all the links defined by ?? ?? and can be obtained based on the frequency based weight assignment function ð?"£ð?"£(??) . The sensor node with the maximum value of ð?"£ð?"£(??) is set to be ?? ?? . The computation of ?? ?? is iteratively achieved and if another node whose weight is higher is obtained, then ?? ?? is a new sensor node. The computation of ?? ?? can be defined as ?? ?? = ? ??? ? ?ð?"£ð?"£(??)?? ??=?? ??=0(12) d) Skeleton links ?? ?? identification and skeleton node set ?? construction The skeleton links ?? ?? is a set of skeleton links ?? ?? derived from the weight assignment function ð?"£ð?"£(??). To obtain ?? ?? , the singular skeleton links ?? ?? need to be obtained. Let us consider a skeleton node pair represented by (?? ?? , ?? ?? ). Let the sensor node ?? ?? initiate a transmission signal to sensor node ?? ?? . Let ?? ?? represent the skeleton link that exist between the skeleton node pair (?? ?? , ?? ?? ) . The skeleton link ?? ?? is the minimum energy utilized link between the nodes ?? ?? and ?? ?? based on equation (8). Let ?? be the time taken for the transmission from ?? ?? to ?? ?? . Tracking route reply from ?? ?? to ?? ?? would enable the identification of ?? ?? and this process is defined as ?? ??+1 = ?? ?? ? ?(???? |????| ? ) , ??(0) = ?? ??(13) where represents the error step. Using ordinary differential equations, the above equation can be represented as ???? ???? ? = ?(???? |????| ? ) , ??(0) = ?? ??(14) Where ?? represents the route reply path from ?? ?? to ?? ?? . Adopting the Second order Range-Kutta theorem where the stages ð?"?ð?"? 1 = ð??"ð??"(?? ?? ) , ð?"?ð?"? 2 = ð??"ð??"(?? ?? + (? 2 ? )ð?"?ð?"? 1 ) and ð??"ð??"(?? ?? ) = ?(????(?? ?? ) |????(?? ?? )| ? ), the above equation can be represented as ?? ??+1 = ?? ?? + (? × ð?"?ð?"? 2 )(15) Having obtained a single skeleton link ?? ?? the process is iteratively repeated to obtain the entire skeleton links ?? ?? for all the remaining sensor nodes ?? ? ?? | ?? ? ?? ?? . The iterative process exhibits multiple overlapping links which can be eliminated by tracking the route reply paths. The sensor nodes that exist on the skeleton links are the critical or skeleton nodes and are represented by the set ?? . Year sensor network topology ?? into topological clusters that represent the prominent 3D shape information of the topology. The skeleton sensor node ?? ?? is considered as the root node of the skeleton graph ð?"¾ð?"¾ ?? . Each topological cluster consists of a set of regular sensor nodes and a skeleton node. In other terms, each skeleton node is used to represent a cluster and the skeleton links form the boundary of that cluster. The cluster is identified in terms of the relative distance from the skeleton node ?? ?? . The skeleton graph ð?"¾ð?"¾ ?? is constructed from the layered topological sets, wherein the skeleton nodes represent a cluster and the skeleton links represent the boundaries. On constructing the ð?"¾ð?"¾ ?? , it is observed that the leaf nodes of the graph can be used to identify the topological information of the sensor network ?? . The construction of the layered topological clusters is critical to obtain the skeleton graph ð?"¾ð?"¾ ?? without the loss of topological information. Let ??(??) represent the distance function. A transmission with a speed parameter ?? (?? > 0) is propagated from the skeleton node ?? ?? that can be represented as a partial differential equation. The solution of the partial differential equation results in a novel distance function represented as ?? ? (??) . The speed of the transmission is defined as ??(??) = ?? ?????(??)(16) To derive the function ??(??) , it is required to define a parameter ?? . Let us consider a skeleton link ?? ?? ? ?? ?? that exists between two skeleton node pair(?? ?? , ?? ?? ). Let there exist ?? regular sensor nodes having (?? ? 1) links that exist between the skeleton node pair (?? ?? , ?? ?? ) . Let the skeleton transmit a packet from ?? ?? to ?? ?? with a radio speed represented as ?? . If ?? ?? ?? represents the time taken to transmit the packets amongst two adjacent sensor nodes, then the time taken to reach the destination can be defined as ?? = ? ?? ?? ?? ???1 ??=1 (17) And ?? ?? ?? can be defined as ?? ?? ?? = ??(?? ???1 , ?? ?? ) ??(?? ?? ) ?(18) Let us consider time ?? ? greater than ?? ?? ?? , i.e., (?? ? > ?? ?? ?? ) and can define ?? ? as ?? ? ? ??(?? ???1 , ?? ?? ) ?? ??ð?"£ð?"£(?? ?? ) ? (19) Rearranging the terms of equation ( 19), ?? can be represented as ?? ? (1 ð?"£ð?"£(?? ?? ) ? ) × (ln(??(?? ???1 , ?? ?? ) ?? ? ? ))(20) Considering ð?"£ð?"£(?? ?? ) = ð?"£ð?"£ ?? ? and ??(?? ???1 , ?? ?? ) = ?? â??" (????, ????, ????) , the value of ?? would result in the worst case scenario. Let ?? ? represent the critical value of ?? and can be defined as ?? ? ? (1 ð?"£ð?"£ ?? ? ? ) × (ln(?? â??" (????, ????, ????) ?? ? ? ))(21) where 0 < ?? ? < ?? â??" (????, ????, ????) and if ?? ? = ?? â??" (????, ????, ????) then ?? ? = 0 , which means that the transmission around the ?? ?? skeleton is uniform and if ?? ? = 0 , the layered topological clusters formed are not accurate. To avoid such scenarios, the authors consider 0 < ?? ? < ?? â??" (????, ????, ????). The time discretized version of the function ?? ? (??) is defined as ?? ? (??) ??????? = [?? ? (??)] (22) Rapid discretization is not considered as [?? ? (??)] would not result in accurate layered topological cluster formulations. All the skeleton nodes having the same ?? ? (??) ??????? form a cluster provided they are not adjacent to one another. In ð?"¾ð?"¾ ?? , the root node is the topological cluster containing the skeleton node ?? ?? followed by the clusters exhibiting increasing values of ?? ? (??) ???????? . Two skeleton nodes in the ð?"¾ð?"¾ ?? are said to be connected if there exists a skeleton link amongst them and, the two topological clusters are said to be adjacent if the ancestor skeleton node is common and there exists a skeleton link amongst them. The identification of the critical sensor nodes or skeleton nodes in the 3D topology ?? is represented as a skeleton graph ð?"¾ð?"¾ ?? (?? , ?? ?? ) consisting of skeleton nodes and skeletal links, which is presented in this section of the paper. The experimental study of the proposed skeleton extraction on varied 3D topologies is discussed in the subsequent section of the paper. # IV. # Experimental Study In this section of the paper, the experimental study and the 3D topologies datasets used to evaluate the performance is discussed. The 3D sensor network ( D D D D D D D D ) Year 013 2 E viewer is developed using the Windows Presentation Foundation model. The algorithms are developed using C#.Net on the Microsoft Visual Studio platform. The 3D datasets are obtained from the AIM@SHAPE Shape Repository [46]. The points corresponding to the 3D data sets were considered as sensors. The radio ranges of the sensor nodes were varied to achieve complete coverage. The Energy efficient TDMA MAC [47] is considered for communication in the sensor network topology. The routing protocol is adopted from the paper of Ref. [48]. The experimental analysis presented here discusses the evaluation conducted on a set of five topologies shown in Table 1. The experimental study presented here consists of 2 sections, namely, skeleton graph G S a) ð?"¾ð?"¾ ?? skeleton graph construction of wireless sensor network topologies considered A set of random sensor nodes are deployed on the five topologies considered. The radio range of the sensor nodes is varied to achieve complete coverage over the entire terrain. Homogenous network deployments are considered to construct the skeleton graph ð?"¾ð?"¾ ?? . To construct the skeleton graph, first we need to identify the skeletal links ?? ?? and the skeleton node set ?? . The skeletal link set consists of a number of skeleton links ?? ? ?? ?? . To identify each skeletal link ?? ? ?? ?? , each node is considered as the source and all the other nodes are considered as the destination. The energy utilized ð?"¢ð?"¢( ??) is monitored and the weights are assigned in accordance to the frequency based weight assignment function ð?"£ð?"£(??) . The sensor node with the maximum weight ?? ? ?ð?"£ð?"£(??)? is considered as the skeleton node ?? ?? . The route reply tracking on the skeleton links and the minimum energy utilized links ?? ? ?? ?? enables to construct the skeleton node set ?? . Having obtained the skeleton nodes ?? and the skeletal links ?? ?? , the skeleton graph needs to be constructed based on the layered topological sets. To construct layered topological sets, the sensor network topology is decomposed into clusters such that each cluster contains only one skeleton node. The distance function ?? ? (??) ??????? is computed to obtain the position and location of the cluster represented by the skeleton node in ð?"¾ð?"¾ ?? . The skeleton nodes are rearranged to form the skeleton graph ð?"¾ð?"¾ ?? centered at the skeleton node ?? ?? . The experimental study is conducted on varied topology sizes described in Table 1. The results obtained are shown in Table 2. The table shows the terrain views obtained from Ref. [46], sensor deployed, the wireless sensor network topology, skeleton nodes identified and the skeleton extracted. # b) sensor network performance analysis with and without skeleton node considerations To study the effect of the critical nodes or skeleton nodes, two scenarios are considered in this discussion, namely, "BALANCED" and "PROPOSED SYSTEM" scenario. In the "BALANCED" scheme, a homogeneous sensor network deployment is considered, i.e., all the sensors are assigned with uniform initial power. In the "PROPOSED SYSTEM" scenario, the skeleton nodes identified are assigned an additional energy of about 35% when compared to the other nodes. The networks were simulated and the results were analyzed. The analysis was carried out to study the effect in terms of the network throughput, network overheads and network lifetime. The results obtained for the Genoa Gulf [49] topology are shown in Figure 5, 6 and 7. The average throughput for the balanced scheme was found to be around 84.9% and for the proposed scheme, it was around 92.7%. The network overheads measured in terms of the energy utilized was reduced by about 44.3%. The efficiency in terms of the network life time is clearly seen in Figure 7. The average throughput of about 88.6% was achieved by the "PROPOSED SYSTEM" when compared to the average throughput of about 80.7% achieved by the "BALANCED" scheme. An average network overhead reduction of about 31.1% was achieved by the "PROPOSED SCHEME". The network lifetime of the sensor network topology is considerably higher for the "PROPOSED SYSTEM" as additional power is assigned to the skeleton nodes identified. From Figure 5-19, it can be concluded that the "PROPOSED SYSTEM", wherein additional power resources is provided to skeleton nodes identified achieved better network performance in terms of network throughput, network lifetime and overhead reduction enhancing the efficiency of the wireless sensor network deployments. V . # Conclusion Network design is critical to construct reliable wireless sensor networks. The coverage of 3D sensor networks is complex in nature and the 2D topologies or the 3D projection schemes are not applicable to achieve realistic results. Skeleton extraction and its significance applicable to areas as medical image processing, computer vision, computer graphics and many more are well understood. These skeleton extraction mechanisms are not applicable to complex 3D wireless sensor networks. Limited work has been carried out to extract the skeleton of 3D wireless sensor networks. This paper proposes a novel skeleton extraction algorithm applicable to 3D wireless sensor network topologies. The skeleton is represented as a skeleton graph G S (S, L S ). To construct the skeleton graph each sensor node initiates transmission throughout the network and the energy utilized is monitored. A novel energy utilization function is e (n) is defined to identify the skeletal links L S . The root node skeleton graph is represented as S C and is computed based on the frequency based weight assignment function f (n). The skeleton nodes are extracted from the skeletal links and layered topological sets are constructed by adopting a topological clustering mechanism. Each cluster considered consists of one skeleton node and is a part of the skeleton graph. The distance function is computed for each cluster to determine its position in the skeleton node from the root node and the graph G S 1![Figure 1 : Volcano monitoring Project from Harvard Sensor Networks Lab [14]](image-2.png "Figure 1 :") 2![Figure 2 : Coverage Problem Dead Zone that occurswhen 2D Plane Solutions are adopted to 3D surfaces[9] ](image-3.png "Figure 2 :") 34![Figure 3 : A seven sensor node topology in 3D surface](image-4.png "Figure 3 :Figure 4 :") ![e) ð?"¾ð?"¾ ?? skeleton graph constructionHaving obtained the skeleton links ?? ?? and the skeleton node set ?? , we shall now discuss the methodology adopted in constructing the skeleton graph ð?"¾ð?"¾ ?? .The skeleton graph is obtained by© 2013 Global Journals Inc. (US)constructing layered topological sets. The layered topological sets are constructed by decomposing the A Novel Skeleton Extraction Algorithm for 3d Wireless Sensor NetworksGlobal Journal of Computer Science and TechnologyVolume XIII Issue XVI Version I](image-5.png "") 5![Figure 5 : Network Throughput Analysis for GENOA GULF](image-6.png "EAFigure 5 :") 211![Figure 11 : Network Throughput Analysis for MATTERHORN](image-7.png "2 EFigure 11 :") 12131516171819![Figure 12 : Network Overhead Analysis for MATTERHORN](image-8.png "Figure 12 :Figure 13 :Figure 15 :Figure 16 :Figure 17 :Figure 18 :Figure 19 :") ![Novel Skeleton Extraction Algorithm for 3d Wireless Sensor Networks is constructed. The skeleton extraction algorithm is validated on a set of varied 3D topologies. Provisioning of additional resources to the skeleton nodes enhances the sensor network performance by 20% and is proved through the experimental study. The results obtained @SHAPE Shape Repository (Sept 18 2013), "Model name: Torus ,ID: 43" Available : http://shapes.aim-at-shape.net/view.php?id=43 51. AIM@SHAPE Shape Repository (Sept 18 2013), "Model name: Matterhorn, ID: 779" Available:http:// shapes.aim-atshape.net/view.php? id=779 A Novel Skeleton Extraction Algorithm for 3d Wireless Sensor Networks 52. AIM@SHAPE Shape Repository (Sept 18 2013), "Model name: Naples gulf ,ID: 825" Available:http://shapes.aim-at-shape.net/view.php? id=825 © 2013 Global Journals Inc. (US) Global Journal of Computer Science and Technology Volume XIII Issue XVI Version I ://shapes.aim-at-shape.net/view.php? id=879 Global Journal of Computer Science and Technology Volume XIII Issue XVI Version I](image-9.png "A") ?? ?? ?????? ?? ??????represents the minimum hop route from sensor node ?? ?????? to sensor node ?? ?????? 1NoTopology NameCoverage AreaNo Of Sensor NodesNo Of Skeleton NodesNo Of LinksRadio Range1Genoa Gulf [49]71910 X 56700 X 1617.772675637447578.92Torus [50]1 X .32 X.9550284000.43Matterhorn [51]46080 X 46080 X 3524.31130369107275.84Naples Gulf [52]5120 X 5120 X 134715357267210805West Sicily [53]177570 X 112950 X1130.5915439285218937.9 © 2013 Global Journals Inc. (US) Global Journals Inc. (US) ## Acknowledgements prove improvements in network throughput, network lifetime and achieve reduction in the network overheads. The authors of this paper would like to thank Mr Ashutosh Kumar and Mr Kashyap Dhruve for their valuable suggestion and support. * TiaGao * TMassey LSelavo DCrawford Borrong Chen * The Advanced Health and Disaster Aid Network: A Light-Weight Wireless Medical System for Triage KLorincz VShnayder LHauenstein FDabiri JJeng AChanmugam DWhite MSarrafzadeh MWelsh 10.1109/TBCAS.2007.910901 Biomedical Circuits and Systems 1 3 Sept. 2007 IEEE Transactions on * Sendrom: Sensor Networks for Disaster Relief Operations Management ECayirci TCoplu Wireless Networks 13 3 2007 * Underwater Acoustic Sensor Networks: Research Challenges IFAkyildiz DPompili TMelodia Ad Hoc Networks 3 Mar. 2005 * Habitat Monitoring with Sensor Networks RSzewczyk EOsterweil JPolastre MHamilton AMainwaring DEstrin Comm. ACM 47 6 2004 * Battlefield Awareness via Synergistic SAR and MTI Exploitation MFennell RWishner IEEE Aerospace and Electronic Systems Magazine 13 2 Feb. 1998 * Monitoring Motor Fluctuations in Patients With Parkinson's Disease Using Wearable Sensors SPatel KLorincz RHughes NHuggins JGrowdon DStandaert MAkay JDy MWelsh PBonato 10.1109/TITB.2009.2033471 Information Technology in Biomedicine 13 6 Nov. 2009 IEEE Transactions * The design space of wireless sensor networks KRomer FMattern 10.1109/MWC.2004.1368897 Wireless Communications 11 6 Dec. 2004 IEEE * HongboJiang ; Wenping Liu; DanWang; Chen Tian * Connectivity-Based Skeleton Extraction in Wireless Sensor Networks XiangBai ; Xue Liu; Ying Wu; WenyuLiu 10.1109/TPDS.2009.109 IEEE Transactions 21 5 May 2010 Parallel and Distributed Systems * 10.1109/TPDS.2013.35 * Barrier coverage with wireless sensors SKumar THLai AArora ACM MobiCom New York, NY, USA 2005 * Complete optimal deployment patterns for fullcoverage and k-connectivity (k?6) wireless sensor networks XBai DXuan ZYun THLai WJia ACM MobiHoc New York, NY, USA 2008 * A coverage algorithm in 3d wireless sensor networks MWatfa SCommuri IEEE PerCom 6 Jan. 2006 * The coverage problem in three-dimensional wireless sensor networks C.-FHuang Y.-CTseng L.-CLo IEEE GLOBECOM 5 * Continuous Skeleton Computation by Voronoi Diagram JWBrandt VRAlgazi CVGIP: Image Understanding 55 3 1992 * Initialization, Noise, Singularities and Scale in Height Ridge Traversal for Tubular Object Centerline Extraction SRAylward EBullitt IEEE Trans. Medical Imaging 21 2 2002 * Animating Volumetric Models NGagvani DSilver Graphical Models 63 6 2001 * Curve-Skeleton Properties, Applications, and Algorithms NDCornea DSilver PMin 10.1109/TVCG.2007.1002 IEEE Transactions on 13 3 May-June 2007 Visualization and Computer Graphics * Curve-Skeleton Applications NDCornea DSilver PMin Proc. IEEE Visualization Conf. (VIS '05) IEEE Visualization Conf. (VIS '05) 2005 * HongboJiang ; Wenping Liu; DanWang; Chen Tian * Connectivity-Based Skeleton Extraction in Wireless Sensor Networks XiangBai ; Xue Liu; Ying Wu; WenyuLiu 10.1109/TPDS.2009.109 IEEE Transactions 21 5 May 2010 Parallel and Distributed Systems * MAP: Medial Axis Based Geometric Routing in Sensor Networks JBruck JGao AAJiang Proc. ACM MobiCom ACM MobiCom 2005 * WenpingLiu * HongboJiang; Xiang Bai Guang Tan * Distance Transform-Based Skeleton Extraction and Its Applications in Sensor Networks ChonggangWang ; Wenyu Liu; KechaoCai 10.1109/TPDS.2012.300 IEEE Transactions on 24 9 Sept. 2013 Parallel and Distributed Systems * Surface Coverage in Sensor Networks LingheKong MingchenZhao Xiao-YangLiu JialiangLu Continuum and Its Applications in Industry (VRCAI '08) IEEE Computer Society 25 Feb. 2013. 2008 IEEE computer Society Digital Library * Volume Decomposition and Hierarchical Skeletonization XZhang JLiu ZLi MJaeger Proc. ACM SIGGRAPH Int'l Conf. Virtual-Reality ACM SIGGRAPH Int'l Conf. Virtual-Reality * A Note on 'A Fully Parallel 3D Thinning Algorithm and Its Applications TWang ABasu Pattern Recognition Letters 28 4 2007 * Automated Generation of Control Skeletons for Use in Animation LWade REParent The Visual Computer 18 2 2002 * Reliable Path for Virtual Endoscopy: Ensuring Complete Examination of Human Organs THe LHong DChen ZLiang IEEE Trans. Visualization and Computer Graphics 7 4 Oct.-Dec. 2001 * Skeleton Based Shape Matching and Retrieval HSundar DSilver NGagvani SDickinson Proc. Shape Modeling Int'l Conf Shape Modeling Int'l Conf 2003 * Distance-Field Based Skeletons for Virtual Navigation MWan FDachille AKaufman Proc. IEEE Visualization Conf IEEE Visualization Conf 2001 * Penalized-Distance Volumetric Skeleton Algorithm IBitter AEKaufman MSato IEEE Trans. Visualization and Computer Graphics 7 3 July-Sept. 2001 * Continuous Skeleton Computation by Voronoi Diagram JWBrandt VRAlazi CVGIP: Image Understanding 55 1992 * Voronoi Skeletons: Theory andApplications ROgniewicz MIlg Proc. Conf. Computer Vision and Pattern Recognition Conf. Computer Vision and Pattern Recognition 1992 63 * Hierarchic Voronoi Skeletons ROgniewicz OKu¨ Pattern Recognition 28 3 1995 * Efficient and Robust Computation of an Approximated Medial Axis YYang OBrock RNMoll Proc. Solid Modeling and Applications Conf Solid Modeling and Applications Conf 2004 * Exact Computation of the Medial Axis of a Polyhedron TCulver JKeyser DManocha Computer Aided Geometric Design 21 1 2004 * Shape Representation Using a Generalized Potential Field Model NAhuja JChuang IEEE Trans. Pattern Analysis and Machine Intelligence 19 2 Feb. 1997 * Skeletonization of Three-Dimensional Object Using Generalized Potential Field JChuang CTsai M.-CKo IEEE Trans. Pattern Analysis and Machine Intelligence 22 11 Nov. 2000 * Automatic Animation Skeleton Construction Using Repulsive Force Field PLiu FWu WMa RLiang MOuhyoung Proc. 11th Pacific Conf. Computer Graphics and Applications 11th Pacific Conf. Computer Graphics and Applications 2003 * Skeleton Extraction of 3D Objects with Radial Basis Functions TGrigorishin YHYang ;WMa FWu MOuhyoung Proc. IEEE Int'l Conf. Shape Modeling and Applications IEEE Int'l Conf. Shape Modeling and Applications 1998. 2003 1 Skeletonization: An Electrostatic Field-Based Approach * A Dynamic Medial Axis Model for Sensor Networks LLin HLee Proc. IEEE Int'l Conf. Embedded and Real-Time Computing Systems and Applications IEEE Int'l Conf. Embedded and Real-Time Computing Systems and Applications Aug. 2007 * Robust centerline extraction framework using level sets MSHassouna AAFarag 10.1109/CVPR.2005.306 IEEE Computer Society Conference on 1 2005. 2005. 2005 Computer Vision and Pattern Recognition * Fast extraction of minimal paths in 3D images and applications to virtual endoscopy ThomasDeschamps LaurentDCohen 10.1016/S1361-8415(01)00046-9 Medical image analysis 1 December 2001 * ChenyangXu * Gradient vector flow: a new external force for snakes JLPrince 10.1109/CVPR.1997.609299 Proceedings. 1997 IEEE Computer Society Conference on 1997 IEEE Computer Society Conference on 1997 Computer Vision and Pattern Recognition * Numerical Analysis of Partial Differential Equations AHCharles TAPorsching 1990 Prentice Hall Engelwood Cliffs, NJ * Snakes, shapes, and gradient vector flow CXu JLPrince JHU-ECE TR96-15 Oct. 1996 The Johns Hopkins University Technical Report * AIM@SHAPE shape repository * Bai; Yu-GuiRong Gang Qu * YangGuo * An Energy-Efficient TDMA MAC for Wireless Sensor Networks Bao-HuaZhao 10.1109/APSCC.2007.25 The 2nd IEEE Dec. 2007 * Energy efficient routing in ad hoc disaster recovery networks GZussman ASegall 10.1109/INFCOM.2003.1208718 INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications IEEE Societies April 2003 1 * Model Name Genoa gulf Aim@shape Shape Repository ID: 789 Sept 18 2013