A non-linear programming method for the distribution of
VHF repeaters
1.Introduction
With the development of technology, the limitation of VHF radio line-of-sight transmission and reception has been solved by the use of repeaters. What’s more, the technology of “continuous tone-coded squelch system” (CTCSS) help to mitigate the interference problems between repeaters which are closed in geographical distance.
In order to use this technology better, the number of repeaters and how to distribute them are in view. In this paper, seven models are used to simulate the repeaters’ distribution in the circular flat area of 40 miles radius and find out the minimum of repeaters for 1,000 and 10,000 simu ltaneous users. To simplify and to easily understand the model, evenly distributed principle is applied to the models. To find out the optimal solution, we calculate the minimum distance and PL number as constraints by using the regularity of trans mission between repeaters. We firstly come to one-dimension model and follows in second- dimension flat model, non-flat model and the three-dimension model to solve the similar problem such as the distribution of satellite, and then we have a lot of results and analysis.
2.Assumptions
●The users meet the evenly distributed principle in the circle. To meet the minimum number of repeaters, the repeaters meet the evenly distributed principle too.
● One repeater for one user service.
●The system must be a network, in which a user can transmit information to another user wherever in the area.
● Each repeater has only one receiv e frequency.
● Only the same repeaters which share the same frequency and PL number cause interference.
● The transmission cycle: According to the regularity of transmission—each repeater can only transmit frequency to the either 600 kHz above or 600 kHz below its own receive frequency, the same repeaters can only transmit frequency in this way: transmit from repeater A to B, from B to C, from C to B, finally from B to A (we can add more repeaters in this circle) to avoid the interference problems.
●All of the transmission cycle for each pair of same repeaters can be included in a circle—called including circle, and the whole area can be covered by many including circles.
● The distance of interfere and the distance of communication is Proportional, we as sume it’s 2.When two repeaters want to communicate , their distance must be less than the communication distance, and if two repeaters have intersections in their communication distance, The user’s transition in the intersection may be in trouble.
Figure 0
3. Symbols
n : In a transmission cycle, the minimum distance between two same repeaters. x : The radius of a unit.
d : Th
e repeaters interference distance. N : The number o
f repeaters.
R : The radius of the flat circle which is given in the problem. a : The number of repeaters in per unit area. 4. Models
4.1Frequency Division Model
Let’s divide the frequency into six segments, as following figure. Because it’s clear that the more available number of different frequencies there are, the more repeaters the system can carry. To demonstrate the decomposition effect better, Figure1 is given.
Figure1.
In Figure1, each repeater can transmit frequency to only two repeaters with specific frequency. That means if one repeater wants to connect with another repeater which has a different frequency; the frequency must be transmitted through at least one more repeater. For example, if A wants to connect with D , the way frequency transmitted is A →B →C →D . 4.2Single Line Model
As the following Figure2, A is the repeater with the same frequency and PL number. So the distance between A and A
may decide the system's capacity. Let's have a look at the following formula.
600 148MHz
145MHz
6
5
4
3
2
1
Figure2.
Formula (1):
N = πR 2 ?a
R is the radius of the flat region, a is the number of repeaters in per unit area. And N is the total num of the repeaters. Formula (2):
a =
total_number _in_a_unit
π(max_length _in_a_unit ?min_interfere _distance min_interval
)
2
total_number _in_a_unit means the number of repeaters in the unit area and the unit means a round region with a repeater in the center. Because the well-distributed users and well-distributed repeaters are even-distributed, the unit is described as a circle. So the max_length _in_a_unit is the circle’s radius which is represented by the maximum interval from the farthest repeater in the unit to the center repeater. The constant min_ interfere _distance means the minimum distance in which the two nearby repeaters can interfere with each other. And the min_interval means the minimum interval of the two nearby repeaters with the same frequency and PL number. Formula (3):
N =πR 2
total_number _in_a_unit
max_length _in_a_unit ?
min_interfere _distance 2
?min_interval 2
The formula is conducted by formula (1) and (2).
To let the repeaters work with no interference, the minimum distance between every two same repeaters (same frequency and same pl number) must be concerned. In order to avoid the interference, the inequality is given below:
d min ≤nx
To change this inequality, we get the results below:
x ≥
d min n
There is a relationship between N and the flat circle area:
N =πR 2
πx
2
Comprehending inequalities above all, here is the relationship between N and n :
N =
πR 2πx 2
≤
πR 2d min 2n 2
=π(R d min
)2n 2
A
A
The minimum distance
between the repeaters
To let the N no less than the users included, n is required as big as suitable. To get the minimu m number of repeaters, n must be suitable.
As we see, when the minimum value of the nearby repeaters' interval with the same frequency and same PL number is larger, the system's capacity is bigger, so we must think about some methods to improve the minimum value to accommodate suitable users.
The minimum distance
between the repeaters
A A
Figure3.
Let's image a line of repeaters, the head and tail of the line is A which we mention above, let's think of something specific. A is the third frequency, and the second repeater in the line may be the fourth frequency, and the next is the fifth frequency. But if the following one is the fourth frequency, the minimum distance between repeaters in the system is two. To large the minimum distance, we use an available PL to associates the following one.
3 4 5 4…
The quantity of groups
3454’5’4’’5’’…
The length of a group
Figure4.
In Figure4, w e make the “4”and“5” as a group, when the sequence increases, the minimum value of A-A is larger and in the line of repeaters, there is no repeated repeater which I mean the repeater with the same frequency and pl number, so this method improves the minimum value (as above, we mean the value is the interval of repeaters between two nearby ones). But the improvement of the minimum value is not unlimited. As the minimum value improved, the available PL number is decreasing. Then we must find the balance of the improvement of the minimum value and PL consume, so that we can use nonlinear programming to solve the problem.
Maybe, you will ask why the sequence must be like "3454545...”, because we assume a network which can connect with each other, for example A can contract with another A.
When there is an A in the single line, minimum value will not be expected large. But we can associate available PL to the A and the second sequence of A to A. We can also improve the
minimum value.
Figure5.
Now, let’s think it over. Let ’s refer to the Figure6 which represents the transition of different frequency repeaters. When it loop from a point to another, and finally return to the point itself (as the case in Figure5), according to the graph theory, it’s an Eulerian trace. So the path must be an even interval and when it moves a step, we use an available PL number. So this is the model for a single line of repeaters and we named the number of moves “num_moves ”.
Figure6.
Because the interval in a single line is even, we use 2?num_moves to represent the cost of PL numbers.
cost_by_a_single_line =2?num_moves
4.3MutiLines Model
There isn't only a line of repeaters like Single Line Model, there are many lines of repeaters (the repeaters are well-distributed, because the users are well-distributed). And many lines which begin with B\C\D... repeat like what is shown in the Figure7.
1
2
3
4
5
6
The distance expands with more PL number
A
A ’’ A ’ A
Figure7.
There are six frequencies. Because we use the repeater with same frequency but different PL in the line, the A represents one of six frequencies. 4.4Two-Dimension Model
And now, you may find the defect of the above model, it's an one-dimension model, and we must find a two -dimension model ,so we extend the above model:
Figure8.
The area is a circle, so we can get the total number and the max length in a unit which is the radius (the single line ’s length we discussed above). And the minimum dist of case D 1 is dist_1_d , which is minimu m distance of A-A. The dist_1_d is the minimum interval of two repeaters, which we talked about at the last part of section 4.2.
total_number _in_a_unit =num_moves ?num_dir
dist_1_d = 2?num_moves max_length _in_a_unit =2?num_moves
In the Fagure8, A can contact with many A . Because of the well-distributed users, the direction o f the lines is well-distributed and the repeaters in the line near the center can be conflicted. So we must associates some available PL number to the conflicted repeater to improve the minimum value. Next, we discuss the number of repeaters in a line we must associates some available PL number.
A
The number of direction is num_dir
A
A
A
B
B
B B
B
C C C C C A
A
A A A
For example, in Figure9:
Figure9.
The num_trans (which is defined in the next passage.) may be larger than 2, for example:
Figure10.
We assume to use variable num_conflict to represent the number of lines we must modify the repeaters' PL number depends on the minimum value of repeaters. We can assume the cost of PL number is a variable named num_trans , and it’s also the largest number of conflicting lines of adjacent. L et’s decide the number in non-linear programming.
conflicted
conflicted The repeater may be the same kind, and there is a conflict
A
A
Figure11.
We can get a simple formula as:
cost_by_near _conflict =(num_trans ?1+num_dir % num_trans )?num_conflict The num_dir is the number of lines. And "%" means mod, which seems like C Programming Language. It’s cle ar that num_trans means the number of total “trans-group ” in which the farthest two lines can be conflicted. The num_dir%trans means the left lines, and if the left lines are associated with the repeated PL number, it will be conflicted with the beginning one. So we must use all new PL number for the left one. And the minus one means the beginning repeater in the “trans-group ” will not be modified PL num.
And the conflicted repeaters ’ distance is decided by the triangle, we can use elementary mathematics to compute the distance.
Figure12.
And the conflict distance, we have got:
distance _2d =2?sin ?
(π/n ?num_trans)?num_conflict Now, we can represent the objective function, which is of course the number of repeaters which we marked as "result" which is the same to N .
2πnum _dir
num_cross
num_cross
trans N
N+1 N+2
1
4
3
2 1
What's the relationship between "result" and other factors? The "result" is decided by the number of repeaters in per unit area. And repeaters in per unit area are all the repeaters in per unit of that network like above formulas.
And what decides the min_interval ? It depends on the minimum value of repeaters in a line and the conflicted repeaters near the center , it’s the minimum of that two value.
Finally, we come to the PL number which is totally 54.The count of available PL number is inverse ratio to the minimum of the repeaters' interval, so we get a restrict equation. The total PL number must be smaller than 54.
cost_by_a_single_line + cost_by_near _conflict 6
i=1
6
i=1
≤54
And the minimum dist:
min_interval =min i =1 .. 6?(dist_d_1i ,dist_d_2i )
And the objective function:
N =πD 2
total_number _in_a_unit
max_length _in_a_unit ?
min_interfere _distance 2
?min_interval 26
i=1
Because of the overlapping of subsystems, the total repeaters in per area will be the sum of the repeaters in subsystems.
The reason why we don ’t reuse the PL number in A ?A when considering the B ?B is that the A and B … are well-distributed. And A ?A ’s distance may be different from B ?B ’s , and the system of A ?A will be overlapping with the system of B ?B . For the minimum interval, we must use a new PL number.
Considering the geometry inset, the dir_num must be 3 or 4 or 6. We can try each one. And maybe each system, such as A ?A ,B ?B , has its own dir_num . But with the limited time , we set all the dir_num same. And we also add some necessary but not important condition such as something is an integer.
Finally, we use lingo to do the non-linear programming. 4.5Single-Line Non-flat Model
When A communicates with A and there is a mountain between A and A , A can’t get to A directly. A must bypass the mountain. When this happens, the probability of conflict will be increased. We must use new PL number to avoid conflict, so the available PL number will be reduced and the minimum value of min_interva l will be decreased. If so, we can get a conclusion by the following formula. The capacity of system will be decreased, and if we want to accommodate the same number of repeaters as before, the primary solution will be changed for more available capacity. Then we probably get non-solution or the result will become larger.
Figure13.
4.6Two-Dimension Non-flat Model
The situation will be the same as before, but something will be different. In Figure14, A1 and A 2 may be conflicted, so are A3 and A4. But A 2 and A3 will not be conflicted, so the situation may be not as bad as we image in the single-line non-flat model. But it doesn’t turn well. The final result will be also increased.
Figure14.
And maybe you have imaged another situation(shown in Figure15). The situation seems to have no effect on primary model. We assume that the users and repeaters are well-distributed, so if A can avoid the mountain, because of the well-distributed model, the B\C\D … (which means other repeaters with different frequency from A ) will be conflicted again. So the situation is still bad.
Conflicted Unconflicted
Conflicted
Maintain
A
A 2
A 3
A 4
A 1
Conflicted
A
A A
A
Maintain
Figure15.
4.7Three-Dimension Model and Higher Dimensional Space Model
Just like the case of two-dimension, we can expand the model to three dimension and higher dimensional space model. We can apply some conclusion of space analytic geometry to re-compute the minimum distance of elements (maybe not repeaters), and this model can solve the distribution of satellite and other similar problems. 5. Simulation Results and Sensitivity
Because of the limitation of time, we only got a local optimal value. So, the data is not so precise . And with the data in the table, we can draw the distribution of repeaters. 5.1 Problem Results.
5.1.1 The result of problem without considering the geometry inset, so num _dir can be anything more than 3.
The distance of interfere is 4.
When the user comes to 1,000, the minimum number is 1,008 and the num_dir is 6. It means there will be six A around A and the num ?trans will be 3. The solution is local optimal in lingo, so it maybe not so precise.
Table1.The results of the different frequency for 1,000 users. The Frequency Num_Moves
Num_conflict
1 (145 MHz) 1 1
2 (145.6 MHz) 4 1
3 (146.2 MHz)
4 1 4 (146.8 MHz) 4 1
5 (147.4 MHz) 4 1
6 (148 MHz) 4
1
A
A
A
A
mountain
When the user comes to 10,000, the minimum number is 10,008 and the num_dir is 6. It means there will be six A around A and the num?trans will be 3.
Table2.The results of different frequency for 10,000 users.
The Frequency Num_Moves Num_conflict
1 (145 MHz) 1 1
2 (145.6 MHz) 1 1
3 (146.2 MHz) 1 1
4 (146.8 MHz) 2 2
5 (147.4 MHz) 3 1
6 (148 MHz) 1 1
5.1.2 The result of problem considering the geometry inset.
(1)The distance of interfere is 1
When the user comes to 1,000 ，The minimum number is 15814. And the “num_dir” is 6, it means there will be six A around A. Because the communication of network, the result is not as small as imagined, but suitable.I don't think it's too large for my assumption, As assumed, the distance for communication is 0.5, and the area will filled by the circle which radius is 0.5,so the least number for coverage of the region is 12800, so it's close to my result!
Table3.The results of the different frequency for 1,000 users.
The Frequency Num_Moves Num_conflict Num_trans
1 (145 MHz) 5 1 1
2 (145.6 MHz) 5 9 1
3 (146.2 MHz) 5 1 1
4 (146.8 MHz) 4 9 1
5 (147.4 MHz) 5 1 1
6 (148 MHz) 5 1 2
When the user comes to 10,000 ，The minimum number is 16838. And the num_dir is 6, it means there will be six A around A.
Table4.The results of different frequency for 10,000 users.
The Frequency Num_Moves Num_conflict Num_trans
1 (145 MHz) 6 1 1
2 (145.6 MHz) 4 1 3
3 (146.2 MHz) 6 1 1
4 (146.8 MHz) 3 1 1
5 (147.4 MHz) 5 1 1
6 (148 MHz) 5 4 1
(2)The distance of interfere is 4.
When the user comes to 1,000 ，The minimum number is 1137. And the num_dir is 6, it means there will be six A around A.
Table5.The results of the different frequency for 1,000 users.
The Frequency Num_Moves Num_conflict Num_trans
1 (145 MHz) 6
2 1
2 (145.6 MHz) 4 2 1
3 (146.2 MHz) 3 1 1
4 (146.8 MHz) 7 1 3
5 (147.4 MHz) 5 1 2
6 (148 MHz) 3 1 2
When the user comes to 10,000 ，The minimum number is 10,015. And the num_dir is 6, it means there will be six A around A.
Table6.The results of the different frequency for 10,000 users.
The Frequency Num_Moves Num_conflict Num_trans
1 (145 MHz) 1 1 2
2 (145.6 MHz) 2 2 3
3 (146.2 MHz)
4 1 4
4 (146.8 MHz) 14 1 2
5 (147.4 MHz) 1 1 4
6 (148 MHz) 1 3 1
5.2 The relationship between Users and Repeaters with considering the geometry inset.
When the distance of interfere is 4:
Table7.
Number of Users Number of Repeaters num_dir 1000 1,008 6
2500 2,501 6
5000 5,005 6
7500 8,834 6
10000 10,008 6
11000 11,134 6
12000 12,000 6
Figure16.
Figure17. Linear model Poly1:
f x=p
1?x+p
2
Coefficients (with 95% confidence bounds):
p
1
=1.011
p
2
=139.1
When the distance of interfere is 1.2:
This model is simplified to reduce the computing complex, so the solution only keeps the relationship, but the value is not precise.
Table8.
Number of Users Number of Repeaters num_dir
1,000 8,876 6
2,500 10,667 6
5,000 10,969 6
7,500 11,482 6
10,000 11,667 6
11,000 11,742 6
12,000 12,140 6
Figure18.
Figure19. Linear model Poly1:
f x=p
1?x+p
2
Coefficients (with 95% confidence bounds):
p
=0.1431
1
=1.03e+004
p
2
5.3 The maximum of t he system’s capacity with considering the geometry inset:
Table9.
The distance of interfere The maximum of repeaters The num of directions
1 342,247 6
2 85,561 6
3 38,027 6
4 21,390 6
8 5,374 6
10 3,422 6
12 2,377 6
Figure20.
Figure21.
General model Exp1:
f x=a?exp?(b?x)
Coefficients (with 95% confidence bounds):
a=1.219e+006
b=?1.275
5.4 The relationship between the maximum interfere distance and number of users.
Table10.
Number of Users Max Interfere Distance The number of directions
10,000 5.85 6
20,000 5.64 6
40,000 2.93 6
100,000 2.52 6
6.Predictions And Analysis
(1)When the distance of interfere is fixed, the relationship between minimum value of repeaters and
the user number is linearity. For this prediction, it’s easy to understand, the more users, the more repeaters. It can be verified with the result of “The relationship between users and repeaters with considering the geometry inset.”
(2)When the user number is fixed and the distance of interfere is increased, the slope is smaller. For
this prediction, when the distance of interfere is increased, the connection between the repeaters will be easier. That is to say we can increase the distance between two nearby repeaters within the communicated distance. Then the minimum value of repeaters will not be so large. But with the
distance of interference increasing, the system’s capacity will be decreased. So it may not accommodate 10,000 users. It can be verified with “The relationship between Users and Repeaters with considering the geometry in set.” and “The maximum of The system’s capacity with considering the geometry inset”
(3)The Maximum of users is exponential growth with the distance of interfere. When the distance of
interfere is decreasing, it means we can set more repeaters in a unit area. When the distance of interference is zero, which means we can set any number of repeaters, the prediction is clear. It can be verified by the “The maximum of the system’s capacity with considering the geometry inset”. (4)When geometric inset is considered, the best direction number is six. Because we can only have
equilateral triangle, quadrilateral and hexagonal to compose the circle, and the regular hexagon’s unit area is largest among the three, regular hexagon is chosen to compose the system. This prediction can be verified by all the results.
7.Recommendations
(1)When the number of users is small, we can improve the distance of communication, the distance of
interfere. So the minimum number of repeaters can be smaller.
(2)When the number of users is large, we can also improve the distance of communication, the
distance of interfere, but the distance of communication and interfere must be s uitable to accommodate enough repeaters to serve users.
(3)If the number of user is 10,000, please choose the repeater whose distance of interfere is about
5.85 miles. It’s enough.
8.Strengths and Weaknesses and Error Analysis
(1)Our Model uses non-linear programming to solve the problem, which can give something precise
and amazing, and we can have less assumed condition. So that we can give the problem a common solution.
(2)With the result of our model, we can get some important formulas and know more about the
problem’s essence.
(3)We don’t have enough time to wait for lingo to return the perfect solution, so we simply some of
the models. We assume all the frequency repeater group has share the same num_dir. In addition that the version of our lingo is low, and we can’t get a powerful lic ense to do more powerful thing.
9.Conclusion
To calculate the minimum number of repeaters necessary in a particular area for simultaneous users, our team set out to come up with a strategy by using models we designed. The first aspect that we took into major consideration was the construction of models. Browsing the reference books and mutual discussion with each other, original ideas are used to developed models. We have used mathematical modeling to analyze some of the factors associated with the problem. A ll of these variables can be changed that make the model has more applicability.
Other important findings through using data test made the solution apparent and standard. We next developed a detailed simulation engine to perform simulations. Our simulations allowed us to obtain lots of data. To ensure the validity of models and the reliability of results, large amounts of data have been tested. The methods we came up with are more accurate close to the right result.
Finally, the discussion of defects area that caused by mountainous makes a further thinkin g of our
models and the way of solution.
In conclusion, though there are still some weaknesses, the strengths of dynamic test of our models make contribution to the solution of the problem.
10.References
High Quality Papers of 2009 MCM/ICM.
Jiang, Qiyuan and Xie, Jinxing. 2003. Mathematical Model.(Chinese). Higher Education Press. Wikipedia. Available: https://www.doczj.com/doc/8911717755.html,/wiki/VHF.
Wu, Jianguo.2005. Mathematical Modeling Case.(Chinese). Water Conservancy and Hydropower of China Press.