# Weight-Aware Sensor Deployment in Wireless Sensor Networks for Smart Cities

Authors: Mingshan Xie; Yong Bai; Zhuhua Hu; Chong Shen
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

During the construction of wireless sensor networks (WSNs) for smart cities, a preliminary survey of the relative criticalness within the monitored area can be performed. It is a challenge for deterministic sensor deployment to balance the tradeoff of sensing reliability and cost. In this paper, based on the sensing accuracy of the sensor, we establish a reliability model of the sensing area which is divided into sensing grids, and different weights are allocated to those grids. We employ a practical evaluation criterion using seesaw mapping for determining the weights of sensing grids. We further formulate and solve an optimization problem for maximizing the trust degree of the WSNs. With our proposed method, the efficient deployment of sensors can be realized. Simulation results show that our proposed deployment strategy can achieve higher trust degree with reduced sensor deployment cost and lower number of sensors at a certain miss probability threshold.


---

## Body

## 1. Introduction

There are many wireless sensor networks (WSNs) applications in smart cities, such as residential security, factory pollution monitoring, elevator monitoring, lamp control, power grid monitoring, fire monitoring, medical care, building monitoring, and air monitoring. During the construction of wireless sensor networks for smart cities, we can survey the terrain situations in advance. In the monitored region, data in some areas is more critical. For instance, in traffic accident monitoring, some sections, such as curves and ramps, are accident-prone areas. Since the accuracy of the sensors cannot be the same in each monitored area, the data collection capability of the critical areas should be considered in the deployment of sensors in these regions.At present, there are many research works about sensor deployment. They focus on various aspects. Some studies are about routing of senses with the consideration of the energy problem [1]. The authors have optimized the sensor placement for indoor localization [2]. In the process of sensor deployment, the weight of the sensing region should be considered. In [3], Zou and Chakrabarty considered the most vulnerable regions in the sensor field when designing algorithms. In [4], the authors think it is necessary to locate the sensor nodes in the field of interest which refers to the preferred field of coverage. It is of practical significance that the sensor deployment should consider the criticalness of each subregion of the sensing area. It is not necessary to deploy sensors in every corner. We need to weigh the criticalness of each subregion in the monitored region in order to ensure the reliability of the data collected.In our work, we present an optimization framework for sensor deployment. The proposed approach aims to improve the comprehensive performance of the sensor network and ensure the effective collection of data.The contributions of this paper are listed as follows.( 1 ) In order to collect data effectively and reliably, considering the actual engineering requirements, this paper proposes a weight-aware sensor deployment method based on the weight of each sensing grid in the monitored region, which is the meshed region according to the sensor’s sensing region.( 2 ) In this paper, the weight of the sensing grid is estimated from three aspects: the probability of abnormal events, the consequence of abnormal events, and the tolerance time of abnormal events. A seesaw mapping is proposed to calculate the weights by taking into account the combined effect of the influencing factors, the cost of damage resulting from an abnormal event, and the tolerance time of an abnormal event.( 3 ) In this paper, the sensing accuracy and coverage degree are synthesized and the sensing trust degree model of the whole WSNs is proposed by taking the weight of sensing grid into account.( 4 ) Considering the fact that sensing areas are often subject to obstacles and sensing accuracy is limited, the corresponding algorithms are proposed, which makes the sensing trust degree calculation model more widely useful.The remainder of this paper is organized as follows. In Section2, we review prior research on the WSNs coverage and deployment. The model for the optimized sensor deployment is proposed in Section 3, and the estimation for the weight is in Section 4. The computing for the sensing trust degree of whole WSNs is also given in detail in Section 5. In Section 6, we describe the weight-aware sensor deployment algorithms in detail. In Section 7, we present the simulation results to evaluate the network performance for the proposed algorithms. Finally, we summarize the main results and give concluding remarks in Section 8.


## 2. Related Work

When sensor nodes are deployed in the monitored area, it is critical to calculate the weight of the sensing region. We divide the sensing region into many grids. An irregular sensor field is modeled as a collection of grids. The sensing matrix is formed by the weights of the sensing grids. Much research has considered dividing the sensing region into many grids. Xiao and Zhang proposed a divide-and-conquer-based surveillance framework, in which a large surveillance area is divided into small areas by critical points and critical lines [5]. In [6], the authors consider an optimization problem of how to partition the given field into multiple parcels and to deploy sensor nodes in some selected parcels such that the field information covered by the deployed sensor nodes meets the requirement. In [7], the performance analysis of different grid types (e.g., triangle, square, pentagon, hexagon, heptagon, and octagon) is discussed by computing their coverage area and efficient coverage area ratios.In the smart cities, sensor deployment must take into account the nature of the terrain, for example, obstacles such as buildings and trees in the line of vision for IR sensors, uneven surfaces and elevations for hilly terrains, redundancy due to the likelihood of sensor failures, and the power needed to transmit information between deployed sensors and between a deployed sensor and the cluster head [8].Sensor deployment methods consider obstacles. In [9], the authors develop a series of mechanisms to handle the obstacles in the 3D environment and propose a greedy heuristic. Chang et al. [10] presented the efficient obstacle-resistant robot deployment (ORRD) algorithm, which involves the design of a node localization policy, a serpentine movement policy, obstacle-handling rules, and boundary rules.To ensure the efficient collection of data, the minimum reliability of wireless sensor networks needs to be considered. Long et al. [11] present an efficient data gathering scheme that guarantees the quality of service and optimizes the following network performance metrics as well as the end-to-end reliability in WSNs. In [12], Deif and Gadallah proposed an ant colony optimization (ACO) algorithm to solve the minimum cost reliability constrained sensor node deployment problem.In summary, there has been a lot of work on the sensor deployment of the WSNs. Some papers are to solve the coverage problem [13–16]. However, most of the researches did not discuss the weight of the sensing field in detail. In fact, the weight of the sensing field has a great influence on the reliability and accuracy of data sampling. The relationship between factors which are involved in the estimation of weights is complicated. In order to solve this problem, we develop a novel seesaw mapping. The major issue of deploying sensors is equivalent to the problem of finding the location combination of the sensors. Considering the weights, we proposed a series of weight-aware sensor deployment algorithms in three cases which are the given total number of sensors, minimum sensing reliability, and some obstacles in the sensing region.


## 3. Deployment Model

The deployment of the sensor network should ensure that all the monitored regions are covered. The number of sensors and the cost of the network are also considered. We can estimate the covered area and the position of the sensors using the method based on the grids. The monitored region is divided into several grids in which the sensors are deployed [17].The probability of abnormal events is very high in certain fields of the monitored region. In monitoring, it is necessary to obtain data from these areas more precisely. In order to obtain accurate monitoring data of an interesting area, several sensors are usually deployed. Sensor deployment requires accurate and computationally feasible sensor detection models. When the sensor is deployed in the critical area, the minimum sensing radius of the sensorrs that does not obstruct the monitoring is considered as the effective sensing threshold of the sensor node of the whole network. The monitored area is divided into M×N sensing grids. We assume that each sensing grid is a regular inscribed quadrilateral of a circle whose diameter is 2rs. The index of the sensing grid is (i,j), where 1≤i≤M, 1≤j≤N. The model is illustrated in Figure 1. The sensing data matrix of the monitored area is set as X∈RM×N.Figure 1
The sensing grids of the monitored region.In this work, we determine a sensing grid to deploy only one sensor. If an area needs more sensors, we can take measures of selecting smallerrs or increase the sensor layout density.Here, we adopt a mask operatorΓ(·) to represent the procedure of deploying the sensors:(1)ΓX⊗W′=X⊗W′⊗Q,where W′ represents the matrix of the sensing grids’ weights and ⊗ represents the elementwise product of two matrices. Q is an M×N matrix defined by the following form:(2)Qi,j=1A sensor has been deployed in the grid which is thei,jth position of theX0otherwise,where (i,j) denotes the index of the sensing grid in Q. The sensors localization set P is obtained by combining all the coordinates of the sensing grid that satisfy Qi,j=1:(3)P=i,j∣Qi,j=1.Now, we can use k to represent the total number of the elements of P. It is obvious that k is the total number of sensors.The index of elements ofQ is numbered by line priority. The index of the numbers is from 1 to M×N. The essence of weight-aware sensor deterministic deployment optimization is a combinatorial optimization issue for the number of sensing grids in which the sensors are located. The combination scheme for the number of sensor positions with the best monitoring effect is selected from many combinations. The set of various combinations of sensors is(4)L=Lg∣0≤g≤CM×Ng,g∈Z,where Lg stands for the gth combination of k numbers which is from 1 to M×N. g is the index of various combinations.(5)FLg=P,where the function F() is to convert a string of numbers into a series of coordinates in the sensing matrix X. Equation (5) denotes that the sensor localization set P is obtained by taking the gth combination scheme Lg.For instance, the index set of the elements ofQ is {(1,1),(1,2),(2,1),(2,2)}. The numbered set corresponding to Q is {1,2,3,4}. Now, we assume that k=3 sensors that need to be deployed. We take any three numbers from the numbered set {1,2,3,4} to form a combination. C43=4. There are four cases of taking any three numbers from the numbered set. L={L1,L2,L3,L4}=1,2,3,1,2,4,2,3,4,1,3,4. The second combination is used to explain the process. g=2, and then L2=1,2,4. F(L2)=P=1,1,1,2,2,2. The three sensors will be deployed to three grids whose indexes are (1,1), (1,2), and (2,2).There are many combinations of sensor localization. It becomes a critical issue for the weight-aware sensor deployment to choose the best one. What criterion is the best combination of the sensor localization? To solve this problem, we need to consider the weight of the sensing grid in the matrixX and ensure the effective and reliable data collection. We introduce the concept of the sensing trust degree of the whole WSN to evaluate deployment. It is related to the sensing reliability degree of the sensing grid, the sensing coverage rate of the whole WSN, and the weight of the sensing grid. In the following, we introduce these concepts.Definition 1 (the sensing reliability degree of the sensing grid).
This is defined as the probability that the data in the sensing grid can be effectively and successfully collected and transmitted to the sink node. The sensing reliability degree of the(i,j)th sensing grid is represented by R(i,j).
R ( i , j ) is the dual concept of data miss probability in sensing grid. The more the data points collected in the sensing region, the smaller the possibility of data loss and the greater the value of R(i,j). R(i,j) is the result of the combined action of all sensors that can sense the (i,j)th sensing grid. It is related to the total number of sensors that can cover the sensing grid and the sensors’ sensing accuracies.
The more the sensor nodes that collect the same data are, the higher the reliability of the data acquisitionR(i,j) is. When one piece of data of the grid is collected by multiple sensors, if one of the sensors fails, it can be acquired by other sensors. For the critical areas of the monitored region, the reliability of data acquisition must be guaranteed.Definition 2 (the sensing coverage degree of the sensing grid).
The more powerful the sensor, the greater the area that it extends. The coverage ability of sensors is reflected by their sensing accuracy. The sensing coverage degree of the sensing grid is related to the sensing accuracy of sensors covered in this grid. The effective coverage degree produced by the most powerful sensor in this grid is used as the sensing coverage degree. The most powerful sensor’s sensing accuracy is maximum. The sensing coverage degree of the(i,j)th sensing grid is represented by COi,j. COi,j×Si,j is defined as the effective coverage area of the (i,j)th sensing grid, where S(i,j) denotes the area of the (i,j)th grid.
The sensing coverage rate of the whole WSNs is denoted bySCO.(6)SCO=COSAS,where AS denotes the area of the whole sensing region. COS denotes the effective coverage area of the whole WSN.(7)COS=∑i=1M∑j=1NCOi,j×Si,j.
The area where sensors overlap increases as the density of sensor deployment increases. As a result, the sensing coverage of the whole network is becoming lower.SCO reflects the density degree of sensor deployment.Definition 3 (the sensing trust degree of the whole WSNs).
It is the sum of all sensing reliabilities of sensing grids in a certain sensing coverage rate of the whole WSN. It is denoted byTR·. The higher the value of TR(·) is, the higher the reliability of the data collected is, that is, the better the performance of the monitoring network is.
Finally, in the case that the number of sensors is given, we can get the best sensor deployment scheme by solving the following optimization problem:(8)P∗=argmaxP⁡TRΓX⊗W′s.t.k≪M×N.
In actual engineering, to ensure the effective collection of data from the monitored region, we also encounter the minimum requirement for grid sensing. It is discussed in the following.
In practice, the minimum sensor reliabilityRmin⁡ of sensing grid and the data loss probability threshold Mmin⁡ in [8] are a pair of dual concepts. The larger the value of Rmin⁡ is, the smaller the value of Mmin⁡ is, and vice versa. In the case that the minimum sensor reliability is defined, the problem of weight-aware sensor deterministic deployment problem becomes(9)P∗=argmaxP⁡TRΓX⊗W′subject toRi,j≥Rmin⁡.


## 4. Estimation of the Weights

Weight estimation is a complex work which is investigated with many methods. In [18], Fujimoto et al. proposed a model reestimation method that involves the extraction of reliable characteristics using Gaussian pruning with weight normalization. In this paper, we hold the main factors that affect the weights. However, the relationship between the weight and the factors is not simply cumulative.The weight of each sensing grid is affected by many factors. In this paper, we have found the three main factors: PL, the probability of an abnormal event occurrence;D, the cost of damage resulting from an abnormal event, that is, the extent of the impact; and T, the tolerance time of an abnormal event, that is, the period time over which the monitored object exhibits an abnormal event to cause great losses. These three quantities of monitoring objects can be estimated by fuzzy comprehensive evaluation method or by Delphi method.Among them, the relationship between the cost of damage resulting from an abnormal event and the tolerance time of an abnormal event is very special. The two variables are independent and unrelated to each other, and they have the opposite direction of development. The problem of calculating their effects on computation of the weight is getting more and more attention. Since the two variables are independent and unrelated, their coordinates are perpendicular to each other. It is not appropriate to calculate the common effects of two independent variables in a summation method. In this paper, the characteristics of two independent and unrelated variables are analyzed, and a novel seesaw mapping is introduced on the basis of the seesaw model in [19, 20].


### 4.1. The Seesaw Mapping

In some application scenarios, two independent variables or entities affect another variable or entity together, but the direction of development of these two entities is opposite, and two variables have opposite orientations relative to the third variable or entity. It is necessary to determine the extent of the combined effect.The condition of seesaw model in [19] is as follows: (1) two independent variables or entities are generally independent of each other; (2) two independent variables or entities affect another variable or entity together. For the two variables or entities that satisfy the condition of the seesaw model, a seesaw mapping can be applied. The seesaw model condition ensures that the two variables or entities can be mapped to Euclidean space. The values of the two coordinates in the Euclidean space reflect the values of the two variables at some certain state points and the values of two individual developments. It is necessary to map the common effects of two quantities in the Euclidean space to a single coordinate. We compare their values by the front and back relationships in a coordinate. This comparison is intuitive and clear. This series of processes is called the seesaw mapping.We assume the variablesA and B satisfied the condition of seesaw model. A=Ai∈R∣i∈Ζ  and  B=Bi∈R∣i∈Ζ. The set of the seesaw pairs of A and B is set as M=Ai,Bi∣i∈T, where (Ai,Bi) is a seesaw pair. One Ai corresponds to one Bi; namely, there is a one-to-one correspondence between Ai and Bi. T is the distribution sequence obeyed by A and B. T⊂R. The distribution sequence can be either spatial or temporal or any other distribution. For example, we can use the seesaw mapping to study the changes of A and B over time. We can also use it to study the difference between A and B when they are at different points in space. i is the index of (A,B) in T. T is commonly {0,1,2,…} or [c,d], where c can take 0 or -∞ and d can be +∞. If T is a countable set, we call T a discrete sequence. Ai denotes the value of variable A at point i in T. Bi denotes the value of variable B at point i in T.Definition 4 (the state of the combined effect).
This is the quantitative representation of the combined effect ofA and B at the i point in T. It is represented by GiAi,Bi, and GiAi,Bi∈R.Definition 5 (the state space).
This is the set ofGiAi,Bi. One calls the state space of the combined effect of A and B. It is denoted by GT(A,B). GTA,B⊂R.
The seesaw mapping is represented as a mapping:(10)Ai,Bi⟶f∗,∗GiAi,Bi,where f∗,∗ is mapping operator. f∗,∗:T×M→R is a two-variable single valued function defined on T×M.The seesaw mapping is as follows.Step 1 (normalize each variable).
(11) A n o r m = F A ,  then A i n o r m = F A ,   A i n o r m ∈ 0,1 B n o r m = F B ,  then B i n o r m = F B ,   B i n o r m ∈ 0,1 ,where the function F∗ is to normalize the variables.
If two variables are measured in different units, various normalization methods are used to map the data of each variable to a range of 0~1. The dimensional expressions are transformed into dimensionless expressions, that is, scalar quantity. In many scenarios, the dimensions of the two variables are different, and it is difficult to compare the size directly, so the two variables need to be converted into scalar quantities.Step 2 (perform coordinate transform).
The developing vector of a variable is taken by a series of values in which the variable varies withT.Definition 6 (positive/negative vectors).
For the variable that plays a positive role in the combined effect, one sets it as a positive vector. The other vector is a negative vector.Definition 7 (equilibrium factor).
When the ratio of the normalized variables reaches a constant, the effect of two variables on a third variable is always the same; that is, the two variables are in equilibrium. This constant is defined as the equilibrium factor. It is denoted byγ. Obviously, if Ainorm/Binorm=γ, then GiAi,Bi=C. C is a constant.Definition 8 (seesaw axis).
It is a coordinate axis measuring the degree of the seesaw effect in two variables. The equilibrium state is the origin.
In Figure2, a rectangular coordinate system is made up of the developing vectors of two variables. Draw a ray with an angle of tan-1⁡γ in the counterclockwise direction where the coordinates of the positive vector are located. We can take one point at the rays and make a vertical line. The pedal can be used as the origin of axis. The direction of this vertical line, which is near the positive vector, is the positive direction of the axis. The other is the negative direction. This vertical line is used as the seesaw coordinate of the two variables. The number of negative directions to the origin is negative, and the number from the origin to the positive is a positive number.Figure 2
The diagram of the proof for saw transform.Theorem 9.
The values of two variables A and B at a pointi in T are, respectively, normalized. Let Anorm be the positive vector and Bnorm be a negative vector. The value of GinormAinorm,Binorm in the seesaw axis is(12)ginormAinorm,Binorm=fAinorm,Binorm=Ainorm2+Binorm2×sin⁡tan-1⁡γ-tan-1⁡BinormAinorm,ginormAinorm,Binorm∈R.Proof.
Assume that two variablesA and B, which are normalized, can be mapped into an Euclidean space. Let OAnorm be horizontal ordinate and OBnorm be vertical ordinate. It is shown in Figure 2 that the ith state of A and B  Gi(Ai,Bi) is mapped as the point G in the Euclidean space. ∠AOH=tan-1⁡γ. Take a spot O′ at the ray OH. Draw a vertical line A′B′ from the O′ pedal. The direction close to the coordinate A is chosen as the positive direction. Finally, O′A′ can be used as the seesaw axis. The projection of GiAi,Bi on the axis O′A′ is Gi′. Then, the value ginormAinorm,Binorm of Gi(Ai,Bi) in the seesaw axis is the length of O′G′.(13)∵tan⁡∠NOG=NGON=BinormAinorm∴∠NOG=tan-1⁡BinormAinorm∵sin⁡∠HOG=sin⁡tan-1⁡γ-∠NOG=HGOG∵OG=ON2+NG22=Ainorm2+Binorm2∴HG=OG×sin⁡∠HOG=Ainorm2+Binorm2×sin⁡tan-1⁡γ-∠NOG=Ainorm2+Binorm2×sin⁡tan-1⁡γ-tan-1⁡BinormAinorm∴HG=OG×sin⁡∠HOG=Ainorm2+Binorm2×sin⁡tan-1⁡γ-∠NOG∵∠OHG=∠HO′G′=∠O′G′G=π2∴HG=O′G′∴O′G′=Ainorm2+Binorm2×sin⁡tan-1⁡γ-tan-1⁡BinormAinorm∴ginormAinorm,Binorm=Ainorm2+Binorm2×sin⁡tan-1⁡γ-tan-1⁡BinormAinorm.Property 10.
g i n o r m A i n o r m , B i n o r m ∈ - 1,1.Proof.
The extended seesaw axisB′O′A′ in Figure 2 is shown in Figure 3. The intersection of the seesaw axis and the horizontal ordinate OAnorm is A′. The intersection of the seesaw axis and the horizontal ordinate OBnorm is B′. At the point A′, the value of axis reached the maximum, and then Ainorm=Anorm and Binorm=0, such that ginormAinorm,Binorm=1. At the point B′, the value of axis is minimum, and then Binorm=Bnorm and Ainorm=0, such that ginorm(Ainorm,Binorm)=-1:(14)∴ginormAinorm,Binorm∈-1,1.
At the maximum or minimum point, the seesaw mapping is reduced to a size comparison of the values of a variable.
In this paper, it is assumed that the contribution of the common effect ofD and T to the weight is not 0 in the process of weight calculation. If tan-1⁡γ=tan-1⁡Binorm/Ainorm, then sin⁡tan-1⁡γ-tan-1⁡Binorm/Ainorm=0, and there is ginorm(Ainorm,Binorm)=0. It requires the further evolution of Theorem 9.Figure 3
The diagram of the proof for saw transform property.Theorem 11.
Positive values of the common contributionGinorm(Ainorm,Binorm) of two variables A and B to the third variable are(15)g^inorm=eAinorm2+Binorm2×sin⁡tan-1⁡γ-tan-1⁡Binorm/Ainorm.Proof.
∵ The domain of the exponential function f(x)=ex is R, the range is f(x)>0, and in the domain f(x) increases with the increase of x.
∵ G i n o r m A i n o r m , B i n o r m reflects the comparative relationship between the common effects of two variables at different points in T. Since the exponential function f(x)=ex is an increasing function, it does not affect the comparative relationship between them. At the same time, it can ensure that GinormAinorm,Binorm is more than 0.
∴ The domain of the exponential function f(x)=ex can be used as a quantized function of the common effect of two variables A and B.


### 4.2. Computation of the Weight Based on the Seesaw Mapping

The probability of the occurrence of an abnormal event and the effect of an abnormal event in each sensing grid are always different, so the importance of each sensing grid is different. Let the weight of the(i,j)th sensing grid be denoted by Wi,j. The matrix of the sensing grids’ weights is W′.The weightWi,j of each sensing grid is affected by many factors. In this paper, we list the three main factors: the probability of an abnormal event occurrence PLi,j, the cost of damage resulting from an abnormal event, that is, the extent of the impact Di,j, and the tolerance time of an abnormal event, that is, the period time over which the monitored object exhibits an abnormal event to cause great losses Ti,j. These three quantities of monitoring objects can be estimated by fuzzy comprehensive evaluation method or by Delphi method. The larger the value of Di,j of a sensing grid is, the smaller the value of Ti,j is and the more important the sensing grid is. Di,j plays a positive role in Wi,j. Ti,j plays a negative role in Wi,j. PLi,j, which is the premise of the combined effect of Ti,j and Di,j, plays a decisive role in Wi,j. Therefore, PLi,j is directly proportional to Wi,j and is proportional to the combined effect of Ti,j and Di,j. Now, we need to study the extent of the combined effect of Ti,j and Di,j on Wi,j in each sensing grid. However, the units of measurement for Ti,j and Di,j are different. The changes in Ti,j and Di,j are independent of each other. These satisfy the definition of the seesaw model. We can use the seesaw mapping to compute the weights.Step 1.
Using the maximum range formula,Di,j is normalized into Di,j′:(16)Di,j′=Di,j-Dmin⁡Dmax⁡-Dmin⁡.Step 2.
Using the maximum range formula,Ti,j is normalized into Ti,j′:(17)Ti,j=Ti,j-Tmin⁡Tmax⁡-Tmin⁡.Step 3.
Compute the weightWi,j of each sensing grid.
The role ofWi,j is to calculate the criticalness of a sensing grid relative to other grids, so we compute the weight using the normalized abnormal event tolerance time Ti,j′ and the normalized extent of the impact of the abnormal events Di,j′. If Di,j′ goes up in increments and Ti,j′ goes toward decreasing direction, it is beneficial to Wi,j. Ti,j′ and Di,j′ are in a state of seesaw. The extent of the combined effect of Ti,j′ and Di,j′ can be computed using the seesaw mapping.
The smaller the value ofTi,j′ is, the greater the value of Di,j′ is and the more important the sensing grid is. Di,j′ can be as the positive vector. In this work, γ is valued at 1; that is, D and T have the same criticalness. We regard that D and T have the same criticalness.
According to the seesaw mapping (Theorem11), we know the extent of the combined effect of Ti,j′ and Di,j′ of the (i,j)th sensing grid:(18)Gi,jDi,j′,Ti,j′=eDi,j′2+Ti,j′2×sin⁡π/4-tan-1⁡Ti,j′/Di,j′Wi,j=Gi,j×PLi,j.Step 4.
NormalizeWi,j for Wi,j′:(19)Wi,j′=Wi,j∑i=1M∑j=1NWi,j.
The weights matrixW′ of the monitored region is composed of many weights Wi,j′ of sensing grids.


## 4.1. The Seesaw Mapping

In some application scenarios, two independent variables or entities affect another variable or entity together, but the direction of development of these two entities is opposite, and two variables have opposite orientations relative to the third variable or entity. It is necessary to determine the extent of the combined effect.The condition of seesaw model in [19] is as follows: (1) two independent variables or entities are generally independent of each other; (2) two independent variables or entities affect another variable or entity together. For the two variables or entities that satisfy the condition of the seesaw model, a seesaw mapping can be applied. The seesaw model condition ensures that the two variables or entities can be mapped to Euclidean space. The values of the two coordinates in the Euclidean space reflect the values of the two variables at some certain state points and the values of two individual developments. It is necessary to map the common effects of two quantities in the Euclidean space to a single coordinate. We compare their values by the front and back relationships in a coordinate. This comparison is intuitive and clear. This series of processes is called the seesaw mapping.We assume the variablesA and B satisfied the condition of seesaw model. A=Ai∈R∣i∈Ζ  and  B=Bi∈R∣i∈Ζ. The set of the seesaw pairs of A and B is set as M=Ai,Bi∣i∈T, where (Ai,Bi) is a seesaw pair. One Ai corresponds to one Bi; namely, there is a one-to-one correspondence between Ai and Bi. T is the distribution sequence obeyed by A and B. T⊂R. The distribution sequence can be either spatial or temporal or any other distribution. For example, we can use the seesaw mapping to study the changes of A and B over time. We can also use it to study the difference between A and B when they are at different points in space. i is the index of (A,B) in T. T is commonly {0,1,2,…} or [c,d], where c can take 0 or -∞ and d can be +∞. If T is a countable set, we call T a discrete sequence. Ai denotes the value of variable A at point i in T. Bi denotes the value of variable B at point i in T.Definition 4 (the state of the combined effect).
This is the quantitative representation of the combined effect ofA and B at the i point in T. It is represented by GiAi,Bi, and GiAi,Bi∈R.Definition 5 (the state space).
This is the set ofGiAi,Bi. One calls the state space of the combined effect of A and B. It is denoted by GT(A,B). GTA,B⊂R.
The seesaw mapping is represented as a mapping:(10)Ai,Bi⟶f∗,∗GiAi,Bi,where f∗,∗ is mapping operator. f∗,∗:T×M→R is a two-variable single valued function defined on T×M.The seesaw mapping is as follows.Step 1 (normalize each variable).
(11) A n o r m = F A ,  then A i n o r m = F A ,   A i n o r m ∈ 0,1 B n o r m = F B ,  then B i n o r m = F B ,   B i n o r m ∈ 0,1 ,where the function F∗ is to normalize the variables.
If two variables are measured in different units, various normalization methods are used to map the data of each variable to a range of 0~1. The dimensional expressions are transformed into dimensionless expressions, that is, scalar quantity. In many scenarios, the dimensions of the two variables are different, and it is difficult to compare the size directly, so the two variables need to be converted into scalar quantities.Step 2 (perform coordinate transform).
The developing vector of a variable is taken by a series of values in which the variable varies withT.Definition 6 (positive/negative vectors).
For the variable that plays a positive role in the combined effect, one sets it as a positive vector. The other vector is a negative vector.Definition 7 (equilibrium factor).
When the ratio of the normalized variables reaches a constant, the effect of two variables on a third variable is always the same; that is, the two variables are in equilibrium. This constant is defined as the equilibrium factor. It is denoted byγ. Obviously, if Ainorm/Binorm=γ, then GiAi,Bi=C. C is a constant.Definition 8 (seesaw axis).
It is a coordinate axis measuring the degree of the seesaw effect in two variables. The equilibrium state is the origin.
In Figure2, a rectangular coordinate system is made up of the developing vectors of two variables. Draw a ray with an angle of tan-1⁡γ in the counterclockwise direction where the coordinates of the positive vector are located. We can take one point at the rays and make a vertical line. The pedal can be used as the origin of axis. The direction of this vertical line, which is near the positive vector, is the positive direction of the axis. The other is the negative direction. This vertical line is used as the seesaw coordinate of the two variables. The number of negative directions to the origin is negative, and the number from the origin to the positive is a positive number.Figure 2
The diagram of the proof for saw transform.Theorem 9.
The values of two variables A and B at a pointi in T are, respectively, normalized. Let Anorm be the positive vector and Bnorm be a negative vector. The value of GinormAinorm,Binorm in the seesaw axis is(12)ginormAinorm,Binorm=fAinorm,Binorm=Ainorm2+Binorm2×sin⁡tan-1⁡γ-tan-1⁡BinormAinorm,ginormAinorm,Binorm∈R.Proof.
Assume that two variablesA and B, which are normalized, can be mapped into an Euclidean space. Let OAnorm be horizontal ordinate and OBnorm be vertical ordinate. It is shown in Figure 2 that the ith state of A and B  Gi(Ai,Bi) is mapped as the point G in the Euclidean space. ∠AOH=tan-1⁡γ. Take a spot O′ at the ray OH. Draw a vertical line A′B′ from the O′ pedal. The direction close to the coordinate A is chosen as the positive direction. Finally, O′A′ can be used as the seesaw axis. The projection of GiAi,Bi on the axis O′A′ is Gi′. Then, the value ginormAinorm,Binorm of Gi(Ai,Bi) in the seesaw axis is the length of O′G′.(13)∵tan⁡∠NOG=NGON=BinormAinorm∴∠NOG=tan-1⁡BinormAinorm∵sin⁡∠HOG=sin⁡tan-1⁡γ-∠NOG=HGOG∵OG=ON2+NG22=Ainorm2+Binorm2∴HG=OG×sin⁡∠HOG=Ainorm2+Binorm2×sin⁡tan-1⁡γ-∠NOG=Ainorm2+Binorm2×sin⁡tan-1⁡γ-tan-1⁡BinormAinorm∴HG=OG×sin⁡∠HOG=Ainorm2+Binorm2×sin⁡tan-1⁡γ-∠NOG∵∠OHG=∠HO′G′=∠O′G′G=π2∴HG=O′G′∴O′G′=Ainorm2+Binorm2×sin⁡tan-1⁡γ-tan-1⁡BinormAinorm∴ginormAinorm,Binorm=Ainorm2+Binorm2×sin⁡tan-1⁡γ-tan-1⁡BinormAinorm.Property 10.
g i n o r m A i n o r m , B i n o r m ∈ - 1,1.Proof.
The extended seesaw axisB′O′A′ in Figure 2 is shown in Figure 3. The intersection of the seesaw axis and the horizontal ordinate OAnorm is A′. The intersection of the seesaw axis and the horizontal ordinate OBnorm is B′. At the point A′, the value of axis reached the maximum, and then Ainorm=Anorm and Binorm=0, such that ginormAinorm,Binorm=1. At the point B′, the value of axis is minimum, and then Binorm=Bnorm and Ainorm=0, such that ginorm(Ainorm,Binorm)=-1:(14)∴ginormAinorm,Binorm∈-1,1.
At the maximum or minimum point, the seesaw mapping is reduced to a size comparison of the values of a variable.
In this paper, it is assumed that the contribution of the common effect ofD and T to the weight is not 0 in the process of weight calculation. If tan-1⁡γ=tan-1⁡Binorm/Ainorm, then sin⁡tan-1⁡γ-tan-1⁡Binorm/Ainorm=0, and there is ginorm(Ainorm,Binorm)=0. It requires the further evolution of Theorem 9.Figure 3
The diagram of the proof for saw transform property.Theorem 11.
Positive values of the common contributionGinorm(Ainorm,Binorm) of two variables A and B to the third variable are(15)g^inorm=eAinorm2+Binorm2×sin⁡tan-1⁡γ-tan-1⁡Binorm/Ainorm.Proof.
∵ The domain of the exponential function f(x)=ex is R, the range is f(x)>0, and in the domain f(x) increases with the increase of x.
∵ G i n o r m A i n o r m , B i n o r m reflects the comparative relationship between the common effects of two variables at different points in T. Since the exponential function f(x)=ex is an increasing function, it does not affect the comparative relationship between them. At the same time, it can ensure that GinormAinorm,Binorm is more than 0.
∴ The domain of the exponential function f(x)=ex can be used as a quantized function of the common effect of two variables A and B.


## 4.2. Computation of the Weight Based on the Seesaw Mapping

The probability of the occurrence of an abnormal event and the effect of an abnormal event in each sensing grid are always different, so the importance of each sensing grid is different. Let the weight of the(i,j)th sensing grid be denoted by Wi,j. The matrix of the sensing grids’ weights is W′.The weightWi,j of each sensing grid is affected by many factors. In this paper, we list the three main factors: the probability of an abnormal event occurrence PLi,j, the cost of damage resulting from an abnormal event, that is, the extent of the impact Di,j, and the tolerance time of an abnormal event, that is, the period time over which the monitored object exhibits an abnormal event to cause great losses Ti,j. These three quantities of monitoring objects can be estimated by fuzzy comprehensive evaluation method or by Delphi method. The larger the value of Di,j of a sensing grid is, the smaller the value of Ti,j is and the more important the sensing grid is. Di,j plays a positive role in Wi,j. Ti,j plays a negative role in Wi,j. PLi,j, which is the premise of the combined effect of Ti,j and Di,j, plays a decisive role in Wi,j. Therefore, PLi,j is directly proportional to Wi,j and is proportional to the combined effect of Ti,j and Di,j. Now, we need to study the extent of the combined effect of Ti,j and Di,j on Wi,j in each sensing grid. However, the units of measurement for Ti,j and Di,j are different. The changes in Ti,j and Di,j are independent of each other. These satisfy the definition of the seesaw model. We can use the seesaw mapping to compute the weights.Step 1.
Using the maximum range formula,Di,j is normalized into Di,j′:(16)Di,j′=Di,j-Dmin⁡Dmax⁡-Dmin⁡.Step 2.
Using the maximum range formula,Ti,j is normalized into Ti,j′:(17)Ti,j=Ti,j-Tmin⁡Tmax⁡-Tmin⁡.Step 3.
Compute the weightWi,j of each sensing grid.
The role ofWi,j is to calculate the criticalness of a sensing grid relative to other grids, so we compute the weight using the normalized abnormal event tolerance time Ti,j′ and the normalized extent of the impact of the abnormal events Di,j′. If Di,j′ goes up in increments and Ti,j′ goes toward decreasing direction, it is beneficial to Wi,j. Ti,j′ and Di,j′ are in a state of seesaw. The extent of the combined effect of Ti,j′ and Di,j′ can be computed using the seesaw mapping.
The smaller the value ofTi,j′ is, the greater the value of Di,j′ is and the more important the sensing grid is. Di,j′ can be as the positive vector. In this work, γ is valued at 1; that is, D and T have the same criticalness. We regard that D and T have the same criticalness.
According to the seesaw mapping (Theorem11), we know the extent of the combined effect of Ti,j′ and Di,j′ of the (i,j)th sensing grid:(18)Gi,jDi,j′,Ti,j′=eDi,j′2+Ti,j′2×sin⁡π/4-tan-1⁡Ti,j′/Di,j′Wi,j=Gi,j×PLi,j.Step 4.
NormalizeWi,j for Wi,j′:(19)Wi,j′=Wi,j∑i=1M∑j=1NWi,j.
The weights matrixW′ of the monitored region is composed of many weights Wi,j′ of sensing grids.


## 5. The Sensing Trust Degree of WSN

As mentioned early,R(i,j) is related to the total number and sensing accuracy of sensors. This paper assumes that the sensor is arranged at the center of each sensing grid. According to the sensing precision formula of single sensor node in [21], it is known that the sensing accuracy is attenuated with the increase of the distance. Assuming the position (p,q) of the grid is arranged with a sensor, the sensing accuracy formula of position (i,j) of the sensing grid is derived as(20)Si,j→p,q=11+α×di,j→p,qβ,where di,j→p,q represents the distance between the (i,j)th and the (p,q)th sensing grid. The sensor is located in the (p,q)th sensing grid. The constants α and β are device-dependent parameters reflecting the physical features of a sensor. Generally, β ranges from 1 to 4 [17], and α is used as an adjustment parameter [16]. Sensors collect data from the sensing grid. The precision of the data in the sensing grid becomes smaller as the distance between the sensing data grid and the sensor grid increases.When a sensing grid is equipped with a sensor, its sensing accuracy corresponding to the sensor is 1. Sinced=0, then S=1. This denotes that the probability of sensor false positives is very small. For example, the closer you get to the camera, the clearer you see and the less likely you are to misjudge. A sensor is deployed in a sensing grid, and the sensing accuracy of the sensor grid for this sensor is 1. In this paper, we assume that sensors are deployed at the center of the sensing grid.In the practical application of sensor networks, obstacles inevitably exist in the monitored region. These obstacles cause signal blocking and reduce sensor sensing efficiency. Here, we consider the obstruction toS(i,j)→(p,q), assuming the known topography within the sensing region. If the obstacles appear in the line of sight from the grid point (i,j) to the grid point (p,q), namely, if the coordinates (x,y) of the obstacle satisfy the equations of connecting (i,j) and (p,q) line, that is, x-i/p-i=y-j/q-j, then S(i,j)→(p,q)=0. Local blocking can also be modeled by setting the sensing probability to very small nonzero values [21].Theorem 12.
If the coordinates(x,y) of the obstacle satisfy the equations of connecting (i,j) and (p,q) line, that is, x×q-x×j-y×p+y×i=i×q-j×p, then S(i,j)→(p,q)=0.Proof.
In actual operations, when(i,j) and (p,q) are on the same line or the same column, there is p-i==0 or q-j==0. It is not allowed for the denominator to be zero.
We have to transform the equation(x-i)/(p-i)=(y-j)/(q-j) to x×q-x×j-y×p+y×i=i×q-j×p.Theorem 13.
In the model, the distance between the(i,j)th sensing grid and the (p,q)th sensor grid is(21)di,j→p,q=i-p2+j-q22×2×rs,where (p,q) are the coordinates of the sensor grid in which the sensor is located.Proof.
The sensor is located at the center of the sensing grid. The sensing grid is the inscribed quadrilateral of a circle with a radius ofrs. It is shown in Figure 4 that the sensor is placed at the point O, and d(i,j)→(p,q) is the distance between the grid (i,i) and the point O.(22)∵di,j→p,q=OP∵OA=rs∴OB=sin⁡π4×OA=22×rs∵DO=j-q×22×2rs=2×rs×j-q∵DP=i-p×22×2rs=2×rs×i-p∴di,j→p,q=OP=DP2+DO22=i-p2+j-q22×2×rs.
If a plurality of sensors are deployed in the sensing region, the sensing reliability degree of the(i,j)th sensing grid is(23)Ri,j=∑p,q∈P11+α×di,j→p,qβ=∑p,q∈P11+α×i-p2+j-q22×2×rsβ.
Sensing reliability is related to whether data can be sampled by the sensor smoothly. The data in the many sensors’ sensing accuracy overlapping field is read by several sensors. The reliability of the overlap field is higher because if one sensor fails, the data can also be sampled through other sensors. So, the sensing reliability is the accumulation of all sensors’ sensing accuracies.Figure 4
The schematic diagram ofdi,j→p,q.Property 14.
Ifk=0, namely, P=Φ, then R(i,j)=0.Proof.
If the sensors are not deployed in the sensing matrix, thenp=∞, q=∞.(24)∴Ri,j=∑p,q∈P1k×1+α×∞×2×rsβ=0.Property 15.
The range ofR(i,j) is [0,1].Proof.
(25) ∵ d i , j → p , q = 0 ∴ 1 1 + α × d i , j → p , q β = 1 ∵ d i , j → p , q = 0 ∴ 1 1 + α × d i , j → p , q β = 1 ∵ d i , j → p , q = ∞ ∴ 1 1 + α × d i , j → p , q β = 0 ∴ 0 ≤ 1 1 + α × d i , j → p , q β ≤ 1 , ∵ The cardinality of P is k ∴ R i , j = ∑ p , q ∈ P 1 1 + α × d i , j → p , q β ∈ 0,1 .
The sensing accuracy of sensors reflects the ability of sensors to collect data. The stronger the sensor, the greater the area that it covers. The coverage area of the whole WSN is the union of all sensors’ coverage fields. In the overlap region, the coverage degree takes the maximum value of all sensor accuracies. The sensing coverage degree of the(i,j)th sensing grid is(26)COi,j=max⁡11+α×di,j→p,q×2×rsβ,11+α×di,j→p,q×2×rsβ,…,11+α×di,j→p,q×2×rsβ=max⁡11+α×i-p2+j-q2×2×rs2β,11+α×i-p2+j-q2×2×rs2β,…,11+α×i-p2+j-q2×2×rs2β.
The total sensing coverage degree of the whole WSN is(27)CO=∑i=1M∑j=1NCOi,j=∑i=1M∑j=1Nmax⁡11+α×i-p2+j-q2×2×rs2β,11+α×i-p2+j-q2×2×rs2β,…,11+α×i-p2+j-q2×2×rs2β.
∵ According to Definition 2, the sensing coverage rate of the whole WSN is(28)SCO=COSAS.
It is shown in Figure4 that AS=M×2×rs×N×2×r=4rs2×M×N.(29)COS=CO×2×rs×2×rs=4rs2×CO∴SCO=COM×N.
The sensing accuracy of multiple sensors overlaps in some sensing grids, and the sensing reliability of the sensing grids increases, while the effective coverage area of the whole WSN is reduced (i.e., the sensing coverage rate becomes smaller). This is because the coverage degree takes the maximum of all sensors’ sensing accuracy in the overlapping areas.
Finally, the sensing trust degree of the whole WSN is defined as(30)TRΓX⊗W′=SCO×∑i=1M∑j=1NWi,j′×Ri,j.
We can use the algorithms in the next section to achieve the maximum ofTRΓX⊗W′.


## 6. Weight-Aware Sensor Deployment Algorithms

It is necessary to select the sensor location combination scheme whose sensing trust degree of the whole monitored region is the maximum, from the combination scheme of many sensor locations. If the same criterion is followed by each location scheme, then these combinations can be compared. This paper discusses algorithms to address the optimal sensor deployment in three cases:(1) the total number of sensors deployed in the monitored region is given; it is very hard to increase the total number of sensors; (2) the minimum sensing reliability of the sensing grid is set; (3) there are some obstacles in the sensing region.


### 6.1. Algorithm Notations

To describe our proposed algorithms, the following notations and message types are used.m: the number of rows in the sensing matrix,n: the number of columns in the sensing matrix,k: the total number of sensors deployed in the monitored region,α: adjustment parameter,β: device-dependent parameter,L: a list that stores the combinations of k numbers from 1 to m×n,g: the index of combination sequences in L,Lg: the gth combination,P: a list that stores a series of row coordinates and column coordinates of each sensor position corresponding to the gth combination Lg,P∗: a list that stores a series of row coordinates and column coordinates of each sensor position corresponding to the combination whose sensing trust degree of the whole WSN is maximum,TR: a list that stores the sensing trust degree of the whole WSN gained from each sensor deployment,W: weight matrix,SR: sensing accuracy degree of the whole WSN,SCO: sensing coverage degree of the whole WSN,Ri,j: the sensing reliability degree of the (i,j)th sensing grid,CO(i,j): the sensing coverage degree of the (i,j)th sensing grid,(i,j): the coordinate of the sensing grid,(p,q): the coordinate of the sensing grid deployed with sensor.


### 6.2. Algorithm Description

Case 1.
The total number of sensors deployed in the monitored region is given (see Algorithm1).
Step  1. Generate combinatorial k numbers from 1 to m×n and store these combinations into L.
Step  2. The sensing accuracy of each sensor is added as the sensing reliability degree R(i,j) of this sensing grid.
Step  3.The maximum sensing accuracy of each sensor to this sensing grid is used as the sensing coverage degree CO(i,j) of this sensing grid.
Step  4.The sensing coverage degree of each sensing grid is accumulated to obtain SCO.
Step  5. The sensing reliability degree R(i,j) of each sensing grid is multiplied by the weight of the sensing grid and then accumulated to obtain SR.
Step  6. Use formula (30) TRg=SCO/M×N×SR to compute the maximum sensing trust degree of the whole WSN of the gth layout.
Step  7. Go through all the combinations in L. Put the sensing trust degree of each combination into TR. When the TR value is the maximum, the corresponding sensor position combination Lresult is required.
Step  8. Using the function F(), the sensor position combination Lresult is transformed into the specific coordinates of the sensor in the sensing data matrix.Algorithm 1:The weight-aware sensor deployment algorithm with the given number of sensors.
input:k, α, β output:P∗ Generate combinatorialk numbers from 1 to m×n, and store these combination into L. for all Lg∈L do SCO←0, SR←0 for i=1 to m do for j=1 to n do for all (p,q)∈P do R(i,j)=R(i,j)+11+α×i-p2+j-q22×2×rsβ CO(i,j)=max⁡11+α×i-p2+j-q22×2×rsβ End for SCO=SCO+COi,j SR=SR+Ri,j×W(i,j) End for End for TRg=SCOM×N×SR End for Lresult=Lg  when  max⁡TRg P∗=FLresultCase 2.
Minimum sensing reliabilityRmin⁡ of the sensing grid is set.
In practical engineering, in order to ensure that the data of each grid is collected effectively and reliably, the minimum sensing reliability degreeRmin⁡ of each sensing grid is often set (see Algorithm 2).
Step  1. It is necessary to determine whether R(i,j) is less than Rmin⁡ each time after R(i,j) is computed. If R(i,j) is less than Rmin⁡, the current selected combination is not appropriate. There is a need to select the next combination and delete the currently inappropriate combination sequence Lg.
Step  2. If the total number of sensors is small, this will cause the sensing accuracy to be less than Rmin⁡ in the calculation process of each sensor position combination. After going through all the combinations, the sensing accuracy is still less than Rmin⁡, such that L is empty. There is a need to increase the number of sensors. The new combinations are generated and stored in L.Algorithm 2:The weight-aware sensor deployment algorithm with Rmin⁡ of each sensing grid.
Input:Rmin⁡ Output:k ifR(i,j)<Rmin⁡ then delete Lg g=g+1 else Perform Algorithm 1 End if ifL==ϕ  and  g≠0 then k=k+1 g←0 Perform Algorithm 1 End ifCase 3.
There are some obstacles in the sensing region.
Inevitably, there will be obstacles in the monitoring area. We assume the position set of the obstacles isOB=xm,yn∣m∈R,n∈R,0≤m≤M,0≤n≤N, where (xm,yn) denotes the coordinates of obstacles (see Algorithm 3).
BeforeR(i,j) is computed, the coordinates of all the obstacles are judged whether they satisfy the line equations determined by two points at (i,j) and (p,q). If they satisfy the equation, then the value of R(i,j) is zero. Otherwise, the value of R(i,j) can be calculated by Algorithm 1.Algorithm 3:The weight-aware sensor deployment algorithm with obstacles in some sensing grids.
input: OB output:Ri,j for allxm,yn∈OB do if x×q-x×j-y×p+y×i=i×q-j×p then Ri,j←0 End if End for


## 6.1. Algorithm Notations

To describe our proposed algorithms, the following notations and message types are used.m: the number of rows in the sensing matrix,n: the number of columns in the sensing matrix,k: the total number of sensors deployed in the monitored region,α: adjustment parameter,β: device-dependent parameter,L: a list that stores the combinations of k numbers from 1 to m×n,g: the index of combination sequences in L,Lg: the gth combination,P: a list that stores a series of row coordinates and column coordinates of each sensor position corresponding to the gth combination Lg,P∗: a list that stores a series of row coordinates and column coordinates of each sensor position corresponding to the combination whose sensing trust degree of the whole WSN is maximum,TR: a list that stores the sensing trust degree of the whole WSN gained from each sensor deployment,W: weight matrix,SR: sensing accuracy degree of the whole WSN,SCO: sensing coverage degree of the whole WSN,Ri,j: the sensing reliability degree of the (i,j)th sensing grid,CO(i,j): the sensing coverage degree of the (i,j)th sensing grid,(i,j): the coordinate of the sensing grid,(p,q): the coordinate of the sensing grid deployed with sensor.


## 6.2. Algorithm Description

Case 1.
The total number of sensors deployed in the monitored region is given (see Algorithm1).
Step  1. Generate combinatorial k numbers from 1 to m×n and store these combinations into L.
Step  2. The sensing accuracy of each sensor is added as the sensing reliability degree R(i,j) of this sensing grid.
Step  3.The maximum sensing accuracy of each sensor to this sensing grid is used as the sensing coverage degree CO(i,j) of this sensing grid.
Step  4.The sensing coverage degree of each sensing grid is accumulated to obtain SCO.
Step  5. The sensing reliability degree R(i,j) of each sensing grid is multiplied by the weight of the sensing grid and then accumulated to obtain SR.
Step  6. Use formula (30) TRg=SCO/M×N×SR to compute the maximum sensing trust degree of the whole WSN of the gth layout.
Step  7. Go through all the combinations in L. Put the sensing trust degree of each combination into TR. When the TR value is the maximum, the corresponding sensor position combination Lresult is required.
Step  8. Using the function F(), the sensor position combination Lresult is transformed into the specific coordinates of the sensor in the sensing data matrix.Algorithm 1:The weight-aware sensor deployment algorithm with the given number of sensors.
input:k, α, β output:P∗ Generate combinatorialk numbers from 1 to m×n, and store these combination into L. for all Lg∈L do SCO←0, SR←0 for i=1 to m do for j=1 to n do for all (p,q)∈P do R(i,j)=R(i,j)+11+α×i-p2+j-q22×2×rsβ CO(i,j)=max⁡11+α×i-p2+j-q22×2×rsβ End for SCO=SCO+COi,j SR=SR+Ri,j×W(i,j) End for End for TRg=SCOM×N×SR End for Lresult=Lg  when  max⁡TRg P∗=FLresultCase 2.
Minimum sensing reliabilityRmin⁡ of the sensing grid is set.
In practical engineering, in order to ensure that the data of each grid is collected effectively and reliably, the minimum sensing reliability degreeRmin⁡ of each sensing grid is often set (see Algorithm 2).
Step  1. It is necessary to determine whether R(i,j) is less than Rmin⁡ each time after R(i,j) is computed. If R(i,j) is less than Rmin⁡, the current selected combination is not appropriate. There is a need to select the next combination and delete the currently inappropriate combination sequence Lg.
Step  2. If the total number of sensors is small, this will cause the sensing accuracy to be less than Rmin⁡ in the calculation process of each sensor position combination. After going through all the combinations, the sensing accuracy is still less than Rmin⁡, such that L is empty. There is a need to increase the number of sensors. The new combinations are generated and stored in L.Algorithm 2:The weight-aware sensor deployment algorithm with Rmin⁡ of each sensing grid.
Input:Rmin⁡ Output:k ifR(i,j)<Rmin⁡ then delete Lg g=g+1 else Perform Algorithm 1 End if ifL==ϕ  and  g≠0 then k=k+1 g←0 Perform Algorithm 1 End ifCase 3.
There are some obstacles in the sensing region.
Inevitably, there will be obstacles in the monitoring area. We assume the position set of the obstacles isOB=xm,yn∣m∈R,n∈R,0≤m≤M,0≤n≤N, where (xm,yn) denotes the coordinates of obstacles (see Algorithm 3).
BeforeR(i,j) is computed, the coordinates of all the obstacles are judged whether they satisfy the line equations determined by two points at (i,j) and (p,q). If they satisfy the equation, then the value of R(i,j) is zero. Otherwise, the value of R(i,j) can be calculated by Algorithm 1.Algorithm 3:The weight-aware sensor deployment algorithm with obstacles in some sensing grids.
input: OB output:Ri,j for allxm,yn∈OB do if x×q-x×j-y×p+y×i=i×q-j×p then Ri,j←0 End if End for


## 7. Performance Validation

In the section, we first validate our proposed algorithm. The sensing trust degree of various sensor deployments caused by different matrix weights is compared. Then, our proposed algorithm is compared with the widely used sensor deployment algorithm MAX_AVG_COV [8].


### 7.1. Simulation Settings

The simulation experiment is completed on MATLAB. This paper assumes that the sensing grid is a regular square. It is assumed that each sensor has the same sensing accuracy; that is,α and β of each sensor are the same. Table 1 enumerates the common parameters of our simulation experiments.Table 1
Simulation parameters.
Parameter description Value Minimum sensing radiusrs Ten meters Adjustment parameterα 1 Device-dependent parameterβ 1


### 7.2. Simulation Results

In the first simulation, we study the weight’s impact on the data collection effects of the WSN. The sensor deployment schemes with the same number of sensors have different sensing trust degrees of the whole WSN in the case of the different weight matrices. We choose the sensor deployment with the highest trust degree of the whole WSN as the best sensor deployment. The weight of the sensing grid in the sensing region is related to the loss cost, occurrence probability, and tolerance time of monitoring abnormal events. The weight of all the grids constitutes the weight matrix of WSN. In order to compare the different sensing trust degrees of the whole WSN caused by the different weight matrices, we randomly set the estimated parameters in Tables2 and 3 for the weight matrices W1 and W2, respectively.Table 2
The estimated parameters ofW1.
The cost of damage resulting from an abnormal eventD(/hundred dollars) {11,2,9;0.5,1,9;0.5,3,8} The tolerance time of an abnormal eventT(/hours) {2,1,0.5;0.3,3,1;0.1,4,1} The probability of an abnormal event occurrence PL {0.1,0.3,0.8;0.9,0.25,0.1;0.4,0.6,0.7}Table 3
The estimated parameters ofW2.
The cost of damage resulting from an abnormal eventD(/hundred dollars) {1,0.5,8;3,10,1;0.5,0.5,1} The tolerance time of an abnormal eventT(/hours) {1,3,8;0.1,3,1;0.9,2,1} The probability of an abnormal event occurrence PL {0.1,0.2,0.7;0.2,0.1,0.9;0.1,0.1,0.1}The number of sensors is set to 5. The number of abscissa grids isM=3, and the number of ordinate grids is N=3. We can see that the different sensing trust degrees are obtained by different weight matrices in Figure 5. When the number of sensors is 5, there are 126 sensor deployment methods, that is, 126 combinations. In Figure 5(a), the sensing trust degree of the WSN which is caused by the sensor deployment corresponding to the 118th combination is highest, up to 1.424. The sensing trust degree of the WSN which is caused by the sensor deployment corresponding to the 23rd combination is minimum, only 0.9707. In Figure 5(b), the sensing trust degree of the WSN which is caused by the sensor deployment corresponding to the 71st combination is highest, up to 1.504. The sensing trust degree of the WSN which is caused by the sensor deployment corresponding to the 71st combination is minimum, only 0.8902. The sensing trust degree of the best combination is about two times that of the worst one. Because of the weight difference, the effect of data collection on the same number of sensors is different. Finally, it is necessary to study the influence of grid weight on sensor deployment.Figure 5
The performance of different weight matrices. (a) Weight matrixW1 and (b) weight matrix W2.
(a)
Weight matrixW1 (b)
Weight matrixW2In order to further analyze the impact of grid weights on data collection, we compare the best deployed sensor locations with the worst locations in the case of the two different weight matrices. In Figure6, these ● denote the sensor locations with the highest sensing degree of the whole WSN, and these △ denote the sensor locations with minimal sensing degree. In Figure 6(a), the sensor deployment coordinates with the highest sensing degree of the whole WSN are {(1,3),(2,2),(2,3),(3,2),(3,3)}, and the sensor deployment coordinates with the minimal sensing degree are {(1,1),(1,2),(2,1),(3,1),(3,2)}. In Figure 6(b), the sensor deployment coordinates with the highest sensing degree are {(1,2),(1,3),(2,1),(2,2),(2,3)}, and the sensor deployment coordinates with the minimal sensing degree are {(1,1),(2,1),(3,1),(3,2),(3,3)}.Figure 6
Comparison of the best and worst sensor deployment.
(a)
Weight matrixW1 (b)
Weight matrixW2As is shown in Figure6, we can see that the sensors are deployed on the edge of the sensing area and in the grids with lower weights by the sensor deployment with the minimum trust degree of the whole WSN. However, the sensors are almost deployed on the center of the sensing area and in the grids with larger weights by the sensor deployment with the maximum trust degree.In the second simulation, we compare our proposed algorithm with MAX_AVG_COV [8]. We assume that the number of rows of the sensing matrix is 4 and the number of columns is 4. We measure the minimum number of sensors required, when miss probability threshold Mmin⁡ (corresponding to the minimum reliability of each grid Rmin⁡) varies from 0.1 to 0.7 with an increment of 0.1.As we can see from Figure7, the minimum number of sensors required decreases as the minimum reliability increases. When Mmin⁡ is 0.1, the minimum number of sensors required by the proposed algorithm is half the number in the MAX_AVG_COV algorithm. When Mmin⁡=0.7, the required number of sensors in our algorithm is less than 2 in the MAX_AVG_COV algorithm. Obviously, the algorithm proposed in this paper is superior to MAX_AVG_COV algorithm.Figure 7
The comparison for minimum reliability.In the third simulation, we study the presence of obstacles in the sensing area. Suppose there are 4 obstacles. The layout model of the obstacle of our proposed algorithm is shown in Figure8. The coordinates of the obstacles are set to OB={(2,2.5),(2.5,4),(2.5,1),(3.5,2)}.Figure 8
The layout model of the obstacle of our proposed algorithm.The layout model of the obstacle of the MAX_AVG_COV algorithm is shown in Figure9.Figure 9
The layout model of the obstacle of MAX_AVG_COV algorithm.Then,d10,14=0, d14,10=0, d6,7=0, d7,6=0, d8,12=0,  d12,8=0, d5,9=0, and  d9,5=0, where di,j denotes distance from the ith sensing grid to the jth sensing grid.We compare the minimum number of sensors required by the two algorithms, as shown in Figure10, when there are obstacles in the sensing region.Figure 10
The comparison for the existence of obstacles.As we can see from Figure10, the minimum number of sensors required varies when there are obstacles in the sensing area. The variations of the algorithms proposed in this paper are smaller. At the miss probability threshold 0.1, the minimum number of sensors required by the MAX_AVG_COV algorithm increases to 15, while that of our proposed algorithm is still 6, with a difference of 9. With the increase of miss probability threshold, the restriction of sensor deployment is getting smaller and smaller, and the minimum number of sensors required is also reduced. At the miss probability threshold 0.7, the minimum number of sensors required by our algorithm is 3, while the minimum number of sensors required by the MAX_AVG_COV algorithm is 5, with a difference of two. Since MAX_AVG_COV algorithm is a local optimum selection method, the localization of obstacles has a great influence on the sensor deployment. The proposed algorithm is a global optimal selection method; as long as the computation time is sufficient, we can always choose an optimal layout scheme, even a way of sensor deployment that can be chosen to avoid the effects of obstacles. From this, we can see that the algorithm proposed in this paper is obviously superior to MAX_AVG_COV algorithm.


## 7.1. Simulation Settings

The simulation experiment is completed on MATLAB. This paper assumes that the sensing grid is a regular square. It is assumed that each sensor has the same sensing accuracy; that is,α and β of each sensor are the same. Table 1 enumerates the common parameters of our simulation experiments.Table 1
Simulation parameters.
Parameter description Value Minimum sensing radiusrs Ten meters Adjustment parameterα 1 Device-dependent parameterβ 1


## 7.2. Simulation Results

In the first simulation, we study the weight’s impact on the data collection effects of the WSN. The sensor deployment schemes with the same number of sensors have different sensing trust degrees of the whole WSN in the case of the different weight matrices. We choose the sensor deployment with the highest trust degree of the whole WSN as the best sensor deployment. The weight of the sensing grid in the sensing region is related to the loss cost, occurrence probability, and tolerance time of monitoring abnormal events. The weight of all the grids constitutes the weight matrix of WSN. In order to compare the different sensing trust degrees of the whole WSN caused by the different weight matrices, we randomly set the estimated parameters in Tables2 and 3 for the weight matrices W1 and W2, respectively.Table 2
The estimated parameters ofW1.
The cost of damage resulting from an abnormal eventD(/hundred dollars) {11,2,9;0.5,1,9;0.5,3,8} The tolerance time of an abnormal eventT(/hours) {2,1,0.5;0.3,3,1;0.1,4,1} The probability of an abnormal event occurrence PL {0.1,0.3,0.8;0.9,0.25,0.1;0.4,0.6,0.7}Table 3
The estimated parameters ofW2.
The cost of damage resulting from an abnormal eventD(/hundred dollars) {1,0.5,8;3,10,1;0.5,0.5,1} The tolerance time of an abnormal eventT(/hours) {1,3,8;0.1,3,1;0.9,2,1} The probability of an abnormal event occurrence PL {0.1,0.2,0.7;0.2,0.1,0.9;0.1,0.1,0.1}The number of sensors is set to 5. The number of abscissa grids isM=3, and the number of ordinate grids is N=3. We can see that the different sensing trust degrees are obtained by different weight matrices in Figure 5. When the number of sensors is 5, there are 126 sensor deployment methods, that is, 126 combinations. In Figure 5(a), the sensing trust degree of the WSN which is caused by the sensor deployment corresponding to the 118th combination is highest, up to 1.424. The sensing trust degree of the WSN which is caused by the sensor deployment corresponding to the 23rd combination is minimum, only 0.9707. In Figure 5(b), the sensing trust degree of the WSN which is caused by the sensor deployment corresponding to the 71st combination is highest, up to 1.504. The sensing trust degree of the WSN which is caused by the sensor deployment corresponding to the 71st combination is minimum, only 0.8902. The sensing trust degree of the best combination is about two times that of the worst one. Because of the weight difference, the effect of data collection on the same number of sensors is different. Finally, it is necessary to study the influence of grid weight on sensor deployment.Figure 5
The performance of different weight matrices. (a) Weight matrixW1 and (b) weight matrix W2.
(a)
Weight matrixW1 (b)
Weight matrixW2In order to further analyze the impact of grid weights on data collection, we compare the best deployed sensor locations with the worst locations in the case of the two different weight matrices. In Figure6, these ● denote the sensor locations with the highest sensing degree of the whole WSN, and these △ denote the sensor locations with minimal sensing degree. In Figure 6(a), the sensor deployment coordinates with the highest sensing degree of the whole WSN are {(1,3),(2,2),(2,3),(3,2),(3,3)}, and the sensor deployment coordinates with the minimal sensing degree are {(1,1),(1,2),(2,1),(3,1),(3,2)}. In Figure 6(b), the sensor deployment coordinates with the highest sensing degree are {(1,2),(1,3),(2,1),(2,2),(2,3)}, and the sensor deployment coordinates with the minimal sensing degree are {(1,1),(2,1),(3,1),(3,2),(3,3)}.Figure 6
Comparison of the best and worst sensor deployment.
(a)
Weight matrixW1 (b)
Weight matrixW2As is shown in Figure6, we can see that the sensors are deployed on the edge of the sensing area and in the grids with lower weights by the sensor deployment with the minimum trust degree of the whole WSN. However, the sensors are almost deployed on the center of the sensing area and in the grids with larger weights by the sensor deployment with the maximum trust degree.In the second simulation, we compare our proposed algorithm with MAX_AVG_COV [8]. We assume that the number of rows of the sensing matrix is 4 and the number of columns is 4. We measure the minimum number of sensors required, when miss probability threshold Mmin⁡ (corresponding to the minimum reliability of each grid Rmin⁡) varies from 0.1 to 0.7 with an increment of 0.1.As we can see from Figure7, the minimum number of sensors required decreases as the minimum reliability increases. When Mmin⁡ is 0.1, the minimum number of sensors required by the proposed algorithm is half the number in the MAX_AVG_COV algorithm. When Mmin⁡=0.7, the required number of sensors in our algorithm is less than 2 in the MAX_AVG_COV algorithm. Obviously, the algorithm proposed in this paper is superior to MAX_AVG_COV algorithm.Figure 7
The comparison for minimum reliability.In the third simulation, we study the presence of obstacles in the sensing area. Suppose there are 4 obstacles. The layout model of the obstacle of our proposed algorithm is shown in Figure8. The coordinates of the obstacles are set to OB={(2,2.5),(2.5,4),(2.5,1),(3.5,2)}.Figure 8
The layout model of the obstacle of our proposed algorithm.The layout model of the obstacle of the MAX_AVG_COV algorithm is shown in Figure9.Figure 9
The layout model of the obstacle of MAX_AVG_COV algorithm.Then,d10,14=0, d14,10=0, d6,7=0, d7,6=0, d8,12=0,  d12,8=0, d5,9=0, and  d9,5=0, where di,j denotes distance from the ith sensing grid to the jth sensing grid.We compare the minimum number of sensors required by the two algorithms, as shown in Figure10, when there are obstacles in the sensing region.Figure 10
The comparison for the existence of obstacles.As we can see from Figure10, the minimum number of sensors required varies when there are obstacles in the sensing area. The variations of the algorithms proposed in this paper are smaller. At the miss probability threshold 0.1, the minimum number of sensors required by the MAX_AVG_COV algorithm increases to 15, while that of our proposed algorithm is still 6, with a difference of 9. With the increase of miss probability threshold, the restriction of sensor deployment is getting smaller and smaller, and the minimum number of sensors required is also reduced. At the miss probability threshold 0.7, the minimum number of sensors required by our algorithm is 3, while the minimum number of sensors required by the MAX_AVG_COV algorithm is 5, with a difference of two. Since MAX_AVG_COV algorithm is a local optimum selection method, the localization of obstacles has a great influence on the sensor deployment. The proposed algorithm is a global optimal selection method; as long as the computation time is sufficient, we can always choose an optimal layout scheme, even a way of sensor deployment that can be chosen to avoid the effects of obstacles. From this, we can see that the algorithm proposed in this paper is obviously superior to MAX_AVG_COV algorithm.


## 8. Conclusion

In practical applications, especially for smart city wireless sensor network deployment, the inconsistency of data weights owing to relative criticalness in different sensing grids needs to be taken into account. In order to ensure the data collection of wireless sensor networks effectively, we propose a computing model of the sensing trust degree of the whole WSN. In this paper, the sensing region is divided into meshed grids. The weights of the sensing grids are estimated by seesaw mapping to reflect the combined effect of the variables related to abnormal events, including the probability of occurrence PC(i,j), loss cost, that is, the degree of impact D(i,j), and the tolerance time T(i,j). The computing model based on sensing trust degree takes into account the sensor location, the impact of the weight of sensing grid, and the obstacles in the sensing region. We study the impact of different sensor deployments on the sensing trust degree of the whole WSN. Our model can obtain as much information as possible when the number of sensors is given. Based on our proposed computing model and formulated optimization problem, we propose the sensor deployment algorithms. Our algorithms are designed for three cases: (1) the number of sensors is limited, (2) the minimum sensing precision is defined, and (3) there are some obstacles in the sensing area. In the simulation experiments, we find out that the sensing affections of different sensor deployment schemes with different weight matrices are different under the condition of the same number of sensors. When the sensing accuracy is limited, the minimum number of sensors needed by our sensor deployment algorithm is less than that of the conventional MAX_AVG_COV algorithm. In this work, the sensing grid is square. In our following research, we will study the sensor deployment scheme for irregular grids and reduce the computational complexity.



---

*Source: 5913836-2018-04-04.xml*