Wireless Sensor Networks for Heritage Object Deformation Detection and Tracking Algorithm

3.2.1. Algorithm of the Automatic Construction of the Connected Core (ACCC)

We assume that all of the nodes in the sensor networks can communicate effectively within the same communication range. Two nodes are adjacent if they are within the communication range of each other; actually, an adjacent link between two nodes is symmetrical. Therefore, the topology of a sensor network can be a simple connected undirected graph G = (V, E), where V is the set of vertices constituted by all nodes and E is the edge sets of all links. Based on these assumptions, we define the following three concepts as a basis to present our ACCC algorithm.

Definition 1 (core): Given a graph G = (V, E), where V is the vertices' sets of sensor nodes and E is the edge sets of all links, the node set C of G = (C⊆V) is a core if and only if C satisfies that for any node p in V, p either in C or p is a neighbor of the node q in C.

Definition 2 (connected core): Given a graph G = (V, E), the node set C of the graph G = (C ⊆V) is a connected core only if C satisfies the following conditions: The subgraph derived from C is a connected graph, and C is a key node set of graph G. For example, the connected key node set is constructed by the cluster head (with red squares) and the gateway (blue hollow triangle or practice triangle) of the sensor networks in Figure 1. The practice triangles in Figure 1 denote both the gateway and domain boundary sensors (Section 3.3). The practice dots represent the domain-boundary-sensors (Section 3.3), and the green hollow dots are the ordinary sensor nodes.

Definition 3 (domain): For the random sensor node p, we assume that the coordinate of p relative to the sink node S is (x, y), sink node S, and all of the sensor nodes have the same communication radius r, then p belongs to the domain (m, n) if and only if the following equation holds: $m=\left[x/\frac{r}{\sqrt{2}}\right]$, $n=\left[y/\frac{r}{\sqrt{2}}\right]$. Where “/” denotes the division operator; “[]” is the integer operators for taking a valuegreater than or equal to an integer.

For example, if r = 15, the geographic coordinates of Node A are (40, 40); then A_x = 4, A_y = 4. Therefore, A belongs to the domain (4,4). We assume that the geographic coordinates of B are (51, 53), B_x = 5, B_y = 5, so B belongs to the domain (5,5), instead of (4,4).

For any sensor node p, we assume that the geographical coordinates are (x, y). All of the nodes, including the sink node S, have the same communication range with a radius of r. For any sensor node p, we can calculate their respective domain according to Definition 3 and give the following ACCC algorithm. We required that the ACCC must be operated in the connectivity core C given in Definition 3:

We explain the ACCC Algorithm 2 as follows. In Step 2, every node p periodically exchanges the comprehensive state information with its adjacent nodes. The comprehensive state information comprises three parameters:

(i)

S_p: the current status of node p (every node has three kinds of statuses: domain head, gateway or ordinary member);

(ii)

E_p: the remaining energy of p;

(iii)

G_p: the domain of p;

(iv)

(x,y): the geographical coordinates of p. After this operation, each node can get the adjacent nodes' information, such as the status of their neighbor nodes, the residual energy, their domain, the straight-line distance to the neighbor node and others.

In Step 3, initially, the status of the sink node is the domain head, while the others are members. In every cycle, node p will calculate its new status according to the following rules by its neighbor's information, such as the status S_p, the energy E_p and G_p. If there is no domain head in the G_p, the node with the largest residual energy in the G_p will be selected as the domain head of this domain. Otherwise, if p is neither a domain head and gateway nor the neighborhood node of other domain, p is the gateway. In Step 4, when the nodes get the sensing data, the data will be delivered directly to the domain head of the domain.

3.2.2. Connectivity Analysis

We can deduce Theorems 1 and 2 by Definition 3:

Theorem 1:

Assume the sink node S and all sensor nodes in the sensor network have the same communication radius r; there is the unique division of domain that satisfied the formula in Definition 3.

Theorem 2:

Any two sensor nodes in the same domain are adjacent nodes.

Proof: According to Definition 3, the domain is a district of square, and the maximum distance between any two nodes of the region is $\sqrt{{\left(\frac{r}{\sqrt{2}}\right)}^2+{\left(\frac{r}{\sqrt{2}}\right)}^2}=r$. Any two nodes are within the radius of each other's effective communication, so any two sensor nodes in the same domain are adjacent nodes.

As shown in Figure 2, let r be the communication radius of the sensor node; the domain is actually an inscribed square of the circle whose radius is r/2. The distance of any two points in the inscribed square is less than r, so that all of the nodes within the inscribed square can communicate with each other; thus, any two nodes within an inscribed square are connected.

According to the algorithm ACCC we know that ACCC is fully distributed.

Theorem 3

Assuming the graph G = (V, E) is a simple, connected, undirected graph, the node set ψ = {p | p is the domain head or gateway node and p ∈ V} that is obtained from the algorithm ACCC is a connected core of graph G.

Proof: First of all, we can see from Theorem 2 and Step 3 of the algorithm ACCC that every node in the set ψ is either a domain head node or its neighbor node is one of the domain heads at least; namely, it is a neighbor with some domain head node. Therefore, the set ψ is a core of the graph G. We prove that ψ is connected by induction as follows.

Let p and q be any two domain head nodes of ψ, that is to say, p,q∈ ψ. We have assumed that all of the sensor nodes have the same communication radius, and for convenience of expression, we assume that the communication radius is one unit length; so, the distance between p and q is the length of the shortest path between p and q, denoted as d(p,q). Since the graph Gis connected, d(p,q)<R (R is a real number), and d(p,q) is a finite integer.

(1)

(i) If d(p,q) = 1, we can deduce that p and q are adjacent, so they are directly reachable. We can deduce that ψ is connected.

(ii) If d(p,q) = 2, namely there is a path (p, r, q) in G, because of d(p, q) = 2; therefore, p and q are not adjacent. From Theorem 2, we know that p and q do not belong to the same domain. Because r is the neighbor of p and q, from Step 3.2 of the ACCC algorithm, if r is not the domain head, then r must be the gateway; therefore, r ∈ ψ. We can deduce that ψ is connected. (iii) If d(p,q) = 3, namely there is a path (p,r₁,r₂,q) in G. For the reason of d(p,r₂) = 2, p and q are not adjacent, and we know that p and r₂ do not belong to the same domain from Theorem 2. From Step 3.2 of the ACCC algorithm, we know that if r₁ is not a domain head, r₁ must be the gateway, and r₁ is the neighbor of p and r₂; so r₁ ∈ ψ. For the same reason, since d(r₁,q) = 2, we know that r₂ ∈ ψ. We can deduce that ψ is connected.

(2)

Assume that ψ is connected when d(p,q) = m(m > 3).

(3)

For d(p,q) = m + 1, there is a path (p,r₁,r₂,…,r_m,q) in G. ψ is the core of graph G, and we can deduce that r₂ is the domain head or r₂ are neighbors of a domain head r in ψ. We can deduce d(p,r) ≤ 3. The proof of Step 1 shows that node p and r are reachable in ψ, but d(r,q) ≤ m; the induction assumption shows that node p and r are reachable within ψ. We can deduce ψ is connected.

From Theorem 3, we know that the nodes of set ψ build a connected core, and the connected core ψ is constituted of domain head nodes and gateway nodes. The Skyline query message and resulting data can be forwarded along the nodes in ψ. Compared to the entire network, the number of nodes in the ψ is much less, which can dramatically reduce network traffic.

3.3.1. Finding Boundary Sensors (FBS) Algorithm

Let all of the nodes in a domain represent the subset S of n-dimensional space R, and the DH (domain head) distinguishes the boundary sensors among them by using the finding boundary sensors (FBS) algorithm in Algorithm 3.

Definition 4, Rotation direction of the path: Let o = (x_o,y_o), p = (x_p,y_p), q = (x_q,y_q) are any three nodes in the domain, vector D(o,p,q) denotes the rotation direction of the path.

If D > 0, then the path <o,p,q,o> forms an anti-clockwise loop; if D < 0, then the path (o,p,q,o) forms a clockwise loop; if D = 0, o, p, q are collinear.

We first identify the smallest y coordinate of nodes in S, assume p₀ and establish a coordinate axis whose origin is p₀ (if two nodes p_i and p_j have the same smallest y coordinate and p_i.x<p_j.x, we select p_j as its origin). The other nodes are mapped to the p₀ origin coordinate axis system. After mapping all of the nodes into the p₀ origin coordinate axis system, we compute all of the node's slope and sort all of the nodes in ascending order according to the node's slope and get the sorted nodes set T = {p₁,p₂,âĂę.p_n}, where p₁ and P_n have the smallest and largest slope, respectively.

Second, we establish the stack ST(S), which is initialized to ST(S) = {P_n, p₀}. Without loss of generality, We assume that at a time, the ST(S) = {P_n, p₀…p_i,p_j,p_k}, where p_k is on the top of ST, and the nodes in ST have constituted a semi-closed convex polygon (Figure 4a); p_l is the next node in the T.

If the rotation direction D (p_j,p_k,p_l) >0, then we push p_l into stack ST(S), since the path <p_j, p_k, p_l> forms an anti-clockwise loop and <p_j, p_k, p_l> forms a convex polygon, and the p_k, p_l are a convex polygon edge. If D (p_j,p_k,xp_l) >0, then we pop p_k out of stack ST(S) (Figure 4b,c), since the path <p_j, p_k, p_l> forms an clockwise loop and p_k, p_l are not a convex polygon edge. Finally, the nodes in ST are the boundary sensors that determine the boundaries of a heritage object.

3.3.2. Boundary Detection

3.3.3. Boundary Tracking and Deformation Detection

4.2. Simulation Experiment

We analyze the time efficiency of EffeHDDT by recording the average processing time for issuing a query to the network to obtain all of the results. All of the simulation experiments run in the network simulator 2 (ns2) [38].

We assume that the sensor network is randomly deployed in a simulated 1000 m × 1000-m sensing field. The radio range of each sensor was assumed to be 3 m. Two heritage sits/objects are simulated to be detected and tracked within the sensing field, a rectangle of 200 m × 100 m and a circle with a radius of 100 m, respectively. We assume that the rectangular and circular objects are initially centered at coordinates of (500, 600) and (200, 200), respectively. The sink is located at coordinates (0, 0). In order to simulate the deformation and collapse of the heritage object, the width and length of the rectangular heritage object and the radius of the circular heritage object increase by 0.1 m in each time slot, and the system generates a tension value V randomly at the same time, when the surface pressure exceeds V, the heritage object is split into multiple small parts and moves around with a random speed.

4.2.1. Communication Cost

In this section, we analyze the communication costs incurred in detecting and tracking the boundary deformation and collapse of the heritage object. The communication cost is defined as the total number of data packets broadcast in establishing the boundary nodes, integrating the local boundary information and then disseminating this information to the sink. In the simulations of the message cost, the sensing field is assumed to contain a total of 2,500 sensors. We compared the communication cost of our EffeHDDT method with those of both CODA and DCS in three different boundary sizes in Figures 10 and 11. We first introduce the simulation setup. In Figure 10a–10c, we adopt a maximum number of 80, 160 and 220 boundary sensors with dynamic clusters in DCS, and 50 static and 50 domains in both CODA and EffeHDDT. In Figure 11a–11c, we adopt 50, 100 and 150 dynamic clusters without limitation of the size in each dynamic cluster in DCS, and 50 static clusters and 50 domains in both CODA and EffeHDDT. Then, comparing the three schemes, the overall trend in both Figures 10 and 11 is that EffeHDDT results in a considerably lower communication overhead, since EffeHDDT constructs the connected core and the DHs in the domains determine the boundary sensors of the two moving heritage objects. By contrast, in DCS and CODA, the boundary sensors are determined by requiring every sensor detecting the emergence of the object to communicate with all of its one-hop neighboring sensors. Dynamic clusters are then built by performing an extensive message exchange among all of the boundary sensors. Therefore, the total message costs of both DCS and CODA are very high.

The communication costs for control message broadcast changing with diffusion speeds are analyzed in Figure 12a–12c. The simulation setup is that we adopt 100, 150 and 200 static clusters in EffeHDDT and 100, 150 and 200 domains in CODA, and the width and length of the rectangular heritage object and the radius of the circle are increased by 0.1 m in each period of diffusion. It can be seen that the EffeHDDT has the least (best) communication cost. The reason is that when the control message in transmitted in the connected core in the EffeHDDT, the average communication cost occurs in domains less than the CODA when tracking diffused objects with a large size.

4.2.2. The Precision of the Estimated Boundary

We define the precision of the estimated boundary as the boundary precision ratio (e/a) with a range of [0, 1]; that is, the actual boundary (a) is divided by the estimated boundary (e). We use the number of sensors within the actual heritage object boundary, representing the actual boundary, and the number of sensors enclosed by the estimated heritage object boundary as the estimated boundary. The precision of the estimated boundary is one if the number of sensors enclosed by the estimated heritage object boundary is equal to the number of sensors within the actual heritage object boundary. In fact, the number of sensors enclosed by the estimated heritage object boundary is less than the number of sensors within the actual heritage object boundary. Thus, the greater the value of the boundary precision ratio (e/a), the greater is the precision of the estimated boundary.

Figure 13a–13c compares the estimation boundary precision ratio of EffeHDDT, CODA and DCS in networks with three sensor densities (2000, 2500 and 3000 nodes). The common trend is that the three schemes retain an approximately constant estimation performance as the heritage size increases. For any given time slot, it can be seen that the heritage object boundary precision of the three schemes increases as the node density increases. Furthermore, we have observed that the EffeHDDT consistently outperforms both CODA and DCS, since EffeHDDT locates the boundary by finding the minimum convex polygon that contains the heritage object.