**Banteng Liu**

Zhejiang Shuren University, Hangzhou, 310015, China

Yourong Chen

Zhejiang Shuren University, Hangzhou, 310015, China

Zhejiang Shuren University, Hangzhou, 310015, China

Yourong Chen

Zhejiang Shuren University, Hangzhou, 310015, China

This study proposes a two-tiered network in which lower-power users communicate with one another through repeaters, has limited capacity and may interfere with one another if their transmitter frequencies are close and they share the same private-line tone. Motivated by cellular networks, this study gives a naive solution where the number of repeaters and their positions can be obtained analytically. This study further proposes an iterative refinement algorithm consisting of three fundamental modules that draw the Voronoi diagram, determine the centers of the circumscribed circles of the Voronoi regions and escape the local optimum by using external optimization.

PDF Abstract XML References Citation

Banteng Liu and Yourong Chen, 2012. Research on the Repeater Optimization Design in the Wireless Senor Networks
Based on Voronoi Algorithm. *Information Technology Journal, 11: 1790-1793.*

**DOI:** 10.3923/itj.2012.1790.1793

**URL:** https://scialert.net/abstract/?doi=itj.2012.1790.1793

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 f_{r}, transmitter frequency f_{t} and Private-line (PL) tone n_{PL}. A repeater responds only to signals on its receiver frequency that contain its PL tone and retransmits with the same PL tone. Both f_{r} and f_{t} are in the range [145, 148 MHz]. In this study, there are |f_{r}-f_{t}| = 0.6 MHz and n_{PL} = 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{V_{u}, V_{r}, V_{ur}, V_{rr}}. V_{u} = {u_{1}, u_{2},...., u_{N}} and V_{r} = {r_{1}, r_{2},...., r_{N}} denote the sets of users and repeaters. E_{ur} is the set of directed links from users to repeaters and between repeaters. A user is identified by a location (x(u_{i}), y(u_{i})) in the plane and a repeater r_{j} is identified by its location, receiver frequency, transmitter frequency and PL tone as (x(r_{j}), y(r_{j}), f_{r}(r_{j}), f_{t}(r_{j}), n_{PL}(r_{j})). The frequencies of a repeater r_{j} satisfy f_{r}(r_{j}), f_{t}(r_{j})∈[145, 148 MHz] and |f_{r}(r_{j}-f_{r})| = 0.6 MHz (Zhou, 2008). Since the considered area is circular with radius Φ, the location of a user or a repeater satisfies x^{2}+y^{2}≤Φ^{2}, where Φ = 40mi. A directed link from u_{i} to r_{j} exist if |u_{i}-r_{j}|≤r. A directed link from r_{j} to r_{k} exists (i.e., (r_{j}, r_{k}∈E_{rr})) if |r_{j}-r_{k}≤R|, the transmitter frequency of r_{j} equals the receiver frequency of r_{k} (i.e., f_{t} (r_{j}) = f_{r}(r_{k})) and they share the same PL tone (i.e., n_{PL}(r_{j} = n_{PL}(r_{k}))). 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 r_{j}, there is connected area (S_{V}(r_{j})), the Voronoi region of r_{j}, such that for every point inside r_{j} is the nearest repeater and for every point outside, r_{j} 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 f_{c} = 0.6 MHz.

Every user is covered by at least one repeater. That is, for every u_{i}, ∃r_{j} such that (u_{r}, r_{j})∈E_{ur} (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 S_{r}(u_{i}) of user u_{i} is the area in Γ that can be covered by at least one reachable repeater of u_{i} (each repeater covers a circle with radius R).

The set of reachable repeaters R_{r}(u_{i}) for u_{i} consists of: repeaters directly reachable by u_{i} (i.e., the repeaters located within the circle with radius r and centered at u_{t}); repeaters reachable through links in Err from the directly-reachable repeaters.

Figure 1 illustrates a simple example where r_{2} can be directly reached by u_{1} and r_{4} and r_{5} can be further reached starting from r_{2}. Two nearby repeaters, r_{2} and r_{3}, may not have a link between them, since they may not match in frequency or PL tone. The reachable repeaters of u_{1} are r_{2}, r_{4} and r_{5} and the reachable area of u_{i} 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 P_{r,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 = P_{r,out}/4πd^{2}.

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 Shannon’s information theory, the loss L_{s} is:

where, L_{s} is in dB, d is in km and f is in GHz. The actual power of the received signal P_{r,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 L_{f,out} = L_{in} = 20 dB (the loss of the feed system), L_{b} = L_{b,in} = 1 dB (other loss of the system), G_{out} = G_{in} 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 P_{r,out} = 100 w and normally a repeater can receive a signal with power no less than 1 μw (i.e. P_{r,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 P_{u,out} = 3.2 w and P_{u,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 Shannon’s theory is φ = Blog_{2}(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, E_{b}/N_{o} 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, I_{other} is the interference from other repeaters and I_{self} 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, P_{ur} 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 I_{other}/I_{self} = 0. Setting E_{b}/E_{O} = 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 r_{j} which has S_{V}(r_{j}) as the area of its Voronoi region, must satisfy ρS_{V}(r_{j})≤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 f_{c} = 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 f_{i,1} and transmitter frequency f_{i,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 N_{PL} = 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 |

- Srinivasan, V., C.F. Chiasserini, P.S. Nuggehalli and R.R. Rao, 2004. Optimal rate allocation for energy-efficient multipath routing in wireless Ad Hoc networks. IEEE Trans. Wireless Commun., 3: 891-899.

Direct Link - Yin, S. and X. Lin, 2005. Multipath minimum energy routing in Ad Hoc network. IEEE Int. Conf. Commun., 5: 3182-3186.

CrossRefDirect Link - Busse, M., T. Haenselmann and W. Effelsberg, 2006. TECA: A topology and energy control algorithm for wireless sensor networks. Proceedings of the 9th ACM International Symposium on Modeling Analysis and Simulation of Wireless and Mobile Systems, October 2-6, 2006, Torremolinos, Spain, pp: 317-321.

CrossRefDirect Link - Wu, X., M. Zhou, L. Meng, J. Hua, K. Zhou and T. Wu, 2010. Connection stability analyze based on LEACH algorithm for mobile Ad Hoc network. Inf. Technol. J., 9: 1212-1216.

CrossRefDirect Link - Zhou, K., L. Meng, Z. Xu, G. Li and J. Hua, 2008. A dynamic clustering based routing algorithm for wireless senor networks. Inform. Technol. J., 7: 694-697.

Direct Link - Jun, D. and L. Wei-Hua, 2010. A security routing optimization scheme for multi-hop wireless networks. Inform. Technol. J., 9: 506-511.

CrossRefDirect Link - Nurul Huda, M., F. Yasmeen, E. Kamioka and S. Yamada, 2007. Optimal path selection in MANET considering network stability and power cost. Inform. Technol. J., 6: 1021-1028.

CrossRefDirect Link - Sharma, S., R.C. Jain and S. Bhadauria, 2006. A power efficient encryption algorithm for multimedia data in mobile Ad hoc network. Trends Applied Sci. Res., 1: 416-425.

CrossRefDirect Link - Sharma, S., R.C. Jain and S.S. Bhadauria, 2006. Simulation study of congestion adaptive routing algorithm for mobile Ad hoc network. Trends Applied Sci. Res., 1: 368-378.

CrossRefDirect Link - Sharma, S., R.C. Jain and S.S. Bhadauria, 2007. SBEVA: A secured bandwidth efficient variance adaptive routing protocol for mobile Ad hoc network. Asian J. Inform. Manage., 1: 1-10.

CrossRefDirect Link - Al-Sharabi, N.A.N., L.R. Fa and M.H. Algamali, 2008. Applied packet received time prediction to reactive ad-hoc routing protocol. J. Applied Sci., 8: 1035-1041.

CrossRefDirect Link - Mahmood, K., I. Hameed, K. Rashid and A. Qayyum, 2003. Secure banking: Authenticating peer-to-peer Ad Hoc interactions. J. Applied Sci., 3: 346-359.

CrossRefDirect Link