# Boundary Recognition by Simulating a Diffusion Process in Wireless Sensor Networks

Authors: De Gu; Jishuai Wang; Ji Li
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

Wireless sensor networks (WSN) are becoming increasingly promising in practice. As the predeployment design and optimization are usually unpractical in random deployment scenarios, the global optimum of the WSN’s performance is achievable only if the topology dependent self-organizing process acquires the overview of the WSN, in which the boundary is the most important. The idea of this paper comes from the fact that contours only break on the geometrical boundary and the WSN are discrete sampling systems of real environments. By simulating a diffusion process in discrete form, the end point of semi-contours suggests the boundary nodes of a WSN. The simulation cases show the algorithm is well worked in WSN with average degree higher than 10. The boundary recognition could be very valuable for other algorithms dedicated to optimize the overall performance of WSN.


---

## Body

## 1. Introduction

There are some areas where we have interests in what is happening, but environments are hostile for a man or too costly to sending a man for the duty. Wireless sensor networks (WSN), which are usually at low cost and self-organized, are appropriate for those tasks [1, 2].Some existed algorithms assume that the sensor fields are convex in shape [3, 4]. However, such assumption is not always fulfilled. The situation of a particular interested area is often unknown. It is quite possible that the area contains some regions with poor accessibility, such as unforeseen obstacles and/or holes [5]. Thus, applying those protocols may lead to a degraded performance or suffer a failure result. Thus, recognizing the geometry of the field should be the first step of organizing WSN, which is deployed in an unknown field, to try to achieve better performances. Plotting the boundary is the most basic measure to describe a geometric shape and probably the best one. In this paper, we study the problem of revealing the global geometric feature of the sensor field, in particular, recognizing the sensor nodes on the boundary.Our viewpoint is to regard the WSN as a discrete sampling of the geometric environment. This is inspired by the fact that the WSN are used for providing intense monitoring of the environment. So, the boundaries of the sensor field usually represent the physical boundary of the underlying environments, such as walls of buildings and changes of topography. More importantly, newly appeared boundaries, which means a majority of local sensors are off duty due to destruction or power deficient, could be an indicator of emergency. For example, a wild fire in forest damages all sensors in fire line and also creates new boundary in the sensor field. An inner boundary is also an important indicator of the unhealthiness of the network, such as insufficient connectivity and coverage, revealing the locations where additional sensor nodes are required.Furthermore, bottleneck recognition [6, 7], which is vital for precise schedule over WSN, requires boundary information. And, in coverage problem, the coverage intensity near the network boundary attracts a lot of research interest [8, 9]. So, boundary recognition provides useful information for other WSN applications.


## 2. Previous Works and Assumptions

It is always easy to find the boundary when an overview is offered. For example, in Figure1, the white area represents the field and the dots represent the sensor nodes. The task should be easy if we can have a glance at one of these pictures, because the overview is provided for human brain. However, in WSN, such centralized process of acquiring the overview needs lots of communications to collect all connection information in the whole networks. The cost of doing so in WSN is extremely high in both energy and time. So, decentralized algorithm or distributed ones are required.Sensor nodes deployed in geometric areas.
(a)
(b)
(c)There are some distributed algorithms trying to recognize the boundary in the literature. They can be classified into three categories by their basic ideas: geometric-based algorithms, statistical algorithms, and topological-based algorithms.The geometric-based algorithms assume that a node of WSN realizes the exact locations of itself and the nodes in its neighborhood. Fang proposed the algorithm based on the fact that a data packet can only get stuck in a node at boundary in a geographical forwarding [10, 11]. So some boundary nodes are identified. Repeating the process of such geographical forwarding starting from different beacon nodes eventually discovers almost the complete boundary cycles. The idea is nice and clear. However, the information of location depends on locating algorithm or locating device such as GPS system. Locating algorithm certainly consumes some energy and the locating error may lead to boundary error. While the locating device is usually an energy hunger. And more, sweeping over the whole network again and again consumes lots of energy. So, the geometric based algorithm recognizes the boundary at a high cost.The information of nodes’ location definitely benefits the boundary recognition. However, the boundary recognition is also needed in the WSN which do not have the ability of locating. So statistical algorithms and topological based algorithms are developed for such WSN.Statistical algorithm assumes that the nodes are uniformly randomly deployed in sensor field. Fekete proposed an algorithm with such assumption [12]. The idea is inspired by the law of large number. According to the law, the average of the results obtained from a large number of trials should be close to the expected value and will tend to become closer as more trials are performed. In his algorithm, the deployment of other nodes is regarded as a “trial,” and the ratio of neighboring area and the whole sensing area is regarded as “expected value.” So, if lots of nodes are deployed, the number of neighbor nodes should be “total trials” × “expected value.” Thus, a node should have a number of neighbors that is close to the average degree (the average number of neighboring nodes in the whole network), unless it is on a boundary. This is because the neighboring area of a boundary node is much smaller than an interior node. The algorithm does not require any location information and gets good result in WSN with high average degree. However, the requirement of density is unrealistic: the average degree should be close or over 100 [13]. In practice, the network is often so sparse that the number of “trials” is not big enough to make the results close to “expected value.”Topological based algorithms assume that a node knows only which other nodes are connected directly [14–18]. This assumption is similar to that in this paper; especially we are inspired by Funke’s approach [17]. In this method, a group of beacons are randomly selected first. Then, after flooding, all nodes in WSN are given a “distant,” which is the hop count to the nearest beacon. In this way, there are many iso-contours of “distant” in the WSN. Finally, the nodes where the iso-contours break are marked as boundary nodes. The simulation of the algorithm shows that some interior nodes are faultily identified. This is because the value of “distant” is measured in integer; randomness of deployment may cause the “distant” of a particular node vary from x to x+1 or x-1. Such phenomenon in WSN makes it possible that interior node is faultily identified, especially in sparse networks. Wang proposed another topological based algorithm [13]. It is reported that the complete sequences of boundary nodes are identified. However, this method can only be used in the scenario that the WSN have topology holes in them. The algorithm does not find any boundary nodes in WSN which is simply connected (without holes). Furthermore, if there are some nodes faultily recognized already (this is never avoided completely), the final process, which connects distributed boundary nodes to a sequence in order to decrease the missing identification, could be a disaster as faulty identification increases massively. In a recent paper, [18] proposes another topological algorithm, which achieves good hole detection result. But its complexity is higher than the algorithm proposed in this paper.This paper proposes a distributed algorithm for recognizing the boundary of WSN, using only direct connection information. We do not assume that any location information, distance information, or angular information is collected.This paper is based on the following assumptions:(1)
the nodes in WSN are provided with limited computation ability, energy, and memory;(2)
the communication range of a node is much greater than sensing range; so, the average degree is reasonable if the sensing field is well covered;(3)
the nodes are uniformly randomly deployed in the sensing field;(4)
the nodes are deployed in a closed area;(5)
the sensing data are not required; that is, the algorithm does not require any positioning information about the nodes.The basic idea of this paper comes from an intense observation of a gas diffusion process in a closed space. We are motivated by the fact that some features of concentration field suggest the boundary of a closed space and then realize that the boundary of WSN can be recognized by simulating similar process.


## 3. An Observation of Mass Diffusion

### 3.1. The Process of Mass Diffusion

Consider the following scenario. Bounded spaceG is filled with inactive gas. For some reasons, another type inactive gas α is generated at constant rate at Y1,Y2,…,Yn, which are inside the space G. As time goes, gas α gradually spreads everywhere in the space. This process is a typical diffusion process. Let us observe that the concentration C of gas α varies from time t and position P(x,y,z) intensely in this process:
(1)C=C(P,t).
Equation (1) is continuous and two-order differentiable mathematically.Fick’s first law relates the diffusive flux to the concentration under the assumption of steady state. It postulates that the flux goes from regions of high concentration to regions of low concentration, with a magnitude that is proportional to the concentration gradient (spatial derivative):(2)j→=-D∇C,
where j→ is the diffusion flux [mol·m−2·s−1]. j→ measures the amount of substance that flows through a small area during a small time interval. D is the diffusion coefficient or diffusivity in dimensions [m2·s−1]. ∇C is the concentration gradient [mol·m−4].Equation (2) is the differential form of Fick’s first law, which shows how diffusive flux behaves locally. By integrating (2) over an infinitesimal surface S, the integral form of Fick’s fist law is derived:
(3)dJdt=-D∬S∇CdA→,
where dJ/dt is the amount of substance transferred per unit time [mol·s−1] and dA→ is an oriented surface area element [m2]. The direction is to the outward normal of the element.Equation (3) describes how substance transfers through a surface.If the surfaceS is a non-self-intersecting continuous closed surface as shown in Figure 2, Jordan-Brouwer separation theorem asserts that the surface S divides the object G (a 3-dimensional bounded closed domain) into an “interior” region g, bounded by surface S, and an “exterior” region G∖g, which consists of all other parts, so that any continuous path ends in different regions intersects S somewhere. Hence, all substance exchange between interior region g and exterior G∖g flows through S.Figure 2
Inside objectG, interior region g bounded by surface S.The net amount of substance that flows intoG in a small time interval [t1,t2] can be derived from (3) by integrating over t:
(4)J=∫t1t2∯SD∇CdA→dt=∫t1t2∭g[∂∂x(D∂C∂x)+∂∂y(D∂C∂y)+∂∂z(D∂C∂z)]dxdydzdt.In the scenario we are observing, there are a group of sourcesY={Y1,Y2,…,Yn}, which generate gas α at constant rate:
(5)F(P,t)={constantP∈Y0P∉Y.Thus, the net gain of gasα in g in time interval [t1,t2] is the sum of the gas that is generated in g and that flows into g:
(6)∫t1t2∭g[∂∂x(D∂C∂x)+∂∂y(D∂C∂y)+∂∂z(D∂C∂z)+F(x,y,z)]dxdydzdt.Meanwhile, the net gain of gasα should also be described by integrating the concentration change over time and space:
(7)∫t1t2∭g∂C∂tdxdydzdt.By the law of mass conservation, (6) equals (7) for any space g and time interval [t1,t2]:
(8)∂C∂t=DΔC+F,
where Δ is the Laplace operator.


### 3.2. Analysis in Mathematics

Considering the case introduced above, there is not any gasα in G at the very beginning:
(9)C=0on⁡G×{0}.And, as the spaceG is bounded, gas α does not spread outside G. Thus, at the boundary of space ∂G(10)∂C(P,t)∂n=0on⁡∂G×(0,t],
where n is the outward normal of ∂G.For the differential equation (8), initial condition and boundary condition are given as (9) and (10). So, there is a unique solution for any time and any spot in G. Therefore, we can simulate the diffusion process discussed above and determine the concentration value everywhere at any time.In previous works, the boundary of the spaceG is always known. How about if the boundary exists but we do not know where it is? Shall we find the boundary by observing the concentration field?Given timet, there is a concentration distribution of α in G. Denote I(v)={P∣C(P)=v}, Iless(v)={P∣C(P)<v}, and Imore(v)={P∣C(P)>v}, where v is nonextreme concentration value. So, I(v), Iless(v), and Imore(v) are all nonempty sets. I(v) is an iso-contour of concentration value v. Iless(v) and Imore(v) are two sets of points where concentration values are less or more than v.There is at least one pointPv∈I(v) on any path connecting Iless(v) and Imore(v).Proof.
LetPl∈Iless(v) and Pm∈Imore(v). Let φ:[0,1]→R3, such that φ(0)=Pl, φ(1)=Pm, and the restriction of φ to [0,1] is injective. That is, φ is a non-self-intersecting continuous curved line segment which ends with Pl and Pm. Assume, if possible, ∃φ, such that I(v)∩φ=∅.
If so, for allx∈[0,1], C(φ(x))≠v. As φ⊂G and C(P) is a continuous function on G, C(φ(x)) is a continuous function about x on [0,1]. C(φ(0))=C(Pl)<v and C(φ(1))=C(Pm)>v; by the intermediate value theorem, ∃x∈[0,1] such that C(φ(x))=v, contradicting for all x∈[0,1], C(φ(x))≠v.
Therefore, for allφ, ∃x∈[0,1] such that φ(x)∈I(v).Consequently, iso-contour never breaks inG; otherwise, there should have been paths connecting Iless(v) and Imore(v). Therefore, iso-contour either is closed surface or breaks on the boundary of space G. That is, ∂I(v)⊂∂G. In particular, if G is a 2D space, iso-contour either is closed curve or ends on the boundary of G. Thus, “P is the endpoint of an iso-contour.” ⇒ “P is on the boundary of G.”The result is encouraging. However, we should notice that “P is on the boundary of G.” ⇏ “P is the endpoint of an iso-contour.”In a map with contour, it is possible that contour is a tangent curve to the boundary of the map at somewhere, as the arrow points to in Figure3. In this case, the union of end points of all contour is almost equal to the complete boundary of G, missing very few isolated points. But in the worst case, the contour is a tangent curve to the boundary everywhere. Here is an example. The space G is circle or sphere in shape, and the source of gas α is exactly at the center. In this case, the outmost iso-contour meets the boundary exactly as shown in Figure 4.Figure 3
A map with contour [19].Figure 4
Iso-contours when source is at the center of a circle.Although the worst case happens in small probability, we should and can avoid it by generating another type of inactive gasα′ at different position and observing the iso-contour I′(v) of α′. This way, the worst case is avoided and the difference between ⋃v(∂I(v)∪∂I′(v)) and ∂G is even smaller. More generally, if there are n types of inactive gas generating in space G at different positions, the union of end points of all iso-contours and all types is almost equal to the boundary of G:
(11)∂G≈⋃v⋃n∂In(v).


## 3.1. The Process of Mass Diffusion

Consider the following scenario. Bounded spaceG is filled with inactive gas. For some reasons, another type inactive gas α is generated at constant rate at Y1,Y2,…,Yn, which are inside the space G. As time goes, gas α gradually spreads everywhere in the space. This process is a typical diffusion process. Let us observe that the concentration C of gas α varies from time t and position P(x,y,z) intensely in this process:
(1)C=C(P,t).
Equation (1) is continuous and two-order differentiable mathematically.Fick’s first law relates the diffusive flux to the concentration under the assumption of steady state. It postulates that the flux goes from regions of high concentration to regions of low concentration, with a magnitude that is proportional to the concentration gradient (spatial derivative):(2)j→=-D∇C,
where j→ is the diffusion flux [mol·m−2·s−1]. j→ measures the amount of substance that flows through a small area during a small time interval. D is the diffusion coefficient or diffusivity in dimensions [m2·s−1]. ∇C is the concentration gradient [mol·m−4].Equation (2) is the differential form of Fick’s first law, which shows how diffusive flux behaves locally. By integrating (2) over an infinitesimal surface S, the integral form of Fick’s fist law is derived:
(3)dJdt=-D∬S∇CdA→,
where dJ/dt is the amount of substance transferred per unit time [mol·s−1] and dA→ is an oriented surface area element [m2]. The direction is to the outward normal of the element.Equation (3) describes how substance transfers through a surface.If the surfaceS is a non-self-intersecting continuous closed surface as shown in Figure 2, Jordan-Brouwer separation theorem asserts that the surface S divides the object G (a 3-dimensional bounded closed domain) into an “interior” region g, bounded by surface S, and an “exterior” region G∖g, which consists of all other parts, so that any continuous path ends in different regions intersects S somewhere. Hence, all substance exchange between interior region g and exterior G∖g flows through S.Figure 2
Inside objectG, interior region g bounded by surface S.The net amount of substance that flows intoG in a small time interval [t1,t2] can be derived from (3) by integrating over t:
(4)J=∫t1t2∯SD∇CdA→dt=∫t1t2∭g[∂∂x(D∂C∂x)+∂∂y(D∂C∂y)+∂∂z(D∂C∂z)]dxdydzdt.In the scenario we are observing, there are a group of sourcesY={Y1,Y2,…,Yn}, which generate gas α at constant rate:
(5)F(P,t)={constantP∈Y0P∉Y.Thus, the net gain of gasα in g in time interval [t1,t2] is the sum of the gas that is generated in g and that flows into g:
(6)∫t1t2∭g[∂∂x(D∂C∂x)+∂∂y(D∂C∂y)+∂∂z(D∂C∂z)+F(x,y,z)]dxdydzdt.Meanwhile, the net gain of gasα should also be described by integrating the concentration change over time and space:
(7)∫t1t2∭g∂C∂tdxdydzdt.By the law of mass conservation, (6) equals (7) for any space g and time interval [t1,t2]:
(8)∂C∂t=DΔC+F,
where Δ is the Laplace operator.


## 3.2. Analysis in Mathematics

Considering the case introduced above, there is not any gasα in G at the very beginning:
(9)C=0on⁡G×{0}.And, as the spaceG is bounded, gas α does not spread outside G. Thus, at the boundary of space ∂G(10)∂C(P,t)∂n=0on⁡∂G×(0,t],
where n is the outward normal of ∂G.For the differential equation (8), initial condition and boundary condition are given as (9) and (10). So, there is a unique solution for any time and any spot in G. Therefore, we can simulate the diffusion process discussed above and determine the concentration value everywhere at any time.In previous works, the boundary of the spaceG is always known. How about if the boundary exists but we do not know where it is? Shall we find the boundary by observing the concentration field?Given timet, there is a concentration distribution of α in G. Denote I(v)={P∣C(P)=v}, Iless(v)={P∣C(P)<v}, and Imore(v)={P∣C(P)>v}, where v is nonextreme concentration value. So, I(v), Iless(v), and Imore(v) are all nonempty sets. I(v) is an iso-contour of concentration value v. Iless(v) and Imore(v) are two sets of points where concentration values are less or more than v.There is at least one pointPv∈I(v) on any path connecting Iless(v) and Imore(v).Proof.
LetPl∈Iless(v) and Pm∈Imore(v). Let φ:[0,1]→R3, such that φ(0)=Pl, φ(1)=Pm, and the restriction of φ to [0,1] is injective. That is, φ is a non-self-intersecting continuous curved line segment which ends with Pl and Pm. Assume, if possible, ∃φ, such that I(v)∩φ=∅.
If so, for allx∈[0,1], C(φ(x))≠v. As φ⊂G and C(P) is a continuous function on G, C(φ(x)) is a continuous function about x on [0,1]. C(φ(0))=C(Pl)<v and C(φ(1))=C(Pm)>v; by the intermediate value theorem, ∃x∈[0,1] such that C(φ(x))=v, contradicting for all x∈[0,1], C(φ(x))≠v.
Therefore, for allφ, ∃x∈[0,1] such that φ(x)∈I(v).Consequently, iso-contour never breaks inG; otherwise, there should have been paths connecting Iless(v) and Imore(v). Therefore, iso-contour either is closed surface or breaks on the boundary of space G. That is, ∂I(v)⊂∂G. In particular, if G is a 2D space, iso-contour either is closed curve or ends on the boundary of G. Thus, “P is the endpoint of an iso-contour.” ⇒ “P is on the boundary of G.”The result is encouraging. However, we should notice that “P is on the boundary of G.” ⇏ “P is the endpoint of an iso-contour.”In a map with contour, it is possible that contour is a tangent curve to the boundary of the map at somewhere, as the arrow points to in Figure3. In this case, the union of end points of all contour is almost equal to the complete boundary of G, missing very few isolated points. But in the worst case, the contour is a tangent curve to the boundary everywhere. Here is an example. The space G is circle or sphere in shape, and the source of gas α is exactly at the center. In this case, the outmost iso-contour meets the boundary exactly as shown in Figure 4.Figure 3
A map with contour [19].Figure 4
Iso-contours when source is at the center of a circle.Although the worst case happens in small probability, we should and can avoid it by generating another type of inactive gasα′ at different position and observing the iso-contour I′(v) of α′. This way, the worst case is avoided and the difference between ⋃v(∂I(v)∪∂I′(v)) and ∂G is even smaller. More generally, if there are n types of inactive gas generating in space G at different positions, the union of end points of all iso-contours and all types is almost equal to the boundary of G:
(11)∂G≈⋃v⋃n∂In(v).


## 4. Simulation of Diffusion in WSN for Boundary Recognition

### 4.1. Discrete Form of Diffusion

A spaceG is uniformly divided into M subspaces. G=⋃i=0Mgi, gi∩gj=∅, i≠j. As G is uniformly divided, denote A as joint area of adjacent subspace, x as distance between them, and V as volume of a subspace. Consider the diffusion process in subspace gi, which is surrounded by g1,g2,…,gn, (see Figure 5).Figure 5
Subspacegi surrounded by g1,g2,…,gn.Similar to (3), the net gain from adjacent subspace by diffusion is
(12)dJidt=∑j=1nDA(Cj-Ci)x.And the change of concentration is due to diffusion in adjacent subspace and the source effect:(13)dCidt=F+∑j=1nDA(Cj-Ci)Vx,
where
(14)F={positiveconstant,ifthereissourceofgasingi0,otherwise.So,(15)lim⁡Δt→0Ci(t+Δt)-Ci(t)Δt=F+DAVx∑j=1n(Cj(t)-Ci(t))lim⁡Δt→0Ci(t+Δt)=lim⁡Δt→0[FΔt+DAΔtVx∑j=1nCj(t)+(1-nDAΔtVx)Ci(t)].LetEi(t)=(1/n)∑j=1nCj(t) as average concentration of gi’s adjacent subspace and k=nDAΔt/Vx. If Δt→0, then k∈(0,1) and
(16)Ci(t+Δt)≈kEi(t)+(1-k)Ci(t)+FΔt.The concentration ofgi after time interval Δt is a weighted average of current concentration of gi and its surroundings, plus a positive constant if there is source of gas in it.


### 4.2. Simulating Diffusion in WSN

In a WSN application, a lot of sensor nodes are deployed in a sensing area. Our viewpoint is to regard the WSN as a discrete sampling of the environment. Every sensor node is a sample of local area. So, we virtually start a simulation of multigas diffusion process.Assuming thatw types of gas are spreading in the area, the local concentration of them at sensor node Ni is Ci=[Ci1,Ci2,…,Ciw]. The nodes that can communicate directly with Ni represent the adjacent subspace. Randomly, select w groups of nodes as diffusion source of w types of gas.At the very beginning, for alli, Ci(0)=0. Then the diffusion process starts.At timet, sensor node Ni broadcasts its current concentration vector Ci(t). Its 1-hop neighbors will receive this data package. Meanwhile, Ni receives the data packages from its neighbors C1(t),C2(t),…,Cn(t). Applying (16) and when Δt=1,
(17)Ci(t+1)=(1-k)Ci(t)+kEi(t)+F,
where
(18)Ei(t)=1n∑j=1nCj(t).F
=
[
0
,
…
,
0
︸
u
-
1
,
c
,
0
,
…
,
0
︸
w
-
u
] if Ni is selected as source of the uth type of gas. F=0 if Ni is not source of any type.


### 4.3. Semi-Iso-Contours and Their End Points

After repeating several times, the diffusion process spreads virtual gas everywhere in the sensor field. Figure6(a) shows the concentration distribution of one type of gas in a sensor field. Then, we can draw semi-iso-contours. The reason why we call it semi-iso-contour rather than iso-contour is that there are seldom absolute equalities in such discrete sampling system. Therefore, approximately equality is employed instead. The criteria we used for approximately equality in 1-hop neighbors are that Ciu≈Cju if and only if |Ciu-Cju|<0.3max⁡k=0n|Ciu-Cku|. Figure 6(b) shows semi-iso-contours in the sensor field. And Figure 6(c) displays all end points of semi-iso-contours.A concentration map and semi-iso-contours. The virtual sources are marked as star. The hotter colour represents higher concentration value, while the cooler colour represents lower concentration value.
(a)
(b)
(c)The end points of semi-iso-contours roughly show the boundary of the sensor field in Figure6(c). But, there are both some faulty recognitions and miss recognitions. This is because the WSN are a discrete sampling system rather than a continuous physical system. To increase the quality of boundary recognition, we shall use information from other types of gas. In our simulation, w=10; that is, 10 types of virtual gas are spreading simultaneously. Figure 7 show semi-iso-contours and their end points of the other 9 types of virtual gas.Semi-iso-contours and their end points of the other 9 types of virtual gas.
(a)
(b)
(c)
(d)
(e)


### 4.4. Final Results of Boundary Recognition

Reading Figure7, we can conclude that the inner nodes are much less probable to be the end points of semi-iso-contours than the boundary nodes. So, if a node is an end point of semi-iso-contour for multiple times in different types of virtual gas, it is very possible that it is located at the boundary of the WSN. When we pick all nodes that are end points at least 3 times out of 10, the boundary recognition is shown in Figure 8.Figure 8
Final result of boundary recognition.


### 4.5. Complexity Analysis

Our approach for boundary recognition consists of 3 steps as follows:(1)
simulating the process of diffusion;(2)
drawing semi-iso-contours;(3)
determining whether to be an end point or not.The 1st step repeats multiple times of communication in neighborhood and calculation. In each repeat, every node should communicate with all its 1-hop neighbors and updatew dimensional vector Ci(t) to Ci(t+1). This is O(nw) in time, where n is the number of 1-hop neighbors. The process should repeat O(h) times in order to guarantee that all nodes are affected by virtual diffusion, where h is the maximum hop counts between 2 nodes in the sensor field. h is decided by the range of the sensor field and the communication range of sensor nodes, which is constant after deployment. So the time complexity for the first step is O(nw)O(1)=O(nw).The 2nd step requires a comparison in neighborhood. That isO(nw) in time.The 3rd step requires a count overw types. That is O(w) in time.So, the overall complexity in time isO(nw).In all three steps, the nodes record current concentration value of adjacent nodes and itself. All historical data are discarded. So the overall complexity in memory isO(nw).A recent paper proposes a topological based algorithm [18], which achieves good hole detection result. In this paper, Dijkstra’s shortest path algorithm is used to construct manifold, so the total complexity is at least O(N2), where N is the number of all sensors in the field. In comparison, the algorithm we proposed is much less complex.


## 4.1. Discrete Form of Diffusion

A spaceG is uniformly divided into M subspaces. G=⋃i=0Mgi, gi∩gj=∅, i≠j. As G is uniformly divided, denote A as joint area of adjacent subspace, x as distance between them, and V as volume of a subspace. Consider the diffusion process in subspace gi, which is surrounded by g1,g2,…,gn, (see Figure 5).Figure 5
Subspacegi surrounded by g1,g2,…,gn.Similar to (3), the net gain from adjacent subspace by diffusion is
(12)dJidt=∑j=1nDA(Cj-Ci)x.And the change of concentration is due to diffusion in adjacent subspace and the source effect:(13)dCidt=F+∑j=1nDA(Cj-Ci)Vx,
where
(14)F={positiveconstant,ifthereissourceofgasingi0,otherwise.So,(15)lim⁡Δt→0Ci(t+Δt)-Ci(t)Δt=F+DAVx∑j=1n(Cj(t)-Ci(t))lim⁡Δt→0Ci(t+Δt)=lim⁡Δt→0[FΔt+DAΔtVx∑j=1nCj(t)+(1-nDAΔtVx)Ci(t)].LetEi(t)=(1/n)∑j=1nCj(t) as average concentration of gi’s adjacent subspace and k=nDAΔt/Vx. If Δt→0, then k∈(0,1) and
(16)Ci(t+Δt)≈kEi(t)+(1-k)Ci(t)+FΔt.The concentration ofgi after time interval Δt is a weighted average of current concentration of gi and its surroundings, plus a positive constant if there is source of gas in it.


## 4.2. Simulating Diffusion in WSN

In a WSN application, a lot of sensor nodes are deployed in a sensing area. Our viewpoint is to regard the WSN as a discrete sampling of the environment. Every sensor node is a sample of local area. So, we virtually start a simulation of multigas diffusion process.Assuming thatw types of gas are spreading in the area, the local concentration of them at sensor node Ni is Ci=[Ci1,Ci2,…,Ciw]. The nodes that can communicate directly with Ni represent the adjacent subspace. Randomly, select w groups of nodes as diffusion source of w types of gas.At the very beginning, for alli, Ci(0)=0. Then the diffusion process starts.At timet, sensor node Ni broadcasts its current concentration vector Ci(t). Its 1-hop neighbors will receive this data package. Meanwhile, Ni receives the data packages from its neighbors C1(t),C2(t),…,Cn(t). Applying (16) and when Δt=1,
(17)Ci(t+1)=(1-k)Ci(t)+kEi(t)+F,
where
(18)Ei(t)=1n∑j=1nCj(t).F
=
[
0
,
…
,
0
︸
u
-
1
,
c
,
0
,
…
,
0
︸
w
-
u
] if Ni is selected as source of the uth type of gas. F=0 if Ni is not source of any type.


## 4.3. Semi-Iso-Contours and Their End Points

After repeating several times, the diffusion process spreads virtual gas everywhere in the sensor field. Figure6(a) shows the concentration distribution of one type of gas in a sensor field. Then, we can draw semi-iso-contours. The reason why we call it semi-iso-contour rather than iso-contour is that there are seldom absolute equalities in such discrete sampling system. Therefore, approximately equality is employed instead. The criteria we used for approximately equality in 1-hop neighbors are that Ciu≈Cju if and only if |Ciu-Cju|<0.3max⁡k=0n|Ciu-Cku|. Figure 6(b) shows semi-iso-contours in the sensor field. And Figure 6(c) displays all end points of semi-iso-contours.A concentration map and semi-iso-contours. The virtual sources are marked as star. The hotter colour represents higher concentration value, while the cooler colour represents lower concentration value.
(a)
(b)
(c)The end points of semi-iso-contours roughly show the boundary of the sensor field in Figure6(c). But, there are both some faulty recognitions and miss recognitions. This is because the WSN are a discrete sampling system rather than a continuous physical system. To increase the quality of boundary recognition, we shall use information from other types of gas. In our simulation, w=10; that is, 10 types of virtual gas are spreading simultaneously. Figure 7 show semi-iso-contours and their end points of the other 9 types of virtual gas.Semi-iso-contours and their end points of the other 9 types of virtual gas.
(a)
(b)
(c)
(d)
(e)


## 4.4. Final Results of Boundary Recognition

Reading Figure7, we can conclude that the inner nodes are much less probable to be the end points of semi-iso-contours than the boundary nodes. So, if a node is an end point of semi-iso-contour for multiple times in different types of virtual gas, it is very possible that it is located at the boundary of the WSN. When we pick all nodes that are end points at least 3 times out of 10, the boundary recognition is shown in Figure 8.Figure 8
Final result of boundary recognition.


## 4.5. Complexity Analysis

Our approach for boundary recognition consists of 3 steps as follows:(1)
simulating the process of diffusion;(2)
drawing semi-iso-contours;(3)
determining whether to be an end point or not.The 1st step repeats multiple times of communication in neighborhood and calculation. In each repeat, every node should communicate with all its 1-hop neighbors and updatew dimensional vector Ci(t) to Ci(t+1). This is O(nw) in time, where n is the number of 1-hop neighbors. The process should repeat O(h) times in order to guarantee that all nodes are affected by virtual diffusion, where h is the maximum hop counts between 2 nodes in the sensor field. h is decided by the range of the sensor field and the communication range of sensor nodes, which is constant after deployment. So the time complexity for the first step is O(nw)O(1)=O(nw).The 2nd step requires a comparison in neighborhood. That isO(nw) in time.The 3rd step requires a count overw types. That is O(w) in time.So, the overall complexity in time isO(nw).In all three steps, the nodes record current concentration value of adjacent nodes and itself. All historical data are discarded. So the overall complexity in memory isO(nw).A recent paper proposes a topological based algorithm [18], which achieves good hole detection result. In this paper, Dijkstra’s shortest path algorithm is used to construct manifold, so the total complexity is at least O(N2), where N is the number of all sensors in the field. In comparison, the algorithm we proposed is much less complex.


## 5. Case Study

The algorithm discussed above is applied in different sensor fields. The results are shown in Figure9.Boundary recognition in multiple cases. (a) 3023 nodes with average degree 13.1; (b) 2094 nodes with average degree 12.6; (c) 2381 nodes with average degree 13.0; (d) 2115 nodes with average degree 12.5; (e) 2024 nodes with average degree 13.4; (f) 1311 nodes with average degree 13.2; (g) 6811 nodes with average degree 13.3.In all these cases, the nodes that are recognized as boundary nodes generally cover the geometrical boundary of the sensor fields. A few inner nodes, which are at least 1-hop range away from actual geometrical boundary, are faultily identified. Table1 is a statistic of faulty recognition.Table 1
Statistics of faulty recognition.
Figure9(a)
Figure9(b)
Figure9(c)
Figure9(d)
Figure9(e)
Figure9(f)
Figure9(g)
Number of nodes
3023
2094
2381
2115
2024
1311
6811
Inner nodes
2468
1402
1866
1448
1738
1065
5618
Faulty recognition
9
25
2
18
13
9
2
Faulty rate (%)
0.36
1.78
0.08
1.24
0.7
0.85
0.04It is predictable that the result of boundary recognition is better if the average degree is higher, because whenn→∞, the discrete sampling system tends to continuous system. In the other hand, the sparseness of WSN challenges the algorithm proposed in this paper. The result in a same area as case (a) in Figure 9 with lower average degree is shown in Figure 10. And the relation between faulty rate and average degree is shown in Figure 11 faulty rate versus average degree.Boundary recognition in sparse WSN. (a) 10.9 in average degree and (b) 8.9 in average degree.
(a)
(b)Figure 11
Faulty rate versus average degree.When faulty rate increases up to 5% or higher (Figure10(b)), the recognition result is worthless. Thus, the algorithm proposed in this paper should be only applied in the WSN with average degree higher than 10. Funke tests the algorithm in sparse WSN [17]. The testing area is a circle hole in square. The comparison shown in Figure 12 indicates that the result of our algorithm at average degree of 10 is comparable with Funke’s result at average of 18 and is much better than Funke’s result at average degree of 10.A comparison between algorithms. (a–d) Funke’s algorithm with average degree at 5 in (a), 10 in (b), 18 in (c), and 39 in (d). The black dots are identified as boundary nodes, while gray ones are inner nodes. (e)–(f) Our algorithm with average degree at 10.
(a)
(b)
(c)
(d)
(e)
(f)


## 6. Conclusion

In this paper, a distributed algorithm for boundary recognition in WSN is proposed. The idea comes from the facts that iso-contours only break on the geometrical boundary and the WSN is a discrete sampling system of real environment. Then, we virtually start a diffusion process to create concentration gradient field in WSN, and finally the nodes that are often identified as end points of semi-iso-contours are regarded as boundary nodes. The simulation results show that the algorithm works well for the WSN with average degree over 10. Further, as diffusion in 3D space is well studied, our algorithm is potentially to be improved to recognize boundary of a 3D WSN, which is also a hot research topic [8, 20].



---

*Source: 236279-2014-06-22.xml*