Rearch on Optimal Coverage Problem of Wireless Sensor Networks剧本下载
Xueqing Wang1 , Fayi Sun2and Xiangsong Kong1
1School of Mechanics & Civil Engineering, China University of Mining & Technology Beijing
100083 Beijing, China
2Weifang University of Science and Technology, 262700 Shouguang, Shandong, China
Abstract: -In a wireless nsor network, the size of radio nodes has direct relation to the cost of total wireless nsor networks, and at the same time, the problem is cloly connected to wireless nsor networks’ performance, such as robust, fault-tolerance, and further more, it is considered at first as wireless nsor networks are designed. Therefore, the rearch on the size of radio nodes has significant meanings of theory and practice to design of wireless nsor networks. The paper simplifies complex coverage problem step by step. By means of math modeling, theoretical analysis and formula deducting, classical geometric theories and the method of mathematics induction are adopted, at last, the analysis formula of minimum number of nodes is theoretically educed under circumstances of entir
e and amless coverage in WSN. In addition, it is worth mentioning that the conclusion is the full same with computing the number of communication nodes of wireless nsor networks.
Key-Words: -Wireless nsor networks; coverage problem; nsor field; nsor nodes
1.INTRODUCTION
Since 1990s, more and more rearchers paid great attention to micro nsors capable of nsing, computing and wireless communicating, and Wireless Sensor Networks (WSN) made up of them with rapid development of the technologies of wireless communicating, embedded computing, nsing and Micro-Electro-Mechanical Systems (MEMS) [1, 2]. Micro nodes are lf-organized, distributed at random, integrated with nsor unit, data processing unit and communication unit. Sensors cooperatively and real-time n, monitor and collect physical phenomena people are interested in. And then, the information are procesd, thereby, knowledge is acquired in details and with accuracy. Huge application merit and development promi attracts attention of them who are people from industry, academic rearchers, and military department [3].
In wireless nsor networks, nodes are usually deployed at random in nsor field, therefore, coverage problem is one of basic problem, and the problem has some influence on monitoring and tr
acking object. Reference [4] propod polynomial time algorithms to find the maximal breach path and the maximal support path that are least and best monitored in the nsor networks. A coverage-prerving node scheduling scheme is prented in [5] to determine when a node can be turned off and when it should be rescheduled to turn on again. How to find the minimal and maximal exposure path that takes the duration that an object is monitored by nsors is addresd in [6, 7, 8]. Localized exposure-bad coverage and location discovery algorithms are propod in [9]. Reference [10] prents that different kinds of holes can form in such networks creating geographically correlated problem areas such as coverage holes, routing holes, jamming holes, sink/black holes and worm holes, etc, detail different types of holes, discuss their characteristics and study their effects on successful working of a nsor network. Reference [11] propos a probe-bad density control algorithm to put some nodes in a nsor-den area to a doze mode to ensure a long-lived, robust nsing coverage. The effectiveness of cluster-bad distributed nsor networks depends to a large extent on the coverage provided by the nsor deployment in [12] and the paper propos a virtual force algorithm (VFA). Document [13] proves the t of active nodes lected by a connected
2009 International Conference on Communications and Mobile Computing
dominating t (CDS) provides full coverage and connectivity. Document [14] address how to dynamically maintain two important measures on the quality of the coverage of a nsor network: the best-ca coverage and worst-ca coverage distances, and gives relevant algorithm.
In this paper, the problem is rearched: minimum number of radio nodes is demanded in a nsor field if the field is covered entirely and amlessly.
2. PROBLEM DESCRIPTION
To illustrate in figure 1, theoretical hypothes are shown below:
Hyp.1 a nsor’s detecting ability is omnidirectional, that is , its coverage range is a disk who radius is r and who area is D (D=πr2).
Hyp.2 in a nsor field, all nsors’ radio power is uniform, that is, the radio radius r of all nsors is equal.
Hyp.3 in a nsor field, all nsors are in the same plane.
Fig.1 Sensors’ nsing range and WSN’ S nsor field
According to above hypothes, the minimum
number of nodes, that is demanded in order to entirely and
amlessly cover the nsor field to illustrate in figure 1 is
the number if coverage area of every node in it is maximal.
Expression in math is:
For ,,,and
is max imal, or max
x F i x D D
i j
j N
D
j
j N
∀∈∃∈
∈
∈
∪
pentile∪
so as t o
Where x is any point in the nsor field, F is the nsor
field, D is disk of every node, N is number of nodes and
∪ is union.
3. RELATED THEORIES
Theorem 1. Area of inscribed equilateral triangle is
昆士兰大学要求
maximal in all inscribed triangle of a circle.
Proof: To illustrate in figure 2, in circle ⊙A, △C1C2C3
and △C1’C2C3 are inscribed triangle of it. C1P1⊥C2C3
and C1P1 is through the center of ⊙A. C1’P2⊥C2C3
and C1’ is any point except for point C1.
Obviously, for 1'1'1,
C A C C
blue plate special
∀∈≠
⊙，i f then |C1P1|
＞|C1’P1| (|C1P1|denotes the length of gment C1P1).
Moreover ∵|C2C3|=|C2C3|
∴ area of △C1C2C3 ＞△C1’C2C3
∵C1’ is discretional
∴ area S of △C1C2C3 is maximal
Here, |C1C2|=|C1C3|
Moreover, ∵symmetry
∴in a similar way, |C2C1|=|C2C3| and |C3C1| = |C3C2|
∴|C1C2|=|C2C3|=|C3C1|
∴△C1C2C3 is equilateral triangle and its area is
maximal.
Fig.2 Graphic illustration of theorem 1
Theorem 2. To illustrate in figure 3, if amless topology
area of 3 amless topology disks: D1, D2 and D3 get
maximum, then 3 circles: C1, C2 and C3 correspondingly四级题目
encircling 3 disks must interct at only point A. That is,
D1∩D2∩D3≠Φ, if max(D1∪D2∪D3), then C1∩C2∩
C3 ={A}.
Proof: Max(D1∪D2∪D3) →min(D1∩D2∩D3)
∵D1∩D2∩D3≠Φ
According to the definition of interction
∴C1∩C2∩C3 ={A}
Fig.3 Graphic illustration of theorem 2
Theorem 3. Seamless topology area of 3 amless
topology disks: D1, D2 and D3 is maximal and its value is
2 if
3 circles: C1, C2 and C3 correspondingly
encircling D1, D2 and D3 interct at point A and △C1C2C3 is equilateral triangle.
Proof: Let max(D1∪D2∪D3) be true, according to theorem 2, then ⊙C1, ⊙C2 and ⊙C3 must interct at point A .
Furthermore, ∵|AC1|=|AC2|=|AC3|=r ∴point C1, C2 and C3 are concyclic ∴△C1C2C3 is inscribed triangle of ⊙A
let area of △C1C2C3 be maximal, according to theorem 1, then △C1C2C3 must be equilateral triangle.
Since area of △C1C2C3 get maximum, here, area of gray field in figure 4(a) is minimal to a certainty. That is, area of gray field in figure 4(b) is minimal, i.e. max(D1∪D2∪D3).
Fig.4 Graphic illustration of theorem 3
Area S 1 of gray field in figure 5(b):
12'23S AC A AC P ＝ar ea of ct or －ar ea of △
2301 23*3360
2
r C P AP π
＝
－
()2
1
212
2
r
r
π＝
－
22
24
π－＝
(1)
教育部考试中心网站
∵symmetry
∴area S 2 of gray field in figure 5(c)
2
24*1S S ＝
(2)
∵symmetry
∴area S 3 of gray field in figure 5(d)
232*2S S ＝
(3)
∴Area S 4 of gray field in figure 5(e)
2
22433
S D S r r ππ−－＝＝－
2
3
r π+＝
(4)minix
∴Area S 5 of gray field in figure 5(f)
42533S S S =∗+∗
应试教育英文2
3
2
33=+ 2
(5)
再别康桥英文译稿∴the problem proves to be true.
C1
Fig.5 Graphic illustration of computing area
From the process of proving, we notice that ∠
AC2B =60°, ∴360°∕∠AC2B = 360°∕60°＝ 6, i.e. A circle ⊙C1 is exactly covered by 6 circles ⊙C 2, ⊙C 3, ⊙C 4, ⊙C 5, ⊙C 6, and ⊙C7. The ca is
illustration in figure 6.
Fig.6 Graphic illustration that one circle is amlessly
covered by 6 circles
4. MINIMUM NUMBER OF NODES IN WSN THAT IS COVERED ENTIRELY AND SEAMLESSLY
According to the above theorem 3, in a given nsor field F , the illustration in figure 7 shows the topology graph. From the figure , it is known that a node is added every time, then the increment δ of coverage area is
2222
6
33r D S πδπ=−∗=−∗－
2
=
(6)
∴the number N of nodes in the nsor field (Some of
boundary nodes are ignored) is
2
2F
F N δ鹅的英文
=
=
=
(7)
Fig.7 Graphic illustration of counting the number of nodes
5. CONCLUSION
In wireless nsor networks, the paper simplifies complex coverage problem step by step. By means of math modeling, theoretical analysis and formula deducting, the analysis formula of minimum number of nodes is theoretically educed under circumstances of entire and amless coverage in WSN. It resolves a math problem of WSN in theory. The rearch on the number of nodes has significant meanings of theory rearch and network designing of WSN. On its basis, the theory has some influence on algorithm rearch and protocol designing. This is the content that I am going to work later.
REFERENCES
[1] Akyildiz I F, Su W, Sankarsubramanlam Y , et al. Wireless
nsor Networks: a Survey. Computer Networks, 2002, 38:393-422.
[2] G.J. Pottie and W.J. Kair. Wireless integrated network
nsors. Commun. ACM, 2000, 43(5): 51-58.
[3] K. Sohrabi, J. Gao, V . Ailawadhi and G .J. Pottie. Protocols
for lf-organization of a wireless nsor network. IEEE Personal Commun, 2000, 7(5): 16-17.
[4] S.meguerdichian, F. Koushanfar, G . Qu and M. Potkonjak.
Coverage problem in wireless ad-hoc networks. IEEE infocom, 2001:1380-1387.
[5] D. Tian and N.D. Georganas. A coverage-prerving node
scheduling scheme for large wireless nsor networks. ADM Int’l Workshop on Wireless nsor Networks & applications, 2002.
[6] S. Meguerdichian, F. Koushanfar, G . Qu et al. Exposure in
wireless ad-hoc nsor networks. ACM Int’l Conf. On Mobile Computing and Networking (MobiCom), 2001, 139-150.
[7] Seapahn Megerian, Farinaz Koushanfar, Gang Qu et al.
Exposure in wireless nsor networks: theory and practical solutions. Wireless Networks, 2002, 8:443-454.
[8] G . Veltri, Q. Huang, G .Qu and M. Potkonjak. Minimal and
maximal exposure path algorithms for wireless embedded nsor networks. ACM Int’l Conf. On Embedded Networked Sensor Systems (SenSys), 2003:40-50.
[9] S. Meguerdichian, S. Slijepcevic, V . Karayan and M.
Potkonjak. Localized algorithms in wireless ad-hoc networks: location discovery and nsor exposure. ACM Int’l Symp. On Mobile ad hoc Networking and Computing (MobiHOC), 2001:106-116.
[10] Nadeem Ahmed, Salil S. Kanhere, Sanjay Jha. The holes
problem in wireless nsor networks: a survey. Mobile Computing and Communications Review, 9(2): 4-18.
[11] F. Ye, G . Zhong, S. Lu et al. PEAS: a robust energy
conrving protocol for long-lived nsor networks. Int’l Conf. On Distributed Computing Systems, 2003.
[12] Yi Zou, Krishnendu Chakrabarty. Sensor deployment and
target localization in distributed nsor networks. ACM Transactions on Embedded Computing Systems, 2004, 3(1): 61-91.
[13] Yi Zou and Krishnendu Chakrabarty. A distributed
coverage- and Connectivity-Centric Technique for Selecting Active Nodes in Wireless Sensor Networks. IEEE Transactions on Computers, 2005, 54(8): 978-990.
[14] Hai Huang, Andrea W.Richa. Dynamic coverage in Ad-Hoc
nsor networks. Mobile Networks and Applications, 2005, 10:9-17.
