Speeding up the solution of the Site and Power Assignment Problem in Wireless Networks Pasquale Avella1 Alice Calamita2 and Laura Palagi2

2025-05-03 0 0 579.54KB 19 页 10玖币

侵权投诉

Speeding up the solution of the Site and Power Assignment

Problem in Wireless Networks

Pasquale Avella1, Alice Calamita2⋆, and Laura Palagi2

1DING, Universit`a del Sannio, Piazza Roma 21, 82100, Benevento, Italy

avella@unisannio.it

2DIAG, Sapienza University of Rome, Via Ariosto 25, 00185, Rome, Italy

{alice.calamita,laura.palagi}@uniroma1.it

Abstract. This paper addresses the optimal design of wireless networks through the site and power

assignment problem. Given a set of candidate transmitters, this problem involves choosing optimal

transmitter locations and powers to provide service coverage over a target area. In the modern context

of increasing traﬃc, establishing suitable locations and power emissions for the transmitters in wireless

networks is a relevant and challenging task due to heavy radio spectrum congestion. Traditional net-

work design formulations are very ill-conditioned and suﬀer from numerical inaccuracies and limited

applicability to large-scale practical scenarios. Our contribution consists of speeding up the solution

of the problem under consideration by addressing its drawbacks from a modeling point of view. We

propose valid cutting planes and various presolve operations to reduce the problem size and strengthen

existing formulations, along with a reduction scheme based on reduced cost ﬁxing to reduce the sources

of numerical inaccuracies. Our proposals prove eﬀective, allowing us to achieve optimality on large-scale

instances obtained from a real 4G LTE network in solution times aligning well with planning windows.

Keywords: wireless network design ·base station deployment ·power assignment ·0-1 linear program-

ming ·reduced cost ﬁxing ·ﬁxing heuristic

1 Introduction

A wireless network is a telecommunications network that uses radio waves, or other wireless communication

technologies, to transmit and receive data without the need for physical cables, allowing for the wireless

connectivity of devices. From a design point of view, the basic elements of wireless networks are transmitters

and receivers. Hence, wireless network design (WND) consists of identifying the proper locations for the

transmitters and setting their operational parameters – like frequency and/or power emission – in such a way

as to cover with service the receivers located in the area of interest.

Even if wireless networks rely on diﬀerent technologies and standards based on the service they are meant

to provide, they all share a common feature: the need to reach users scattered over a vast area with a

radio signal that must be strong enough to prevail against other unwanted interfering signals. The quality of

⋆Corresponding author. This author has been partially supported by Fondazione Ugo Bordoni, Rome, Italy

arXiv:2210.04022v4 [cs.DM] 26 Nov 2023

2 P. Avella et al.

service (and hence the coverage) indeed depends on the interplay of numerous signals, wanted and unwanted,

generated from a large number of transmitting devices. The increasing traﬃc and the densiﬁcation of the

base stations along the territory have led to an increase in interfering signals. Consequently, establishing

suitable locations and power emissions for all the transmitters, coexisting within a heavily congested radio

spectrum, has become a challenging and relevant task. Indeed, in the current era of pervasive connectivity, the

design of wireless networks plays a pivotal role in shaping modern societal infrastructure. The importance of

studying wireless network design lies in its profound implications for enhancing communication and enabling

technological advancements, and its inﬂuence on the evolving dynamics of global connectivity in daily lives.

This paper addresses the design of wireless networks for 4G LTE technology and considers the frequency

as ﬁxed, thus tackling a WND problem known as the site and power assignment problem. This research was

carried out in collaboration with the Fondazione Ugo Bordoni (FUB) [15], a higher education and research

institution under the supervision of the Italian Ministry of Enterprises and Made in Italy (MISE) that

operates in the telecommunication ﬁeld, providing innovative services for government bodies.

Literature overview As wireless networks are becoming denser, due to technological advancements and in-

creased traﬃc [18], practitioners’ traditional design approach based on trial-and-error supported by simulation

has exhibited many limitations. The ineﬃciency of this approach led to the need for optimization approaches,

which resulted in been critical for lowering costs and meeting user-demanded service quality standards (see

e.g., [10,11]). Many optimization models for WND have been investigated over the years. However, the natural

formulation on which most models are based presents severe limitations since it involves numerical problems

in the problem-solving phase, which emerge even in small instances. Indeed, the constraint matrices of these

models contain coeﬃcients that range in a huge interval, as well as large big-Mleading to weak bounds. In

this paper we review the exact approaches proposed for WND problems, pointing out the contributions that

highlight these numerical issues. We recommend [5] for a complete literature review on WND (also including

heuristic approaches) and [19] for a thorough overview of the optimization challenges in modern WND.

The exact approaches proposed in the literature are mainly oriented towards non-compact formulations

and row generation methods. In [20], a mixed-integer linear programming (MILP) formulation is introduced,

and the proposed exact solution method combines combinatorial and classical Benders decomposition and

valid cuts. In [2,3,6, 12], mixed-integer formulations are used to solve randomly generated instances through

standard MIP solvers. In [10], a non-compact 0-1 formulation is investigated. The solution algorithm is based

on a row-generation method. The same authors of [10] present a 0-1 model for a WND variant linked to the

feasible server assignment problem in [14]. In [7], a non-compact formulation is proposed for the maximum

link activation problem; the formulation uses cover inequalities to replace the source of numerical instability.

In [13], the source of numerical issues in WND is deeply investigated, and the use of numerically safe LP

solvers is suggested to make the solutions reliable. In [5], a compact reformulation for the siting problem has

been proposed that allows for the exact solution of large instances. The papers explicitly addressing numerical

issues are [5, 7, 10, 13, 14].

Site and Power Assignment in Wireless Networks 3

Main motivation and contributions Traditional solution methods, employing (mixed-)integer linear programs

with (very) ill-conditioned coeﬃcient matrices, suﬀer from numerical inaccuracies and limited applicability to

large-scale practical scenarios. Indeed, the traditional modeling choice typically includes big-Mcoeﬃcients to

model coverage conditions, leading to very weak linear relaxations and solutions – returned by state-of-the-art

MIP solvers – typically far from the optimum [9]. Our contribution consists of speeding up the solution of

the problem under consideration, by addressing its drawbacks, from a modeling point of view. Speciﬁcally,

we discuss how to improve the natural formulation of the WND problem proposed in the literature by

1. introducing several presolve operations to reduce the number of problem variables and overall problem

size;

2. providing valid cliques and variable upper bounds to accelerate solution times;

3. proposing an aggressive reduction scheme based on a reduced cost ﬁxing procedure that strengthens the

formulation by reducing the big-Mvalues.

Although reduced cost ﬁxing is a well-known technique, its application to this problem has never been

investigated before (as far as we know) and shows signiﬁcant potential thanks to the positive impact on the

reduction of numerical problems. To improve this technique, we provide a heuristic, producing near-optimal

solutions very quickly. Our proposals to reduce memory and numerical issues will allow a rapid solution of

large WND instances in line with the times required in the planning phase.

The remainder of this paper is organized as follows. Section 2 presents the problem statement and its

mathematical formulation. In Section 3, our contribution to accelerating the problem solution is given. In

Section 4, computational results are discussed. Conclusions are provided in Section 5.

2 Problem Formulation

A wireless network consists of radio transmitters distributing service (i.e., wireless connection) to a target

area. The target area is usually partitioned into elementary areas, called testpoints, in line with the rec-

ommendations of the telecommunications regulatory bodies. Each testpoint is considered a representative

receiver of all the users in the elementary area. Testpoints receive signals from all the transmitters. The

power received is classiﬁed as serving power if it relates to the signal emitted by the transmitter serving the

testpoint; otherwise, it is classiﬁed as interfering power (see 4G LTE standard [22]). A testpoint is regarded

as served (or covered) by a base station if the ratio of the serving power to the sum of the interfering powers

and noise power (Signal-to-Interference-plus-Noise Ratio or SINR) is above a threshold [21], whose value

depends on the desired quality of service.

We assume the frequency channel is given and equal for all the transmitters. Having a ﬁxed frequency is

a straightforward assumption: for diﬀerent frequency channels the problem decomposes as there is no inter-

ference among non-co-channel signals. We also assume that the power emissions of the activated transmitters

can be represented by a ﬁnite set of power values, which ﬁts with the standard network planning practice

of considering a small number of discrete power values. This practice of power discretization for modeling

purposes has been introduced in [10].

4 P. Avella et al.

Let Bbe the ﬁnite set of potential transmitters and Tbe the ﬁnite set of receivers located at the testpoints.

Let P={P1, . . . , P|P|}be the ﬁnite set of feasible power values assumed by the activated transmitters, with

P1>0 and P|P| =Pmax. Hence L={1,...,|P|} is the ﬁnite set of power value indices (or simply power

levels). We introduce the variables

zbl =(1 if transmitter bis emitting at power Pl

0 otherwise b∈ B, l ∈ L

and

xtb =(1 if testpoint tis served by transmitter b

0 otherwise. b∈ B, t ∈ T

To enforce the choice of only one (strictly positive) power level for each activated transmitter we use

l∈L

zbl ≤1b∈ B.(1)

The mathematical formulation of the WND problem contains the so-called SINR inequalities used to

assess service coverage conditions. We recall that a testpoint t∈ T is regarded as covered by a base station

β∈ B if the SINRtβ is above a threshold. The SINRtβ is given by the ratio of the serving power coming from

βand the sum of the interfering powers and noise power measured in t. The serving power is given by the

product of the power emitted by the serving base station βand the fading coeﬃcient, modeling the reduction

of power in the signal from βto t. The interfering power is given by the sum of all interfering contributions

measured at the testpoint t. These interfering contributions are modeled as the serving power, with the

unique diﬀerence that the signal is emitted by all the activated base stations, except for the serving one (i.e.,

except for β). To formulate the SINR inequalities, we refer to the discrete big-Mformulation reported in [10],

which considers a discretization of the power range. Let ˜atb >0 be the fading coeﬃcient applied to the signal

received in t∈ T and emitted by b∈ B. Let µ > 0 be the system noise. Then a receiver tis served by a base

station β∈ B if the SINRtβ is above a given SINR threshold δ > 0, namely

˜atβ X

l∈L

Plzβl

µ+X

b∈B\{β}

˜atb X

l∈L

Plzbl

≥δ t ∈ T , β ∈ B :xtβ = 1 (2)

where the numerator represents the serving signal in t(coming from β), and the denominator is the sum of

the noise and the interfering signals in t(coming from all b̸=β). Following [10], we can rewrite the SINR

condition (2) through the big-Mconstraints

˜atβ X

l∈L

Plzβl −δX

b∈B\{β}

˜atb X

l∈L

Plzbl ≥δµ −Mtβ (1 −xtβ )t∈ T , β ∈ B (3)

where Mtβ is a large (strictly) positive constant. When xtβ = 1, (3) reduces to (2); when xtβ = 0 and Mtβ

is suﬃciently large, (3) becomes redundant. We can set, e.g.,

Mtβ =δµ +δPmax X

b∈B\{β}

˜atb.(4)

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

SpeedingupthesolutionoftheSiteandPowerAssignmentProbleminWirelessNetworksPasqualeAvella1,AliceCalamita2⋆,andLauraPalagi21DING,Universit`adelSannio,PiazzaRoma21,82100,Benevento,Italyavella@unisannio.it2DIAG,SapienzaUniversityofRome,ViaAriosto25,00185,Rome,Italy{alice.calamita,laura.palagi}@uniroma1.i...

展开>> 收起<<

Speeding up the solution of the Site and Power Assignment Problem in Wireless Networks Pasquale Avella1 Alice Calamita2 and Laura Palagi2.pdf

共19页,预览4页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Speeding up the solution of the Site and Power Assignment Problem in Wireless Networks Pasquale Avella1 Alice Calamita2 and Laura Palagi2

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: