Abstract:
An un-triangulated hole counting method is described in the invention to evaluate the performance of sensing coverage or wireless communication coverage in a randomly and uniformly deployed sensor network or wireless network without knowing the network topology. This method calculates the expected number of un-triangulated holes, which is the un-triangulated area size in the target area divided by mean un-triangulated hole size, given node density and target area size of the network. The present invention thus provides an aid for controlling the degree of coverage in node deployment for randomly deployed sensor networks. It can also aid to choose a suitable common transmission range for all nodes in a wireless network to provide acceptable wireless radio coverage. A position inside a target area is said to be un-triangulated if it is not enclosed by any triangle formed by connectivity links between three mutually connected nodes. An un-triangulated hole is an area enclosed by a polygon formed by links between nodes where each position of the area is un-triangulated.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    Not applicable 
       STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT 
       [0002]    Not applicable 
       REFERENCE TO SEQUENCE LISTING, A TABLE, OR A COMPUTER PROGRAM LISTING COMPACT DISC APPENDIX 
       [0003]    Not applicable 
       BACKGROUND OF THE INVENTION 
       [0004]    1. Field of the Invention 
         [0005]    The present invention relates to coverage evaluation and un-triangulated coverage hole counting in wireless sensor networks, and radio transmission range optimization in wireless networks. 
         [0006]    2. Description of the Related Art 
         [0007]    The probability of triangulation is closely related to the probability of existence of un-triangulated coverage (or routing) holes and the probability of coverage. Therefore the probabilistic analysis of triangulation is a fundamental topology control tool to maintain expected quality of monitoring and network connectivity. If the node density and target area size of a random deployed sensor network are given, the probabilistic analysis is helpful to select the appropriate transmission range for network connectivity and save power at the same time. Hence this is a statistical tool for topology control to achieve efficient power management and longest network lifetime providing acceptable sensing monitoring integrity and accuracy, as well as connectivity. 
         [0008]    A few existing works provided mathematical methods for the calculation of coverage probability. Assume nodes are randomly deployed in the target sensing area according to a two-dimensional Poisson process, with node density λ. Node density λ is the mean number of nodes lying inside a unit disk sensing area, assuming uniform sensing area πR 2 =1, and hence the sensing range R=1/√π. 
         [0009]    P. Hall introduced a method to calculate the probability of coverage (P c ) for any single point not located near the boundary of the area S, which is defined by the probability that at least 1 (k≧1) node lies inside the circle with unit area centred there. P c  is defined in terms of the Poisson distribution with node density λ: 
         [0000]    
       
         
           
             
               P 
               c 
             
             = 
             
               
                 
                   ∑ 
                   
                     k 
                     = 
                     1 
                   
                   ∞ 
                 
                  
                 
                   
                     
                       λ 
                       k 
                     
                      
                     
                        
                       
                         - 
                         λ 
                       
                     
                   
                   
                     k 
                     ! 
                   
                 
               
               = 
               
                 1 
                 - 
                 
                    
                   
                     - 
                     λ 
                   
                 
               
             
           
         
       
     
       BRIEF SUMMARY OF THE INVENTION 
       [0010]    The main objective of the invention is to calculate the expected number of un-triangulated holes in a randomly and uniformly deployed sensor network, given node density and target area size, without knowing the network topology. This method can guide the sensor node deployment in large scalar sensor networks when nodes are deployed randomly from such as a helicopter or a ship to a wide area, in order to achieve acceptable sensing coverage using minimum number of sensor nodes. 
         [0011]    The second objective is to optimize the radio transmission range in a randomly deployed wireless networks to achieve acceptable networking connectivity and better power saving. The invention calculates the expected number of routing holes in a wireless network given number of wireless nodes, uniform transmission range and target area size. The method can be used to determine optimal transmission range for all wireless nodes in the network to achieve acceptable networking connectivity with limited number of routing holes. 
         [0012]    Firstly, the invention calculates the expected un-triangulated area size, given node density and target area size. Node density is the mean number of node inside a unit sensing area covered by a sensor node&#39;s sensing range, or the wireless communication area covered by a node&#39;s half transmission range. 
         [0013]    Then the invention calculates the mean un-triangulated hole size, which is the mean un-triangulated area inside a hole. 
         [0014]    Finally, the expected number of un-triangulated hole is calculated, which is the expected un-triangulated area size inside the target area, divided by the mean un-triangulated hole size. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0015]    The present invention will become more understandable from the detailed description given herein below and the accompanying drawings which are given by way of illustration only, and thus are not limitative of the present invention. In the following figures, assume each node has sensing area defined by a circle with radius R, and a ‘link’ is said to exist between any two nodes which are no less than 2R units to each other. 
           [0016]      FIG. 1 . shows a position A is triangulated by three nodes {N 0  N 1  N 2 }, where nodes {N 0  N 1  N 2 } are located inside the disk with radius 2R centred by A. Nodes {N 0  N 1  N 2 } are mutually connected within distance less than 2R to each other to form a triangle enclosing A. 
           [0017]      FIG. 2 . shows the areas S N1  (in which node N 1  must lie) when the distance between the closest node N 0  and A is less than R. 
           [0018]      FIG. 3 . shows the areas S N2  (in which node N 2  must lie) when the distance between the closest node N 0  and A is less than R, and node N 1  is within coordinate (x 1 , y 1 ). 
           [0019]      FIG. 4 . shows the calculation result and simulation result of probability of triangulation. 
           [0020]      FIG. 5 . shows all possible quadrangles N 1 N 3 N 2 N 4  forming a un-triangulated hole with hole radius (R t ). 
           [0021]      FIG. 6 . shows how a un-triangulated hole with hole radius (R t ) is triangulated when the sensing radius is enlarged to R t.    
           [0022]      FIG. 7 . shows the calculation result of un-triangulated hole size with various hole radius (R t ) assuming the un-triangulated hole is a quadrangle area or a ellipse respectively. 
           [0023]      FIG. 8 . shows how the expected number of holes with various hole radius R t  is calculated based on the probability of un-triangulation in the target area. 
           [0024]      FIG. 9 . shows the expected number of holes in the unit area with various hole densities (R t ), and various node densities (λ). 
           [0025]      FIG. 10 . shows the total number of un-triangulated holes in the unit area (hole density) with various node densities. 
           [0026]      FIG. 11 . shows boundary effect while detecting a hole. 
           [0027]      FIG. 12 . shows the calculation result and simulation result of probability of no un-triangulated hole for various target area sizes and various node densities. 
           [0028]      FIG. 13 . shows the calculation result of probability of no un-triangulated hole considering boundary effect. 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     A. Probability of Triangulation 
       [0029]    If a point A lies within the area being studied, the probability of triangulation can be estimated, namely the lower bound of the probability that A has three neighbours (each lying within 2R of A) connected to each other by links which form a triangle around A, assuming uniform sensing area πR 2 =1, and hence the sensing range R=1/√π. 
         [0030]    These neighbours are called N 0 , N 1 , and N 2 . It is assumed that the closest neighbour is a vertex of this triangle and that it is called N 0 , because the closest node is most likely to triangulate the point. 10 6  simulations with varied numbers of neighbours showed that if the closest node cannot triangulate A, its probability of being triangulated by any other three nodes is less than 2%, which can be neglected in order to simplify the calculation. To put this more rigorously, it can be stated that the probability of triangulation is greater than or equal to the probability when the closest node to A is involved in triangulating it. 
         [0000]      Prob(Triangulation)≧Prob(Triangulation always using the closest node to  A ) 
         [0031]    Thus a lower bound on the probability of triangulation will now be derived. The distance between N 0  and A is x 0 , with 0&lt;x 0 &lt;2R, assuming each node has circular sensing area of radius R. N 1  and N 2  are further than x 0  from A. It is necessary that 0&lt;x 0 &lt;2R/√3, in order for a suitable triangle to exist. 
         [0032]      FIGS. 2 and 3  show the areas S N1  (in which node N 1  must lie) and S N2  (in which node N 2  must lie). Any position in S N1  must be less than 2R from N 0  to ensure that N 1  and N 0  are connected, moreover, regardless of what position N 1  occupies within S N1 , the area of S N2  defined by the condition which follows must be greater than zero. The left (right) semicircle is defined as the area to the left (right) of the y-axis. If N 1  is located in one semicircle (left or right), S N2  must be a sub-area of S N1  in the other semicircle with each point within it closer than 2R from N 1 , so that N 2  is connected to both N 0  and N 1 . Point A is therefore triangulated by N 0 , N 1  and N 2  as shown in  FIG. 1 . 
         [0033]    Now that S N1  and S N2  have both been determined, the probability may be found that at least one node falls inside S N1  and the other inside S N2 , namely the probability of triangulation for some specified value of x 0 . The integral of this over the range 0&lt;x 0 &lt;2/√3 R is the probability of triangulation by the closest node and two other neighbours. 
         [0034]    If both N 1  and N 2  lie in the same semicircle in  FIG. 2 , N 0 , N 1  and N 2  cannot form a triangle enclosing A. Similarly, N 0  and N 2  (or N 1 ) must not lie to the same side of line AN 1  (or AN 2 ) ( FIG. 3 ), otherwise A would lie outside the triangle formed by N 0 , N 1  and N 2.  The node in the right semicircle is designated N 1 , while N 2  is in the left semicircle. 
         [0035]    N 1  must be within 2R of N 0  in order to connect to it, and should be further than x 0  units from A because the distance between the closest node N 0  and A is x 0 . Therefore N 1  may lie within S N1 , which is defined as the intersection of two circles centred on N 0  and A, each having a radius of 2R. However, the circle centred on A with radius x 0  is excluded. Hence N 1  lies within 2R of both A and N 0 . 
         [0036]    If N 1  is located to the right (left) side of S N1 , then N 2  should lie to the left (right) side of S N1  in order to enclose A. Similarly, if N 1  is located to the same side of the y-axis as N 0  (under point A in  FIGS. 2 and 3 ), then N 2  should be on the other side. Therefore the possible area S N2  (containing N 2 ) is the intersection of S N1  and the circle centred on N 1  with radius 2R. S N2  is on the opposite side of the y-axis from N 1 . 
         [0037]    Unfortunately, for some positions in S N1 , S N2  is the empty set because both N 1  and N 2  are located at the left (right) side, or there is no intersecting area above A when N 1  is located beneath it. In order to ensure that S N2  is non-empty, it should include at least one point (C left  and C right ) for the left and right semicircles respectively within S N1  that are closest to both N 0  and the y-axis. C right  (C left ) is the point to the right (left) side of S N1  with minimum mean distance to any position in the left (right) side of S N1 , therefore it is the closest point to the y-axis. If there is more than one point closest to the y-axis, then C right  (C left ) is the closest point to both A and N 0  (point C in  FIG. 2 ) but C should lie on the opposite side of the x-axis from N 0  in order to triangulate A. In  FIG. 2  where x 0 ≦R, the two points C left  and C right  represent the same point named C, where the coordinates of C is (0, x 0 ). 
         [0038]    As discussed above, N 1  and N 2  must lie in different semicircles (left and right), in order to ensure that with N 0 , they form a triangle enclosing A ( FIG. 3 ). 
         [0039]    For x 0 ≦R and some specified position of N 1 , namely (x 1 , y 1 ), it is possible that N 0  and N 2  lie on the same side of line AN 1 , so that N 2  falls within the area S N2 ′ ( FIG. 3 ). In this case, A is not located inside the triangle formed by N 0 , N 1  and N 2 . If we consider N 1 ′, located at (x 1 , −y 1 ), a similar situation occurs when N 2  falls inside S N2 . Therefore the mean area of S N2  for N 1 (x 1 , y 1 ) and N 1 ′(x 1 , −y 1 ) is (S N2 +S N2 ′)/ 2 , as shown in  FIG. 3 ; this result is used in later calculations. 
         [0040]    S N1 (x 0 ) and S N2 (x 0 ) are the sizes of the areas in which N 1  and N 2  respectively may each lie for any x 0  (distance between N 0  and A). For the purposes of the calculation, N 1  and N 2  are assumed to lie on the left and right semicircles respectively in order to triangulate position A. Therefore S N1 (x 0 ) and S N2 (x 0 ) are the areas of each region coinciding with only one semicircle. S N1 (x 0 )=0 for x 0 ≧2/√3 R. 
         [0041]    For 0&lt;x 0 ≦R ( FIG. 3 ): 
         [0000]    
       
         
           
               
             
               
                 
                   
                     
                       
                         S 
                         
                           N 
                           1 
                         
                       
                        
                       
                         ( 
                         
                           x 
                           0 
                         
                         ) 
                       
                     
                     = 
                       
                      
                     
                       2 
                        
                       
                         
                           ∫ 
                           0 
                           
                             
                               2 
                                
                               
                                   
                               
                                
                               R 
                             
                             - 
                             
                               x 
                               0 
                             
                           
                         
                          
                         
                           
                             ( 
                             
                               
                                 ∫ 
                                 
                                   
                                     max 
                                      
                                     
                                       ( 
                                       
                                         
                                           
                                             x 
                                             0 
                                             2 
                                           
                                           - 
                                           
                                             y 
                                             1 
                                             2 
                                           
                                         
                                         , 
                                         0 
                                       
                                       ) 
                                     
                                   
                                 
                                 
                                   
                                     
                                       4 
                                        
                                       
                                         R 
                                         2 
                                       
                                     
                                     - 
                                     
                                       
                                         ( 
                                         
                                           
                                             x 
                                             0 
                                           
                                           + 
                                           
                                             y 
                                             1 
                                           
                                         
                                         ) 
                                       
                                       2 
                                     
                                   
                                 
                               
                                
                               
                                   
                               
                                
                               
                                  
                                 
                                   x 
                                   1 
                                 
                               
                             
                             ) 
                           
                            
                           
                               
                           
                            
                           
                              
                             
                               y 
                               1 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   
                     = 
                       
                      
                     
                       2 
                        
                       
                         
                           ∫ 
                           0 
                           
                             
                               2 
                                
                               R 
                             
                             - 
                             
                               x 
                               0 
                             
                           
                         
                          
                         
                           
                             ( 
                             
                               
                                 
                                   
                                     4 
                                      
                                     
                                       R 
                                       2 
                                     
                                   
                                   - 
                                   
                                     
                                       ( 
                                       
                                         
                                           x 
                                           0 
                                         
                                         + 
                                         
                                           y 
                                           1 
                                         
                                       
                                       ) 
                                     
                                     2 
                                   
                                 
                               
                               - 
                               
                                 
                                   max 
                                    
                                   
                                     ( 
                                     
                                       
                                         
                                           x 
                                           0 
                                           2 
                                         
                                         - 
                                         
                                           y 
                                           1 
                                           2 
                                         
                                       
                                       , 
                                       0 
                                     
                                     ) 
                                   
                                 
                               
                             
                             ) 
                           
                            
                           
                               
                           
                            
                           
                              
                             
                               y 
                               1 
                             
                           
                         
                       
                     
                   
                 
               
             
           
         
       
     
         [0042]    N 1 (x 1 , y 1 ) is assumed to lie above the x-axis and to the right of the y-axis only because S N1  is symmetrical about both the x-axis and the y-axis. 
         [0043]    S N2 (x 0 ) is the integral over x 1  and y 1  of the area S N2 (x 1 , y 1 ) which results when N 1  lies at (x 1,  y 1 ). For 0&lt;x 0 ≦R: 
         [0000]    
       
         
           
             
                 
             
              
             
               
                 
                   S 
                   
                     N 
                     2 
                   
                 
                  
                 
                   ( 
                   
                     x 
                     0 
                   
                   ) 
                 
               
               = 
               
                 
                   1 
                   
                     
                       S 
                       
                         N 
                         1 
                       
                     
                      
                     
                       ( 
                       
                         x 
                         0 
                       
                       ) 
                     
                   
                 
                  
                 
                   
                     ∫ 
                     0 
                     
                       
                         2 
                          
                         R 
                       
                       - 
                       
                         x 
                         0 
                       
                     
                   
                    
                   
                     
                       ( 
                       
                         2 
                          
                         
                             
                         
                          
                         
                           
                             ∫ 
                             
                               
                                 max 
                                  
                                 
                                   ( 
                                   
                                     
                                       
                                         x 
                                         0 
                                         2 
                                       
                                       - 
                                       
                                         y 
                                         1 
                                         2 
                                       
                                     
                                     , 
                                     0 
                                   
                                   ) 
                                 
                               
                             
                             
                               
                                 
                                   4 
                                    
                                   
                                     R 
                                     2 
                                   
                                 
                                 - 
                                 
                                   
                                     ( 
                                     
                                       
                                         x 
                                         0 
                                       
                                       + 
                                       
                                         y 
                                         1 
                                       
                                     
                                     ) 
                                   
                                   2 
                                 
                               
                             
                           
                            
                           
                             
                               
                                 S 
                                 
                                   N 
                                   2 
                                 
                               
                                
                               
                                 ( 
                                 
                                   
                                     x 
                                     1 
                                   
                                   , 
                                   
                                     y 
                                     1 
                                   
                                 
                                 ) 
                               
                             
                              
                             
                                
                               
                                 x 
                                 1 
                               
                             
                           
                         
                       
                       ) 
                     
                      
                     
                        
                       
                         y 
                         1 
                       
                     
                   
                 
               
             
           
         
       
       
         
           
             
               
                 S 
                 
                   N 
                   2 
                 
               
                
               
                 ( 
                 
                   
                     x 
                     1 
                   
                   , 
                   
                     y 
                     1 
                   
                 
                 ) 
               
             
             = 
             
               
                 
                   1 
                   2 
                 
                  
                 
                   
                     ∫ 
                     0 
                     
                       
                         2 
                          
                         R 
                       
                       - 
                       
                         x 
                         1 
                       
                     
                   
                    
                   
                     
                       max 
                        
                       
                         [ 
                         
                           
                             
                               
                                 
                                   min 
                                    
                                   
                                     ( 
                                     
                                       
                                         
                                           
                                             
                                               
                                                 
                                                   
                                                     4 
                                                      
                                                     
                                                       R 
                                                       2 
                                                     
                                                   
                                                   - 
                                                   
                                                     
                                                       ( 
                                                       
                                                         
                                                           x 
                                                           1 
                                                         
                                                         + 
                                                         
                                                           x 
                                                           2 
                                                         
                                                       
                                                       ) 
                                                     
                                                     2 
                                                   
                                                 
                                               
                                               + 
                                               
                                                 y 
                                                 1 
                                               
                                             
                                             , 
                                           
                                         
                                       
                                       
                                         
                                           
                                             
                                               
                                                 
                                                   4 
                                                    
                                                   
                                                     R 
                                                     2 
                                                   
                                                 
                                                 - 
                                                 
                                                   x 
                                                   2 
                                                   2 
                                                 
                                               
                                             
                                             - 
                                             
                                               x 
                                               0 
                                             
                                           
                                         
                                       
                                     
                                     ) 
                                   
                                 
                                 - 
                               
                             
                           
                           
                             
                               
                                 
                                   
                                     max 
                                      
                                     
                                       ( 
                                       
                                         0 
                                         , 
                                         
                                           
                                             x 
                                             0 
                                             2 
                                           
                                           - 
                                           
                                             x 
                                             2 
                                             2 
                                           
                                         
                                       
                                       ) 
                                     
                                   
                                 
                                 , 
                                 0 
                               
                             
                           
                         
                         ] 
                       
                     
                      
                     
                         
                     
                      
                     
                        
                       
                         x 
                         2 
                       
                     
                   
                 
               
               + 
               
                 
                   1 
                   2 
                 
                  
                 
                   
                     ∫ 
                     0 
                     
                       
                         2 
                          
                         R 
                       
                       - 
                       
                         x 
                         1 
                       
                     
                   
                    
                   
                     
                       max 
                        
                       
                         [ 
                         
                           
                             
                               
                                 
                                   min 
                                   ( 
                                   
                                     
                                       
                                         
                                           
                                             
                                               
                                                 
                                                   4 
                                                    
                                                   
                                                     R 
                                                     2 
                                                   
                                                 
                                                 - 
                                                 
                                                   
                                                     ( 
                                                     
                                                       
                                                         x 
                                                         1 
                                                       
                                                       + 
                                                       
                                                         x 
                                                         2 
                                                       
                                                     
                                                     ) 
                                                   
                                                   2 
                                                 
                                               
                                             
                                             - 
                                             
                                               y 
                                               1 
                                             
                                           
                                           , 
                                         
                                       
                                     
                                     
                                       
                                         
                                           
                                             
                                               
                                                 4 
                                                  
                                                 
                                                   R 
                                                   2 
                                                 
                                               
                                               - 
                                               
                                                 x 
                                                 2 
                                                 2 
                                               
                                             
                                           
                                           - 
                                           
                                             x 
                                             0 
                                           
                                         
                                       
                                     
                                   
                                   ) 
                                 
                                 - 
                               
                             
                           
                           
                             
                               
                                 
                                   
                                     max 
                                      
                                     
                                       ( 
                                       
                                         0 
                                         , 
                                         
                                           
                                             x 
                                             0 
                                             2 
                                           
                                           - 
                                           
                                             x 
                                             2 
                                             2 
                                           
                                         
                                       
                                       ) 
                                     
                                   
                                 
                                 , 
                                 0 
                               
                             
                           
                         
                         ] 
                       
                     
                      
                     
                         
                     
                      
                     
                        
                       
                         x 
                         2 
                       
                     
                   
                 
               
             
           
         
       
     
         [0044]    For R&lt;x 0 ≦2R/√3, because the probability that three nodes can triangulate A is very low (&lt;&lt;1%) according to the calculation result, therefore it is not calculated in the invention. 
         [0045]    With a 2D Poisson process, the approximation can be made as follows: 
         [0046]    For each x 0  (the distance from the closest node to A), the probability of triangulation f(x 0 ) is Prob(no node in area πx 0   2 )·Prob(at least one node in area 2πx 0 dx 0 )·Prob(at least one node in area S N1 (x 0 ) and at least one node in area S N2 (x 0 ), with S N1  in either the left or right semicircle), which can be calculated as below: 
         [0000]    
       
         
           
             
               f 
                
               
                 ( 
                 
                   x 
                   0 
                 
                 ) 
               
             
             = 
             
               
                 
                    
                   
                     
                       - 
                       λ 
                     
                      
                     
                         
                     
                      
                     π 
                      
                     
                         
                     
                      
                     
                       x 
                       0 
                       2 
                     
                   
                 
                  
                 
                   ( 
                   
                     1 
                     - 
                     
                        
                       
                         
                           
                             - 
                             λ 
                           
                           · 
                           2 
                         
                          
                         
                             
                         
                          
                         π 
                          
                         
                             
                         
                          
                         
                           x 
                           0 
                         
                          
                         
                           dx 
                           0 
                         
                       
                     
                   
                   ) 
                 
               
                
               
                 [ 
                 
                   γ 
                   + 
                   
                     
                       ( 
                       
                         1 
                         - 
                         γ 
                       
                       ) 
                     
                      
                     γ 
                   
                 
                 ] 
               
             
           
         
       
       
         
           
             
               Because 
                
               
                   
               
                
               
                  
                 
                   zdx 
                   0 
                 
               
             
             = 
             
               1 
               + 
               
                 zdx 
                 0 
               
               + 
               
                 
                   
                     ( 
                     
                       zdx 
                       0 
                     
                     ) 
                   
                   2 
                 
                 
                   2 
                   ! 
                 
               
               + 
               
                 
                   
                     ( 
                     
                       zdx 
                       0 
                     
                     ) 
                   
                   3 
                 
                 
                   3 
                   ! 
                 
               
               + 
               
                 
                   
                     ( 
                     
                       zdx 
                       0 
                     
                     ) 
                   
                   4 
                 
                 
                   4 
                   ! 
                 
               
               + 
               … 
             
           
         
       
     
         [0000]    where z=−λ·2πx 0 , for dx 0 →0, therefore e zx     0   ≈1−λ·2πx 0 dx 0 . 
       Therefore 
       [0047]        f ( x   0 )≈ e   −λπx     0     2 [1−(1−λ·2π x   0   dx   0 )][γ+(1−γ)γ]= e   −λπx     0     2 (2γ−γ 2 )λ·2π x   0   dx   0    
         [0000]      γ=(1− e   −λ·S     N1     (x     0     ) )(1− e   −λ·S     N2     (x     0     ) ) 
         [0048]    γ is the Probability that there is at least one node in area S N1 (x 0 ) and at least one node in area S N2 (x 0 ) for S N1  within the right side and S N2  within the left side. 
         [0049]    The probability of triangulation P t  for a specified point (assuming a mean node density of λ in a two-dimensional Poisson process) may be calculated as follows: 
         [0000]    
       
         
           
             
               
                 P 
                 t 
               
                
               
                 ( 
                 λ 
                 ) 
               
             
             = 
             
               
                 
                   ∫ 
                   0 
                   
                     2 
                      
                     R 
                   
                 
                  
                 
                   f 
                    
                   
                     ( 
                     
                       x 
                       0 
                     
                     ) 
                   
                 
               
               ≈ 
               
                 
                   ∫ 
                   0 
                   R 
                 
                  
                 
                   
                     
                        
                       
                         
                           - 
                           λ 
                         
                          
                         
                             
                         
                          
                         π 
                          
                         
                             
                         
                          
                         
                           x 
                           0 
                           2 
                         
                       
                     
                      
                     
                       ( 
                       
                         
                           2 
                            
                           
                               
                           
                            
                           γ 
                         
                         - 
                         
                           γ 
                           2 
                         
                       
                       ) 
                     
                   
                    
                   2 
                    
                   
                       
                   
                    
                   λ 
                    
                   
                       
                   
                    
                   π 
                    
                   
                       
                   
                    
                   
                     x 
                     0 
                   
                    
                   
                       
                   
                    
                   
                      
                     
                       x 
                       0 
                     
                   
                 
               
             
           
         
       
     
         [0050]    The probability of triangulation not occurring at a specified point is P nt (λ): 
         [0000]        P   nt (λ)=1− P   t (λ)   [1] 
         [0051]    Ten thousand simulations with varied node densities (λ) were run to confirm the analysis. For each simulation, 4λ nodes are randomly deployed inside a circle with radius 2R centred on point. If A is located within a triangle formed by the closest node N 0  and any other two nodes, all closer than 2R from each other, then A is triangulated.  FIG. 4  shows that the simulation results agree with calculations very well for the probability of triangulation at a specified point with exactly 4λ neighbours, with a maximum difference of less than 1% for λ≧5. Furthermore, in contrast to the point in question having a fixed number of neighbours, one thousand simulations with random nodal deployment (two-dimensional Poisson process) for each mean node density λ (12≧λ≧1) were also carried out. Hence the number of neighbours is not necessarily exactly 4λ due to the use of a Poisson process. With λ&gt;4, the analytical results agree with simulation to within 5% ( FIG. 4 ). 
       B. Calculation of the Mean Size of a Hole 
       [0052]    Assume that all nodes have circular sensing areas of radius R. The hole radius (or triangulated radius) is denoted by R t  and is defined as follows. For an un-triangulated hole, R t  may be found, where R t &gt;R, so that the hole only becomes triangulated if the sensing radius of all its boundary nodes is increased to at least R t .  FIG. 6  shows how a hole lying within quadrangle N 1 N 4 N 2 N 3  can be triangulated by increasing the sensing radius to R t  so that each edge cannot be longer than 2R t . In other cases, a hole may be enclosed by more than one connected quadrangle, which can be considered as two or more adjacent holes, however this is neglected in the following analysis because it is rare in high-density networks. 
         [0053]    The conditions for a hole to be enclosed by a quadrangle with boundary node sensing radii of exactly R t  are defined by the following two points:
       1. One diagonal of the quadrangle must be of length 2R t , and the other diagonal must be no shorter than 2R t , so that it can be triangulated by links of length 2R t  or greater. And the hole could not be triangulated by links shorter than 2R t , with R&lt;R t .   2. Each edge of the quadrangle must be no longer than 2R t , otherwise the hole cannot not be triangulated by links of this length or shorter.       
 
         [0056]    A general description of all possible quadrangles N 1 N 3 N 2 N 4  defined by the above conditions is provided in  FIG. 5 . N 1  and N 2  are two sensor nodes 2R t  units apart, and the large circles centred on these nodes both have radius 2R t . N 3  may lie anywhere inside S N3 , which is the intersection of the circles centred on N 1  and N 2 , excluding the void area. C and D are the highest and lowest points respectively inside S N3 . The void area is the intersection of two circles with radii 2R t  centred on C and D ( FIG. 5 ). 
         [0057]    N 4  may lie anywhere inside S N4 , which is a subset of S N3  defined by a specific position of N 3 (x 3 , y 3 ), such that the distance between N 3  and any point in S N4  is greater than or equal to 2R t , as dictated by condition 1 above—see  FIG. 5 . If N 3  is in the void area, the distance from it to N 4  cannot be more than 2R t . N 3  and N 4  must be on opposite sides of the x-axis, so that they can be more than 2R t  units apart. A and B are the leftmost and rightmost points respectively within S N4 . 
         [0058]    The area of the quadrangle is Q=HR t , where H=y 4 −y 3  ( FIG. 6 ). H mean  is the mean of H, and the mean area of the quadrangle is Q mean . It is shown below that: 
         [0000]        Q   mean   =R   t   ×H   mean ≈2.21 R   t   2    
         [0059]    For each possible point N 4 (x 4 , y 4 ) inside S N4 , corresponding to every point N 3 (x 3 , y 3 ) inside S N3 , the height H of the quadrangle is calculated, in order to derive H mean . In the following calculations, x 3 &lt;0 and y 3 &lt;0, which does not affect the result, because S N3  is symmetrical about both x-axis and y-axis. 
         [0000]    
       
         
           
             
               H 
               mean 
             
             = 
             
               
                 
                   
                     ∫ 
                     0 
                     
                       - 
                       Rt 
                     
                   
                    
                   
                     
                       ( 
                       
                         
                           ∫ 
                           
                             - 
                             
                               
                                 
                                   4 
                                    
                                   
                                     Rt 
                                     2 
                                   
                                 
                                 - 
                                 
                                   
                                     ( 
                                     
                                       Rt 
                                       - 
                                       
                                         x 
                                         3 
                                       
                                     
                                     ) 
                                   
                                   2 
                                 
                               
                             
                           
                           
                             
                               
                                 3 
                               
                                
                               Rt 
                             
                             - 
                             
                               
                                 
                                   4 
                                    
                                   
                                     Rt 
                                     2 
                                   
                                 
                                 - 
                                 
                                   x 
                                   3 
                                   2 
                                 
                               
                             
                           
                         
                          
                         
                           H 
                           × 
                           
                             S 
                             
                               N 
                                
                               
                                   
                               
                                
                               4 
                             
                           
                            
                           
                               
                           
                            
                           
                              
                             
                               y 
                               3 
                             
                           
                         
                       
                       ) 
                     
                      
                     
                         
                     
                      
                     
                        
                       
                         x 
                         3 
                       
                     
                   
                 
                 
                   
                     ∫ 
                     0 
                     
                       - 
                       Rt 
                     
                   
                    
                   
                     
                       ( 
                       
                         
                           ∫ 
                           
                             - 
                             
                               
                                 
                                   4 
                                    
                                   
                                     Rt 
                                     2 
                                   
                                 
                                 - 
                                 
                                   
                                     ( 
                                     
                                       Rt 
                                       - 
                                       
                                         x 
                                         3 
                                       
                                     
                                     ) 
                                   
                                   2 
                                 
                               
                             
                           
                           
                             
                               
                                 3 
                               
                                
                               Rt 
                             
                             - 
                             
                               
                                 
                                   4 
                                    
                                   
                                     Rt 
                                     2 
                                   
                                 
                                 - 
                                 
                                   x 
                                   3 
                                   2 
                                 
                               
                             
                           
                         
                          
                         
                           
                             S 
                             
                               N 
                                
                               
                                   
                               
                                
                               4 
                             
                           
                            
                           
                               
                           
                            
                           
                              
                             
                               y 
                               3 
                             
                           
                         
                       
                       ) 
                     
                      
                     
                         
                     
                      
                     
                        
                       
                         x 
                         3 
                       
                     
                   
                 
               
               ≈ 
               
                 2.21 
                  
                 Rt 
               
             
           
         
       
       
         
           
             
               
                 
                   
                     S 
                     
                       N 
                        
                       
                           
                       
                        
                       4 
                     
                   
                   = 
                     
                    
                   
                     
                       ∫ 
                       
                         x 
                         a 
                       
                       
                         x 
                         b 
                       
                     
                      
                     
                       
                         ( 
                         
                           
                             ∫ 
                             
                               
                                 
                                   
                                     4 
                                      
                                     
                                       Rt 
                                       2 
                                     
                                   
                                   - 
                                   
                                     
                                       ( 
                                       
                                         
                                           x 
                                           4 
                                         
                                         - 
                                         
                                           x 
                                           3 
                                         
                                       
                                       ) 
                                     
                                     2 
                                   
                                 
                               
                               + 
                               
                                 y 
                                 3 
                               
                             
                             
                               
                                 
                                   4 
                                    
                                   
                                     Rt 
                                     2 
                                   
                                 
                                 - 
                                 
                                   
                                     Max 
                                      
                                     
                                       ( 
                                       
                                         Rt 
                                         ± 
                                         
                                           x 
                                           4 
                                         
                                       
                                       ) 
                                     
                                   
                                   2 
                                 
                               
                             
                           
                            
                           
                               
                           
                            
                           
                              
                             
                               y 
                               4 
                             
                           
                         
                         ) 
                       
                        
                       
                           
                       
                        
                       
                          
                         
                           x 
                           4 
                         
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       ∫ 
                       
                         x 
                         a 
                       
                       
                         x 
                         b 
                       
                     
                      
                     
                       
                         [ 
                         
                           
                             
                               
                                 
                                   
                                     
                                       4 
                                        
                                       
                                         Rt 
                                         2 
                                       
                                     
                                     - 
                                     
                                       
                                         Max 
                                          
                                         
                                           ( 
                                           
                                             Rt 
                                             ± 
                                             
                                               x 
                                               4 
                                             
                                           
                                           ) 
                                         
                                       
                                       2 
                                     
                                   
                                 
                                 - 
                               
                             
                           
                           
                             
                               
                                 ( 
                                 
                                   
                                     
                                       
                                         4 
                                          
                                         
                                           Rt 
                                           2 
                                         
                                       
                                       - 
                                       
                                         
                                           ( 
                                           
                                             
                                               x 
                                               4 
                                             
                                             - 
                                             
                                               x 
                                               3 
                                             
                                           
                                           ) 
                                         
                                         2 
                                       
                                     
                                   
                                   + 
                                   
                                     y 
                                     3 
                                   
                                 
                                 ) 
                               
                             
                           
                         
                         ] 
                       
                        
                       
                          
                         
                           x 
                           4 
                         
                       
                     
                   
                 
               
             
           
         
       
       
         
           
             
               
                 
                   H 
                   = 
                     
                    
                   
                     
                       
                         
                           ∫ 
                           
                             x 
                             a 
                           
                           
                             x 
                             b 
                           
                         
                          
                         
                           
                             ( 
                             
                               
                                 ∫ 
                                 
                                   
                                     
                                       
                                         4 
                                          
                                         
                                           Rt 
                                           2 
                                         
                                       
                                       - 
                                       
                                         
                                           ( 
                                           
                                             
                                               x 
                                               4 
                                             
                                             - 
                                             
                                               x 
                                               3 
                                             
                                           
                                           ) 
                                         
                                         2 
                                       
                                     
                                   
                                   + 
                                   
                                     y 
                                     3 
                                   
                                 
                                 
                                   
                                     
                                       4 
                                        
                                       
                                         Rt 
                                         2 
                                       
                                     
                                     - 
                                     
                                       
                                         Max 
                                          
                                         
                                           ( 
                                           
                                             Rt 
                                             ± 
                                             
                                               x 
                                               4 
                                             
                                           
                                           ) 
                                         
                                       
                                       2 
                                     
                                   
                                 
                               
                                
                               
                                   
                               
                                
                               
                                 
                                   y 
                                   4 
                                 
                                  
                                 
                                    
                                   
                                     y 
                                     4 
                                   
                                 
                               
                             
                             ) 
                           
                            
                           
                               
                           
                            
                           
                              
                             
                               x 
                               4 
                             
                           
                         
                       
                       
                         S 
                         
                           N 
                            
                           
                               
                           
                            
                           4 
                         
                       
                     
                     - 
                     
                       y 
                       3 
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       
                         
                           ∫ 
                           
                             x 
                             a 
                           
                           
                             x 
                             b 
                           
                         
                          
                         
                           
                             
                               
                                 
                                   
                                     
                                       4 
                                        
                                       
                                         Rt 
                                         2 
                                       
                                     
                                     - 
                                     
                                       
                                         Max 
                                          
                                         
                                           ( 
                                           
                                             Rt 
                                             ± 
                                             
                                               x 
                                               4 
                                             
                                           
                                           ) 
                                         
                                       
                                       2 
                                     
                                     - 
                                   
                                 
                               
                               
                                 
                                   
                                     
                                       [ 
                                       
                                         
                                           
                                             
                                               4 
                                                
                                               
                                                 Rt 
                                                 2 
                                               
                                             
                                             - 
                                             
                                               
                                                 ( 
                                                 
                                                   
                                                     x 
                                                     4 
                                                   
                                                   - 
                                                   
                                                     x 
                                                     3 
                                                   
                                                 
                                                 ) 
                                               
                                               2 
                                             
                                           
                                         
                                         + 
                                         
                                           y 
                                           3 
                                         
                                       
                                       ] 
                                     
                                     2 
                                   
                                 
                               
                             
                             2 
                           
                            
                           
                               
                           
                            
                           
                              
                             
                               x 
                               4 
                             
                           
                         
                       
                       
                         S 
                         
                           N 
                            
                           
                               
                           
                            
                           4 
                         
                       
                     
                     - 
                     
                       y 
                       3 
                     
                   
                 
               
             
           
         
       
       
         
           
             
               
                 α 
                 1 
               
               = 
               
                 
                   cos 
                   
                     - 
                     1 
                   
                 
                 ( 
                 
                   
                     
                       
                         
                           
                             ( 
                             
                               Rt 
                               - 
                               
                                 x 
                                 3 
                               
                             
                             ) 
                           
                           2 
                         
                         + 
                         
                           y 
                           3 
                           2 
                         
                       
                     
                     / 
                     2 
                   
                   
                     2 
                      
                     Rt 
                   
                 
                 ) 
               
             
             ; 
             
               
                 α 
                 2 
               
               = 
               
                 
                   tan 
                   
                     - 
                     1 
                   
                 
                  
                 
                   ( 
                   
                     
                       - 
                       
                         y 
                         3 
                       
                     
                     
                       Rt 
                       - 
                       
                         x 
                         3 
                       
                     
                   
                   ) 
                 
               
             
           
         
       
       
         
           
             
               
                 
                   
                     x 
                     a 
                   
                   = 
                     
                    
                   
                     Rt 
                     - 
                     
                       2 
                        
                       Rt 
                        
                       
                           
                       
                        
                       
                         cos 
                          
                         
                           ( 
                           
                             
                               α 
                               1 
                             
                             - 
                             
                               α 
                               2 
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     Rt 
                     - 
                     
                       2 
                        
                       Rt 
                        
                       
                           
                       
                        
                       
                         cos 
                         [ 
                         
                           
                             
                               cos 
                               
                                 - 
                                 1 
                               
                             
                             ( 
                             
                               
                                 
                                   
                                     
                                       
                                         ( 
                                         
                                           Rt 
                                           - 
                                           
                                             x 
                                             3 
                                           
                                         
                                         ) 
                                       
                                       2 
                                     
                                     + 
                                     
                                       y 
                                       3 
                                       2 
                                     
                                   
                                 
                                 / 
                                 2 
                               
                               
                                 2 
                                  
                                 Rt 
                               
                             
                             ) 
                           
                           - 
                           
                             
                               tan 
                               
                                 - 
                                 1 
                               
                             
                              
                             
                               ( 
                               
                                 
                                   - 
                                   
                                     y 
                                     3 
                                   
                                 
                                 
                                   Rt 
                                   - 
                                   
                                     x 
                                     3 
                                   
                                 
                               
                               ) 
                             
                           
                         
                         ] 
                       
                     
                   
                 
               
             
           
         
       
       
         
           
             
               x 
               b 
             
             = 
             
               
                 2 
                  
                 Rt 
                  
                 
                     
                 
                  
                 
                   cos 
                   [ 
                   
                     
                       
                         cos 
                         
                           - 
                           1 
                         
                       
                       ( 
                       
                         
                           
                             
                               
                                 
                                   ( 
                                   
                                     Rt 
                                     + 
                                     
                                       x 
                                       3 
                                     
                                   
                                   ) 
                                 
                                 2 
                               
                               + 
                               
                                 y 
                                 3 
                                 2 
                               
                             
                           
                           / 
                           2 
                         
                         
                           2 
                            
                           Rt 
                         
                       
                       ) 
                     
                     - 
                     
                       
                         tan 
                         
                           - 
                           1 
                         
                       
                        
                       
                         ( 
                         
                           
                             - 
                             
                               y 
                               3 
                             
                           
                           
                             Rt 
                             + 
                             
                               x 
                               3 
                             
                           
                         
                         ) 
                       
                     
                   
                   ] 
                 
               
               - 
               Rt 
             
           
         
       
     
         [0060]    The un-triangulated area of a hole is not necessarily enclosed by its quadrangle, because although each edge of the quadrangle is no longer than 2R t  units, the length of an edge might be greater than 2R (e.g. edge N 2 N 3  of  FIG. 6 ). Therefore an un-triangulated area outside edge N 2 N 3  exists, which is enclosed by triangle N 2 N 5 N 3 . Hence the un-triangulated area of a hole is larger than the quadrangle area Q if one or more edges of the quadrangle are longer than 2R.  FIG. 6  shows that the un-triangulated area of the hole is enclosed by a polygon N 2  N 5  N 3  N 1  N 6  N 4  with six edges, each no longer than 2R. 
         [0061]    If all four edges of the quadrangle are longer than 2R, the un-triangulated area of the hole is enclosed by a polygon with at least eight edges. In such a case, assume that un-triangulated area is enclosed by an ellipse with radius R t  and height H/2, then the mean un-triangulated area is H mean R t π/2≈3.47R t   2 , which is larger than the mean quadrangle size 2.21R t   2 . The assumption of the un-triangulated area being an ellipse does not affect the accuracy of the calculation, as shown below. 
         [0062]    If k edges of the quadrangle are longer than 2R (k≦4), then the mean un-triangulated area is: 
         [0000]        k/ 4×ellipse_area+(1− k/ 4)×quadrangle_area=( k/ 4)3.47 R   t   2 +(1− k/ 4)2.21 R   t   2    
         [0063]    From  FIG. 6 , the probability that the un-triangulated area is enclosed by such an ellipse could be calculated for different hole radii R t . This is the probability that N 3  (or N 4 ) is more than 2R units away from N 1  or N 2 .  FIG. 7  shows that when R t ≦1.5R, the un-triangulated area is approximately equal to the quadrangle area, because for R t &lt;1.5R, the un-triangulated area is enclosed by a quadrangle with a probability of over 95%. Since for most holes, later calculations in  FIG. 9  show that R t ≦1.5R for medium and high node densities (λ≧7), the un-triangulated area of a hole is considered to be equal to the quadrangle size Q mean  in the following calculations. 
       C. Calculation of Hole Density Distribution and Hole Counting 
       [0064]    The next step is to calculate h sum , the total number of holes inside a unit area, taking into account all hole radii R t  (where R&lt;R t &lt;∞): 
         [0000]    
       
         
           
             
               h 
               sum 
             
             = 
             
               
                 
                   ∑ 
                   
                     Rt 
                     = 
                     R 
                   
                   ∞ 
                 
                  
                 
                   
                     
                       
                         S 
                         
                           n 
                            
                           
                               
                           
                            
                           t 
                         
                       
                        
                       
                         ( 
                         
                           R 
                           t 
                         
                         ) 
                       
                     
                     × 
                     1 
                   
                   
                     Q 
                     mean 
                   
                 
               
               = 
               
                 
                   
                     ∑ 
                     
                       Rt 
                       = 
                       R 
                     
                     ∞ 
                   
                    
                   
                     
                       
                         S 
                         
                           n 
                            
                           
                               
                           
                            
                           t 
                         
                       
                        
                       
                         ( 
                         
                           R 
                           t 
                         
                         ) 
                       
                     
                     
                       2.21 
                        
                       
                           
                       
                        
                       
                         R 
                         t 
                         2 
                       
                     
                   
                 
                 = 
                 
                   
                     ∑ 
                     
                       Rt 
                       = 
                       R 
                     
                     ∞ 
                   
                    
                   
                     
                       
                         P 
                         
                           n 
                            
                           
                               
                           
                            
                           t 
                         
                       
                        
                       
                         ( 
                         λ 
                         ) 
                       
                     
                     
                       2.21 
                        
                       
                           
                       
                        
                       
                         R 
                         t 
                         2 
                       
                     
                   
                 
               
             
           
         
       
     
         [0065]    S nt (R t ) is the expected un-triangulated area within a unit area, for hole radii of R t , which can be derived from the probability of triangulation calculated in [1] of section A. Assuming random deployment following a two-dimensional Poisson process with node density λ, the probability of non triangulation for any point is P nt (λ). λ is the mean number of nodes lying inside the unit sensing area πR 2 . 
         [0066]    Therefore 
         [0000]    
       
         
           
             
               
                 
                   ∑ 
                   
                     
                       R 
                       t 
                     
                     = 
                     R 
                   
                   ∞ 
                 
                  
                 
                   
                     S 
                     
                       n 
                        
                       
                           
                       
                        
                       t 
                     
                   
                    
                   
                     ( 
                     
                       R 
                       t 
                     
                     ) 
                   
                 
               
               = 
               
                 
                   
                     P 
                     
                       n 
                        
                       
                           
                       
                        
                       t 
                     
                   
                    
                   
                     ( 
                     λ 
                     ) 
                   
                 
                 × 
                 1 
               
             
             , 
           
         
       
     
         [0000]    which is the expected un-triangulated area in a unit area, including all un-triangulated holes (quadrangles), with hole radii of R t . 
         [0067]    Assume λ 0 =λ and R t(0) =R. If the sensing radii are enlarged from R to R t(i)  (i&gt;0), then by definition, any un-triangulated holes with hole radii less than R t(i)  would disappear, whereas all other holes would remain un-triangulated. Hence the un-triangulated area S i  with hole radii between R t(i)  and R t(i+1)  (i≧0) inside unit area may be calculated as: 
         [0000]        S   i   =[P   nt (λ i )− P   nt (λ i+1 )]·1 
         [0068]    λ i  is the node density for sensing radii of R t(i) , which is the mean number of nodes lying inside an area of πR t(i)   2 , as shown in  FIG. 8 . 
         [0000]    
       
         
           
             
               λ 
               i 
             
             = 
             
               
                 
                   λ 
                   × 
                   π 
                    
                   
                       
                   
                    
                   
                     R 
                     
                       t 
                        
                       
                         ( 
                         i 
                         ) 
                       
                     
                     2 
                   
                 
                 
                   π 
                    
                   
                       
                   
                    
                   
                     R 
                     2 
                   
                 
               
               = 
               
                 
                   λ 
                    
                   
                       
                   
                    
                   
                     R 
                     
                       t 
                        
                       
                         ( 
                         i 
                         ) 
                       
                     
                     2 
                   
                 
                 
                   R 
                   2 
                 
               
             
           
         
       
       
         
           
             
               R 
               
                 t 
                  
                 
                   ( 
                   i 
                   ) 
                 
               
             
             = 
             
               
                 
                   
                     
                       λ 
                       i 
                     
                     × 
                     
                       R 
                       2 
                     
                   
                   λ 
                 
               
               = 
               
                 R 
                  
                 
                   
                     
                       λ 
                       i 
                     
                     λ 
                   
                 
               
             
           
         
       
     
         [0069]    If the interval R t(i+1) −R t(i) →0, then H i , the expected number of un-triangulated holes inside a unit area for hole radii between R t(i+1)  and R t(i)  may be calculated as: 
         [0000]    
       
         
           
             
               
                 
                   
                     H 
                     i 
                   
                   = 
                     
                    
                   
                     
                       S 
                       i 
                     
                     / 
                     
                       
                         Q 
                         mean 
                       
                        
                       
                         ( 
                         
                           R 
                           
                             t 
                              
                             
                               ( 
                               i 
                               ) 
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       
                         
                           P 
                           
                             n 
                              
                             
                                 
                             
                              
                             t 
                           
                         
                          
                         
                           ( 
                           
                             λ 
                             i 
                           
                           ) 
                         
                       
                       - 
                       
                         
                           P 
                           
                             n 
                              
                             
                                 
                             
                              
                             t 
                           
                         
                          
                         
                           ( 
                           
                             λ 
                             
                               i 
                               + 
                               1 
                             
                           
                           ) 
                         
                       
                     
                     
                       2.21 
                        
                       
                           
                       
                        
                       
                         R 
                         
                           t 
                            
                           
                             ( 
                             i 
                             ) 
                           
                         
                         2 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       
                         
                           P 
                           
                             n 
                              
                             
                                 
                             
                              
                             t 
                           
                         
                          
                         
                           ( 
                           
                             λ 
                             i 
                           
                           ) 
                         
                       
                       - 
                       
                         
                           P 
                           
                             n 
                              
                             
                                 
                             
                              
                             t 
                           
                         
                          
                         
                           ( 
                           
                             λ 
                             
                               i 
                               + 
                               1 
                             
                           
                           ) 
                         
                       
                     
                     
                       2.21 
                        
                       
                           
                       
                        
                       
                         R 
                         2 
                       
                        
                       
                         
                           λ 
                           i 
                         
                         λ 
                       
                     
                   
                 
               
             
           
         
       
     
         [0070]    Therefore the expected total number of un-triangulated holes h sum  inside unit area may be calculated as: 
         [0000]    
       
         
           
             
               h 
               sum 
             
             = 
             
               
                 
                   ∑ 
                   
                     i 
                     = 
                     0 
                   
                   ∞ 
                 
                  
                 
                   H 
                   i 
                 
               
               = 
               
                 
                   ∑ 
                   
                     i 
                     = 
                     0 
                   
                   ∞ 
                 
                  
                 
                   
                     
                       
                         P 
                         
                           n 
                            
                           
                               
                           
                            
                           t 
                         
                       
                        
                       
                         ( 
                         
                           λ 
                           i 
                         
                         ) 
                       
                     
                     - 
                     
                       
                         P 
                         
                           n 
                            
                           
                               
                           
                            
                           t 
                         
                       
                        
                       
                         ( 
                         
                           λ 
                           
                             i 
                             + 
                             1 
                           
                         
                         ) 
                       
                     
                   
                   
                     2.21 
                      
                     
                         
                     
                      
                     
                       R 
                       2 
                     
                      
                     
                       
                         λ 
                         i 
                       
                       λ 
                     
                   
                 
               
             
           
         
       
     
         [0071]      FIG. 9  shows the expected number of holes in the unit area for the interval R t(i+1) −R t(i) =0.1, and 2≦λ≦12. For λ=2, and 1.1R≧R t &gt;R, the expected number of holes in the unit area is 0.16, and not surprisingly, the expected number of holes drops to 0 when R t &gt;2R. However for λ≧5, the expected number of holes is close to zero when R t &gt;1.4R. 
         [0072]      FIG. 10  shows the total number of un-triangulated holes in the unit area (hole density). It shows that the hole density is largest (0.58) for λ=1.25, because for lower node density, the nodes are too sparsely deployed to form any un-triangulated polygons (holes), so that the mean hole size is much larger than that of higher node densities. For higher node densities, the hole density drops quickly to less than 0.1 for λ≧4.5. For λ&gt;10, the hole density is close to zero. 
         [0073]    Finally, the expected number of holes in the target area S with node density λ is calculated as below: 
         [0000]        E   hole (λ)= h   sum   ×S    
         [0074]    If the centre of a hole with hole radii R t  lies less than R t  units from the boundary of the target area ( FIG. 11 ), this hole cannot be detected because no nodes are allowed outside the target area. Calculation result shows the mean of R t  is approximately 1.1R for 20≧λ≧2. In order to overcome the boundary effect, only holes centred within the non-boundary area, more than R t =1.1R units (R=1/√π) from the boundary, may be calculated ( FIG. 11 ). 
         [0075]    Simulations were performed to detected un-triangulated holes inside target areas of between 16 and 160 square units, using Matlab 7.0 as the simulator. For each target area, 100 simulations with random node deployment were performed using the 3MeSH-DR hole detection and recovery algorithm as proposed by Xiaoyun Li and David Hunter, for 12≧λ≧2. 
         [0076]    In  FIGS. 12 and 13 , P noHole  (the probability of no un-triangulated hole) is calculated by: 
         [0000]    
       
      
       P 
       noHole 
       =e 
       −E 
       
         hole 
       
       (λ)  
      
     
         [0000]    The simulation results in  FIGS. 12 and 13  show that the probability of no un-triangulated hole increases from less than 10% to more than 98% when the node density increases from 3 to 12 for most target area sizes considered. But for the smallest target area sizes of 16 and 32 square units, the probability of no hole increases for lower node densities (λ≦3), because the mean hole radius for these lower node densities is large (around 1.4R), and some of the holes&#39; radii could be more than 1.8R as shown in  FIG. 10 . Therefore for small target areas, as one would expect, the boundary effect dominates, indeed, holes with larger hole radii are less likely to be detected. Hence the probability of no hole is higher for low node densities. However for higher node densities (λ≧4), the probability of no hole increases monotonically for target area sizes greater than or equal to 16 square units. 
         [0077]      FIG. 12  shows that because of the boundary effect, there is a large offset between the simulation results from the 3MeSH hole detection algorithm and the analytical result. As expected, the offset is smaller for larger areas, due to the decreased influence of the boundary effect.  FIG. 13  shows that the offset decreases greatly after considering the boundary effect in the way discussed above. The calculation results agree with the simulations very well for each target area considered with varied node densities, with an average error of less than 5%.