Research Article
Research on the Repeater Optimization Design in the Wireless Senor Networks Based on Voronoi Algorithm
Zhejiang Shuren University, Hangzhou, 310015, China
Yourong Chen
Zhejiang Shuren University, Hangzhou, 310015, China
Amplify-and-forward relay networks are very helpful for long-distance communication. Through relay nodes, low-power users can communicate with one another in situations where direct user-to-user communication would not be possible (Baek and de Veciana, 2005). In many networks, the nodes are homogeneous and a node can simultaneously play the roles of source node, sink node and relay node. In other scenarios, the relay nodes usually do not initiate communications but only help communications between other nodes (Srinivasan et al., 2004).
In general scenarios, the capacity of a repeater and interference among nearby repeaters should be taken into account. This paper proposes a model in which each repeater can simultaneously manage at most C users and two nearby repeaters interfere with each other if their transmitter frequencies are close and they share the same private-line tone. Our objective is the fewest repeaters that can satisfy the users' communication requirement. In this model, two requirements should be satisfied (Yin and Lin, 2005). Every user is covered by at least one repeater; every user can communicate with any other user.
According to the references, the circle-covering problem is NP-hard and is usually very time-consuming even for a small number of circles (Busse et al., 2006; Foulds, 1984).
Motivated by cellular networks, this study gives a naive solution in which the number of repeaters and their positions can be obtained analytically. In numerical simulation, this naive solution performs unexpectedly well.
VORONOI MODEL
Given a circular flat area Γ of radius Φ, this model should determine the fewest radial repeaters to accommodate N users. A repeater is a combination receiver/transmitter that picks up weak signals, amplifies them and retransmits them on a different frequency. The three parameters characterizing a repeater are receiver frequency fr, transmitter frequency ft and Private-line (PL) tone nPL. A repeater responds only to signals on its receiver frequency that contain its PL tone and retransmits with the same PL tone. Both fr and ft are in the range [145, 148 MHz]. In this study, there are |fr-ft| = 0.6 MHz and nPL = 54PL tones available (Wu et al., 2010).
The maximal communication distance r from a user to a repeater is the same for every user and it is considerably smaller than the communication radius R of a repeater. Every user should be covered by at least one repeater.
The primary problem is to determine the minimum number of repeaters to satisfy the communication requirement. This study uses a two-tiered directed network D{Vu, Vr, Vur, Vrr}. Vu = {u1, u2,...., uN} and Vr = {r1, r2,...., rN} denote the sets of users and repeaters. Eur is the set of directed links from users to repeaters and between repeaters. A user is identified by a location (x(ui), y(ui)) in the plane and a repeater rj is identified by its location, receiver frequency, transmitter frequency and PL tone as (x(rj), y(rj), fr(rj), ft(rj), nPL(rj)). The frequencies of a repeater rj satisfy fr(rj), ft(rj)∈[145, 148 MHz] and |fr(rj-fr)| = 0.6 MHz (Zhou, 2008). Since the considered area is circular with radius Φ, the location of a user or a repeater satisfies x2+y2≤Φ2, where Φ = 40mi. A directed link from ui to rj exist if |ui-rj|≤r. A directed link from rj to rk exists (i.e., (rj, rk∈Err)) if |rj-rk≤R|, the transmitter frequency of rj equals the receiver frequency of rk (i.e., ft (rj) = fr(rk)) and they share the same PL tone (i.e., nPL(rj = nPL(rk))). Clearly, we need to know the locations of users and repeaters.
A network D is a solution if the following three conditions (Ω1, Ω2, Ω3) are all satisfied.
For simplicity, we assume that users are uniformly distributed and each communicates with the nearest repeater. Each repeater can manage at most C users at the same time. For a repeater rj, there is connected area (SV(rj)), the Voronoi region of rj, such that for every point inside rj is the nearest repeater and for every point outside, rj is definitely not the nearest repeater. The number of users inside the Voronoi region of a repeater must be no more than its capacity (Jun and Wei-Hua, 2010).
If two repeaters share the same PL tone and are less than 2R apart, the difference between their transmitter frequencies must be no less than the threshold fc = 0.6 MHz.
Every user is covered by at least one repeater. That is, for every ui, ∃rj such that (ur, rj)∈Eur (Nurul Huda et al., 2007).
Our goal is a solution with the minimum number of repeaters M. Although every user is covered by at least one repeater, the user's signals may not reach the desired position in Γ, since the coverage of a repeater is also limited and the solution does not guarantee a multi-hop path through several repeaters to reach the desired position. Ignoring the small area that can be reached directly by a user without the help of a repeater, the reachable area Sr(ui) of user ui is the area in Γ that can be covered by at least one reachable repeater of ui (each repeater covers a circle with radius R).
The set of reachable repeaters Rr(ui) for ui consists of: repeaters directly reachable by ui (i.e., the repeaters located within the circle with radius r and centered at ut); repeaters reachable through links in Err from the directly-reachable repeaters.
Figure 1 illustrates a simple example where r2 can be directly reached by u1 and r4 and r5 can be further reached starting from r2. Two nearby repeaters, r2 and r3, may not have a link between them, since they may not match in frequency or PL tone. The reachable repeaters of u1 are r2, r4 and r5 and the reachable area of ui is the union of their coverage areas. The following condition must be satisfied to guarantee every user can in principle reach any position of the considered area through multi-hop repeaters (Sharma et al., 2006a).
A network D is a strong solution if (Ω1, Ω2, Ω3) are all satisfied. When R≥2Φ, any solution is a strong solution.
Fig. 1: | An illustration of repeaters |
To find a strong solution is much more difficult than to find a solution and the two tasks are equivalent only if R≥2Φ. This study assumes that there is no interference from fog, rivers, hills, buildings, sunspots, etc. (Sharma et al., 2006b).
Let Pr,out be the power of the signal transmitted by a repeater. Its average power P in a unit area at a distance D from the repeater is p = Pr,out/4πd2.
According to antenna theory, the effective receiving area of an antenna is λ2/4π, where λ the wavelength of the signal is. So the receiving power of the signal is as following:
Replacing λ by c/f, where c is the velocity of light and f is the frequency of the signal, we obtain:
In terms of Shannons information theory, the loss Ls is:
where, Ls is in dB, d is in km and f is in GHz. The actual power of the received signal Pr,out is as following (Sharma et al., 2007):
From one repeater (transmitter) to another repeater (receiver), the equations that hold and the conventional values are Lf,out = Lin = 20 dB (the loss of the feed system), Lb = Lb,in = 1 dB (other loss of the system), Gout = Gin 39 dB (the gain of the f antenna) (Al-Sharabi et al., 2008).
For this problem, the frequency of signals is about 146.5 MHz (the midpoint of the available spectrum 145-148 MHz) and thus:
The effective radiated power of most repeaters is Pr,out = 100 w and normally a repeater can receive a signal with power no less than 1 μw (i.e. Pr,in≥1 μw). According to above, the communication radius of a repeater is R≈85.5 mi. Analogously, the average working power for a user (according to several wireless devices) is Pu,out = 3.2 w and Pu,in≥1 μw, resulting in a communication radius r ≈ 15.28 miles (Mahmood et al., 2003).
We calculate the capacity of a repeater. Ignoring background noise and the interference, we assume that signals from one repeater do not affect others. A mainstream method to estimate the capacity of information over a noisy channel, according to Shannons theory is φ = Blog2(1+SNR).Where φ is the information bit rate (dB), SNR is the signal-to-noise ratio (dimensionless) and B is the total bandwidth (Hz).
The transmitter frequency in a repeater is an exact value rather than in a broad band. We use the equation:
where, Eb/No is the level that ensures operation of bit-performance at the level required for digital voice transmission, G is the gain of the antenna, V is the gain of voice, Iother is the interference from other repeaters and Iself is the interference of a repeater with itself. The SNR can be regarded as the ratio of effective information in the total received signal:
where, Pur is the power of the signal from a single user as received by the repeater (measured in watts). Normally, G = 39 dB = 7966.40 w and V = 0.4 dB = 1.07 w (in the calculation, the units must be watts). We ignore interference from other repeaters: We set Iother/Iself = 0. Setting Eb/EO = 18 dB = 63.01 w (the bit energy-to-noise density ratio always ranges from 5 to 30 dB; we set it at the midpoint 18 dB), we get the capacity of a repeater as:
Because users are mobile, the (fixed) repeaters must cover all of the considered area Γ. A solution for one distribution of users may not be a solution for another distribution. Therefore, a practical solution should not depend on a specific distribution.
Consequently, we use a continuous uniform distribution instead of a discrete uniform distribution of users. The user density is ρ = N/πΦ2.Omitting the bow-irrelevant Ω2, the other three constraints changed to: Every repeater rj which has SV(rj) as the area of its Voronoi region, must satisfy ρSV(rj)≤C. Every point is covered by a repeater. The reachable area of every point (considering that at every point, there can be user) is equal to the considered area Γ. In the frequency range [145, 148 MHz] with fc = 0.6 MHz, in a PL tone, if R≥2Φ, there are almost 6 different repeater transmitter frequencies without interference (145.0, 145.6, 146.2,..., 148.0 MHz).
Let repeater i have receiver frequency fi,1 and transmitter frequency fi,2. With more than 6 repeaters, there must be at least one pair i and j with inverse frequencies. Repeater i may amplify signals and send them to repeater j and repeater j may amplify those signals and send them back to repeater i and so on. To avoid this problem, we put only no interacting repeaters in a PL tone group; the maximum size of such a group is 5. So when R≥Φ, with NPL = 54 different PL tones, the maximum number of repeaters without any interference is 324 and without any interactions is 270. Therefore, if the required number of small circles is no more than 324, we do not need to consider interference avoidance but just set repeaters not to interfere with one another; if the required number is no more than 270, we can make sure there will not be interactions between repeaters.
According to the connectivity constraint, the (integer) number of repeaters M hould satisfy:
According to the capacity constraint should satisfy:
For N = 10000, we need M≥85.
We propose a two-tiered network model, where lower-power users communicate with one another through repeaters, taking into account in our model capacity constraints and interference. We give a naive solution in which the number of repeaters and their positions can be obtained analytically. We further develop an algorithm based on Voronoi diagrams which outperforms the naive solution. For 1,000 users, the algorithm proposes 11 repeaters which we prove to be optimal. For the 10,000 users, the algorithm obtains a solution with 104 repeaters. Moreover, we offer an algorithm, based on maximum and minimum spanning trees, to assign frequencies and private-line tones. This algorithm does not introduce any new repeaters yet can broaden the reachable areas of users.
Compared with the related model for sensor wireless networks and mo- bile communication networks, our model is more general. Our algorithm is effective and efficient: It runs much faster than the simulated annealing approach and is better able escape the local optimum than another iterative refinement algorithm. Our algorithm does not require any specific geographical features of the considered area, while many efficient circle-covering algorithms work well only for squares.
There are also two considerable weaknesses in our work:
• | We have not developed an algorithm that satisfied the constraint of global reach ability without adding too many repeaters |
• | Our model does not take into account the erogeneity of users or repeaters, or wave reflection and refraction by the atmosphere |