{'fraction_non_alphanumeric': 0.042977487982485366, 'fraction_numerical': 0.012898005806482319, 'mean_word_length': 4.046109510086455, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Maximizing Mobile Coverage via Optimal Deployment of Base Station and Relays

Deploying relays and/or mobile base stations is a major means of extending the coverage of a wireless network. This paper presents models, analytical results, and algorithms to answer two related questions: The first is where to deploy relays in order to extend the reach from a base station to the maximum; the second is where to deploy a mobile base station and how many relays are needed to reach any point in a given area. Simple time-division and frequency-division scheduling schemes as well as an end-to-end data rate requirement are assumed. An important use case of the results is in the Public Safety Broadband Network, in which deploying relays and mobile base stations is often crucial to provide coverage to an incident scene.

Section IV studies the deployment of relays. Specifically, the relays are deployed between the base station and the destination. We analytically determine the optimal positions of the relays, so that the reach to the destination is maximized subject to the end-to-end data rate requirement.
When the number of relays is small, the maximum reach increases with the number of relays.
But beyond a certain number, deploying more relays does not provide further improvement (in fact, it decreases the maximum reach if the same QoS needs to be maintained).
Section V studies the deployment of a mobile base station. Specifically, the mobile base station is deployed to cover an arbitrary polygon, which may or may not be convex. Both the general case where the base station can be located anywhere and the situation where the base station is constrained to be outside or on the boundary of the polygon are considered. We propose efficient algorithms to compute the optimal position of the mobile base station, so that the minimum signal-to-noise ratio (SNR) of any point over the entire region is maximized. If the polygon can not be covered by the mobile base station alone, relays are deployed to extend the coverage. The goal here is limited to reaching any point in the region, rather than covering the entire region at the same time.
Section VI shows numerical results. Concluding remarks are given in Section VII.

A. Network Model with Relays
The network model with relays is shown in Fig. 1, where K − 1 relays are deployed between the base station and the destination. At each relay, signals from both directions are fully decoded and re-transmitted, so that the base station, relays and the destination form a two-way multi-hop decode-and-forward (DF) D2D network.
Without loss of generality, we let relays be located along the line segment that connects the base station and the destination. The K + 1 devices are connected by K segments and the length of the k-th segment is d k in meters for k ∈ {1, . . . , K}. The transmit power of the k-th forward and backward links are p k and q k . The total bandwidth is W . The end-to-end data rate requirement of the forward and backward links are B and C, respectively. We study where the relays should be deployed, so that the reach to the destination is maximized subject to the end-to-end data rate requirement.

B. Network Model with a Mobile Base Station
The network model with a mobile base station is shown in Fig. 2, where the mobile base station is deployed to cover an arbitrary polygon, which may or may not be convex. We first consider the case where the mobile base station can be deployed anywhere. We then consider the case where the base station is constrained to be outside or on the boundary of the polygon, which could be the situation at an incident scene.
In the case that only the mobile base station is deployed, we study where it should be deployed, so that the minimum SNR of any point in the entire region is maximized. Due to the end-toend data rate requirement, part of the polygon may be beyond the coverage of the mobile base station. In that case, relays are deployed to extend the coverage, where the optimal positions of the mobile base station and the relays need to be determined.

III. CHANNEL MODEL
In the DF network, an outage event is declared whenever the SNR of any link falls below a prescribed threshold. In other words, the end-to-end data rate is dominated by the weakest link.

A. Fading Model
We use Rayleigh fading model for links between nearby devices [31]. Let the channel power gain of the k-th segment be: where A is a constant value that considers shadowing and antenna gain, α is the path loss exponent, φ denotes the power gain of the Rayleigh fading channel, which follows the exponential distribution with unit mean, d k is the distance introduced in Section II-A.

B. End-to-End Data Rate
We consider uniform time-division and frequency-division scheduling schemes for allocating the resources, which are simple and guarantee robustness much needed in the Public Safety Broadband Network. Understanding of these simple schemes is also the first step toward more sophisticated solutions involving spectrum sharing.
Under uniform time division, each link uses a 1 2K fraction of the time and the total bandwidth. The SNR of the k-th forward and backward links defined as γ k and τ k are: where σ 2 is the power spectral density of the white Gaussian noise, p k and q k are the transmit power and W is the bandwidth introduced in Section II-A.
The end-to-end outage probability of the forward and backward links are [28]: where γ and τ are the prescribed SNR threshold of the forward and backward links. 6 The end-to-end data rate of the forward and backward links under time division defined as B t and C t are: Under uniform frequency division, each link uses a 1 2K fraction of the bandwidth and the total time. Similarly, the end-to-end data rate of the forward and backward links under frequency division defined as B f and C f are: whose exponential parts are 1 2K of those in (4). Under power constraint, the end-to-end data rate achieved according to (5) under frequency division are higher than those achieved according to (4) under time division. Under energy constraint, the end-to-end data rate achieved according to (5) under frequency division are identical to those achieved according to (4) under time division with p k and q k replaced by 2Kp k and 2Kq k , respectively.
In the amplify-and-forward (AF) network, each relay amplifies and forwards the signals from both directions. Under the same resources allocation schemes, each link sees no interference.
But the noise in previous links is amplified, so that the SNR in AF network decreases with the number of links. Then the end-to-end SNR is smaller than that of the weakest link in AF network, which is also smaller than that of the weakest link in DF network. Hence DF outperforms AF as far as maximizing the reach is concerned.

IV. THE DEPLOYMENT OF RELAYS
In the case of the deployment of relays, K −1 relays are deployed between the base station and the destination. The optimal distance tuple (d 1 , . . . , d K ) maximizes the reach to the destination subject to the end-to-end data rate requirement. Once the optimal distance tuple is computed, the optimal positions of the relays are straightforward.

A. The General Cases
Under time division, the end-to-end data rate expressed as (4) should be no less than the data rate requirement B, C introduced in Section II-A. The optimization problem to find the optimal distance tuple (d 1 , . . . , d K ) is: which can be rewritten as: 8 The optimization problem (7) is convex and the associated Lagrangian is [32]: where λ and ν are the Lagrangian multipliers.
Let d * 1 , . . . , d * K , λ * and ν * be the optimal solutions. The Karush-Kuhn-Tucker (KKT) conditions are: The solutions of (10g) are: We find all feasible distance tuples (d 1 , . . . , d K ) satisfying the KKT conditions (10) and the one with the maximum sum distance is the optimal distance tuple. The solutions of the KKT conditions (10) have three possible cases.
The first case is that λ * = 0 and ν * > 0. Using (10f) and (11), ν * satisfies The left side of (12) decreases with ν * , so that it is easy to obtain the unique solution of (12).
Then the distance tuple is computed by (11). If the distance tuple satisfies (10c), it is a feasible solution of the KKT conditions.
The second case is that λ * > 0 and ν * = 0. Using (10e) and (11), λ * satisfies Similarly, it is easy to obtain the unique solution of (13). Then the distance tuple is computed by (11). If the distance tuple satisfies (10d), it is a feasible solution of the KKT conditions.
The numerical method for computing the optimal distance tuple for maximizing the reach to the destination is summarized as Algorithm 1. If either λ * = 0 or ν * = 0, the solution of (12) or (13) is unique, so that there is no more than one feasible distance tuple. If λ * > 0 and ν * > 0, the solution of (14) with non-identical parameters is typically unique or null, so is the number of the feasible distance tuple. Then the complexity of Algorithm 1 is the comparison of no more than 3 feasible distance tuples.
Under frequency division, the end-to-end data rate expressed as (5) should be no less than the data rate requirement. The optimization problem to find the optimal distance tuple (d 1 , . . . , d K ) is: which is convex and similar to (7). Then following the same way as Algorithm 1, the optimal distance tuple for maximizing the reach to the destination is computed.

B. The Cases with Identical Parameters
In the following, we study the cases with identical parameters, which shed more light on the intuition about how to optimally deploy relays for maximizing the reach to the destination. The identical parameters are p k = q k = p, γ = τ and B = C for k ∈ {1, . . . , K}.
whose feasible solution is unique with λ * > 0. The optimal distance of each link and the maximum reach to the destination are: Under frequency division, the optimization problem (15) uses 2Kb instead of b in the optimization problem (7). Then using 2Kb instead of b in (17a) and (17b), the optimal distance of each link and the maximum reach to the destination are: . Under time division, the optimal distance of each link decreases with K, and the maximum reach to the destination increases with K for K ≤ ⌊β exp 1 1−α ⌋, but decreases for K ≥ ⌈β exp 1 1−α ⌉. Under frequency division, the optimal distance of each link decreases with K, and the maximum reach to the destination increases Proof: Under time division, substituting (8) into (17), the optimal distance of each link is: which decreases with K. The maximum reach to the destination is: which increases with K for K ≤ ⌊β exp 1 1−α ⌋, but decreases for K ≥ ⌈β exp 1 1−α ⌉. Under frequency division, substituting (8) into (18), the optimal distance of each link is: which decreases with K. The maximum reach to the destination is: Therefore, when the number of relays is small, more relays increase the maximum reach to the destination. Beyond a certain number, deploying more relays not only does not provide further improvement, but decreases the maximum reach.

C. Discussions
In the following, we discuss the upper bound of the number of relays and the traffic types for general cases.

1) The Number of Relays:
The fraction of the resources allocated to each link decreases with the number of relays, which may decrease the end-to-end data rate. In order to satisfy the end-to-end data rate requirement, the number of relays should be bounded.
2C and the number of relays is upper bounded by: Proof: For the optimization problem (7) and (15), the parameters defined as b and c should be positive, Hence (23) must hold.
Therefore, each additional relay adds to the maximum reach to the destination in general. But there must exist a certain number, beyond which deploying more relays is not necessary and does not provide further improvement in the maximum reach.
which is a convex problem and (x, y) is the optimal position of the mobile base station. The optimal position of the mobile base station also maximizes the N-of-N system lifetime for homogeneous destinations 2 in [23]. Instead of using KKT conditions, we study the structure of the optimal position of the mobile base station to develop a more efficient numerical method.
In order to satisfy the constraint (25b), (x, y) locates in a disk whose center is the vertex  Fig. 3. The coverage of the mobile base station is a disk, which could be determined by a diameter in Fig. 3(a) or three points on the boundary in Fig. 3(b). The optimal position of the mobile base station is marked by a star. We define C i as the circle whose center is the vertex (x i , y i ) and radius is r.
In Fig. 3(a), the optimal position of the mobile base station (x, y) is the sole intersection point of two circles C i and C j . The line segment connecting the vertices (x i , y i ) and (x j , y j ) is a diameter of the coverage of the mobile base station. For two indexes i, j ∈ {1, . . . , M}, the coordinate of the mobile base station is: In Fig. 3(b), the optimal position of the mobile base station is the sole intersection point of three circles C i , C j and C k , which is also the center of the circumcircle of the triangle whose vertices are (x i , y i ), (x j , y j ) and (x k , y k ). For three different indexes i, j, k ∈ {1, . . . , M}, the coordinate of the mobile base station is: We find all candidate positions described by (26) and (27), and compute the maximum distance to all vertices for each candidate position as: The candidate position with the minimum maximum distance to all vertices is the optimal position of the mobile base station.

Algorithm 2
Computing the optimal position of the mobile base station without place restrictions 1: Input: (x i , y i ) for i ∈ {1, . . . , M}. 2: Output: (x, y). 3: Find the candidate positions using (26), (27). 4: Compute the maximum distance to all vertices for each candidate position using (28). 5: Return (x, y) which is the coordinate of the candidate position with the minimum maximum distance to all vertices.
The numerical method computes the optimal position of the mobile base station without place constrictions as Algorithm 2. The complexity is the comparison of no more than 1 6 M 3 − 1 6 M candidate positions satisfying (26) or (27) where M ≥ 3.

B. With Place Restrictions
When the mobile base station shall be deployed outside or on the boundary of the polygon, the optimization problem is changed to:  Fig. 4. The intersection area is the shadowed part and the optimal position of the mobile base station is marked by a star. In Fig. 4(a) and Fig. 4(b), the optimal position of the mobile base station is outside the polygon. In Fig. 4(c) and Fig. 4(d), the optimal position of the mobile base station is on the boundary of the polygon. We define E i as the edge of the polygon connecting two adjacent vertices (x i , y i ) and (x i+1 , y i+1 ) for i ∈ {1, . . . , M} where (x M +1 , y M +1 ) = (x 1 , y 1 ).
In Fig. 4(a), the optimal position of the mobile base station (x, y) is the sole intersection point of two circles C i and C j , and outside the polygon. For two non-adjacent indexes i, j ∈ {1, . . . , M}, the coordinate of the mobile base station is described by (26).
In Fig. 4(b), the optimal position of the mobile base station (x, y) is the sole intersection point of three circles C i , C j and C k , and outside the polygon. For three different indexes i, j, k ∈ {1, . . . , M}, the coordinate of the mobile base station is described by (27).
In Fig. 4(c), the optimal position of the mobile base station (x, y) is the intersection point of one circle C j and one edge E i . The line segment connecting (x j , y j ) and (x, y) is orthogonal to y) is on E i . For three different indexes i, i + 1, j ∈ {1, . . . , M}, the coordinate of the mobile base station is: In Fig. 4(d), the optimal position of the mobile base station (x, y) is the intersection point of two circles C j and C k and one edge E i . The distance from (x, y) to (x j , y j ) and (x k , y k ) are the same and (x, y) is on E i . For four indexes i, i + 1, j, k ∈ {1, . . . , M} where j = k, the coordinate of the mobile base station is: The candidate position with the minimum maximum distance to all vertices is the optimal position of the mobile base station.

Algorithm 3
Computing the optimal position of the mobile base station with place restrictions 1: Input: (x i , y i ) for i ∈ {1, . . . , M}. 2: Output: (x, y). 3: Find the candidate positions using (26), (27) and delete the ones inside the polygon. 4: Find the candidate positions using (30), (31) and delete the ones outside the polygon. 5: Compute the maximum distance to all vertices for each candidate position using (28). 6: Return (x, y) which is the coordinate of the candidate position with the minimum maximum distance to all vertices.
The numerical method computes the optimal position of the mobile base station outside or

C. Relay-Assisted Coverage
The optimal position of the mobile base station maximizes the minimum SNR of any point over the entire region. But due to the end-to-end data rate requirement, part of the polygon may be beyond the coverage of the mobile base station. When the destination locates at the area beyond the coverage of the mobile base station, the minimum number of relays are deployed along the line segment connecting the mobile base station and the destination.
Using Algorithm 1, we first compute the optimal positions of the relays for maximizing the reach to the destination as the number of relays increases. Once the maximum reach is larger than or equal to the distance between the mobile base station and the destination, the number of relays is the minimum one and the relays are deployed at the optimal positions.
We caution that, with relays, the goal here is limited to reaching any point in the region, rather than covering the entire region at the same time.

D. Discussions
For the nonconvex polygon, the optimal position of the mobile base station could be inside, outside or on the boundary of the polygon. But the convex polygon satisfies Proposition 5.

A. The Deployment of Relays
In the case of the deployment of relays, the optimal distance tuple is computed which maximizes the reach to the destination subject to the end-to-end data rate requirement.
The optimal distance tuple as the transmit power increases with one relay under time division and frequency division are shown in Fig. 6. With fixed transmit power, d 1 is larger than d 2 since the transmit power of the base station is larger than that of the destination. As discussed in Section III-B, when the transmit power of each device is the constraint, the end-to-end data rate under time division is smaller than that under frequency division. Then d 1 + d 2 under time division is smaller than that under frequency division. With the optimal distance tuple, the optimal positions of the relays are straightforward. For example, when P = 20 dBm, the maximum reach to the destination is 341 meters under time division and 493 meters under frequency division.
The optimal position of the relay is 192 meters from the base station under time division and 277 meters from the base station under frequency division.
As Proposition 3 shows, substituting the simulation parameters into (23), the number of relays K − 1 can not exceed 9. The optimal distance tuple as the number of relays increases under time division and frequency division when P = 20 dBm are shown in Fig. 7 and Fig. 8. When  frequency division.

B. The Deployment of the Mobile Base Station
In the case of the deployment of the mobile base station, the polygon is a quadrilateral whose four vertices are (0, 350), (300, 650), (500, 600), and (600, 300) in meters. The optimal position of the mobile base station is computed, which maximizes the minimum SNR of any point over the entire region.
When the mobile base station could be deployed anywhere, the optimal position of the mobile base station is (368, 304) in meters as marked by a star in Fig. 9. The distance from the mobile base station to the vertices of the polygon are 304, 282, 304 and 304 meters. As shown in

VII. CONCLUSION
In this paper, we study the optimal positions of multiple relays and a mobile base station for maximizing the reach of a wireless network under time division and frequency division.
When the number of relays is small, the maximum reach increases with the number of relays.
Beyond a certain number, deploying more relays does not provide further improvement due to the end-to-end data rate requirement. The optimal position of the mobile base station maximizes the minimum SNR of any point in a polygon. Due to the end-to-end data rate requirement, relays may be deployed to reach any point in the polygon. Maximizing the reach of the wireless network using spectrum sharing scheme and providing full coverage to a given area are left for future work, where interference and scheduling are crucial to the wireless coverage.