Taiwo Oyedare
email: toyedare@tnstate.edu

Al Ashraf

Sachin Sharah

Shetty
email: sshetty@tnstate.edu

A Reputation-Based Coalition Game to Prevent Smart Insider Jamming Attacks in MANETs

Keywords: Coalition, Reputation, Insider Jamming, Transmission Rate

Mobile Adhoc Networks (MANET) are susceptible to jamming attacks which can inhibit data transmissions. There has been considerable work done in the detection of external jamming attacks. However, detection of insider jamming attack in MANET has not received enough attention. The presence of an insider node that has constantly monitored the network and is privy to the network secrets can acquire sufficient information to cause irreparable damage. In this paper we propose a framework for a novel reputation-based coalition game between multiple players in a MANET to prevent internal attacks caused by an erstwhile legitimate node. A grand coalition is formed which will make a strategic security defense decision by depending on the stored transmission rate and reputation for each individual node in the coalition. Our results show that the simulation of the reputation-based coalition game would help improve the network's defense strategy while also reducing false positives that results from the incorrect classification of unfortunate legitimate nodes as insider jammers.

Introduction

Mobile Ad-hoc Network (MANET) is a group of self-organized, infrastructureless mobile nodes that relies on interdependence and cooperation of all nodes to carry out critical network functions. MANETs are vulnerable to jamming attacks due to the shared nature of the wireless medium. There are two main categories of jamming attacks: external jamming and insider jamming 1 . External jamming attacks are launched by foreign devices that are not privy to network secrets such as the network's cryptographic credentials and the transmission capabilities of individual nodes the network [START_REF] Mpitziopoulos | A Survey on Jamming Attacks and Countermeasures in WSNs[END_REF]. These types of attacks are relatively easier to counter through some cryptography based techniques, some spread spectrum methodology 2 , Antenna Polarization and directional transmission methods [START_REF] Stutzman | Antenna Theory and Design[END_REF].

Smart insider jamming attacks on the other hand are much more sophisticated in nature because they are launched from a compromised node. 3 The attacker exploits the knowledge of network secrets to deceptively target critical network functions. In order to effectively prevent the smart insider jamming attack, we adopt a reputation mechanism to detect the presence of smart jammer nodes when they are passively eavesdropping and collecting information about the network prior to launching the jamming attack. A lower reputation threshold is set such that the jammer would not be able to successfully jam the network without being detected by its neighbors. In this paper, we propose a reputationbased coalition game to prevent an attack that could be posed by an erstwhile legitimate node. Game theoretic based approaches for mitigating attack can be seen in the works of [START_REF] Han | Coalition Games with Cooperative Transmission: A Cure for the Curse of Boundary Nodes in Selfish Packet-Forwarding Wireless Networks[END_REF] where a coalition game with cooperative transmission was implemented as a cure for the curse of boundary nodes in selfish packetforwarding. Alibi-based protocol [START_REF] Nguyen | ALIBI: A Novel Approach for Detecting Insider-based Jamming Attacks in Wireless Networks[END_REF] and self-healing protocol [START_REF] Li | Self-Healing Wireless Networks Under Insider Jamming Attacks[END_REF] have been used to either detect or recover from a jamming attack. Our reputation-based coalition game differs from the aforementioned approaches by (1) Designing a coalition formation algorithm, (2) Maintaining the coalition via a reputation mechanism, (3) Identifying the insider jammer based on reputation score , and (4) Excluding the attacker from the coalition by rerouting transmission path and randomly modifying communication channel. The game is fully distributed and does not rely on any trusted central entity to operate at optimal performance. The remainder of this paper is organized as follows. Section II we present relevant works that are closely related to our model; in Section III we present the network and jammer model; Section IV contains the proposed defense model and in Section V we show our simulation results and finally in Section VI we conclude the work and highlight prospective future work.

Related Work

Researchers have devoted great efforts on security in MANET. In [START_REF] Marti | Mitigating Routing Misbehavior in Mobile ad hoc Networks[END_REF] and [START_REF] Michiardi | Core: A collaborative reputation mechanism to enforce node cooperation in mobile ad hoc networks[END_REF], the authors used watchdog/pathrater and collaborative reputation (CORE) mechanisms respectively to prevent to mitigate node misbehavior in MANETs. Other works have used non-cooperative games to model security scenarios as well as the corresponding defense strategies to such attacks [START_REF] Michiardi | A Game Theoretical Approach to Evaluate Cooperation Enforcement Mechanisms in Mobile Ad hoc Networks[END_REF]. Most of these works focused on two player games where all legitimate nodes are modelled as a single node and attacker nodes are also modeled as a single node as well; this is only valid for centralized networks, whereas MANETs are self-organized networks.

Some researchers have also used coalition game to ensure security in MANETs. Li et al [START_REF] Li | Self-Healing Wireless Networks Under Insider Jamming Attacks[END_REF] designed a self-healing wireless networks under insider jamming attacks. The concept of a pairwise key mentioned in their design shows that the design works best in a centralized system and not a self-organized system like MANETs. Some other works have only focused on node selfishness and not on intentional malicious acts or jamming attacks. Zhu et al [START_REF] Han | Coalition Games with Cooperative Transmission: A Cure for the Curse of Boundary Nodes in Selfish Packet-Forwarding Wireless Networks[END_REF] used coalition game in which boundary nodes used cooperative transmission to help backbone nodes in the middle of the network and in return the backbone nodes would be willing to forward the boundary nodes' packets.

Our approach is unique in that (1) we refrain from treating the nodes in a collective manner, instead we consider them as individual node by defining a security characteristic function for the coalition formation (2) we use reputation mechanism to prevent false positives (3) we kept a history of the nodes' transmission rates (4) we successfully identify the insider jammer and excluded it from the coalition.

3 Network and Jammer Model

Network Model

Our network model involves a characteristic function and a coalition formation model. This model is similar to related efforts [START_REF] Peleteiro | Fostering Cooperation through Dynamic Coalition Formation and Partner Switching[END_REF] [11] [START_REF] Li | Achieving Secure and Cooperative Wireless Networks with Trust Modeling and Game Theory[END_REF] [13], [START_REF] Li | Achieving Secure and Cooperative Wireless Networks with Trust Modeling and Game Theory[END_REF]. It departs from the related efforts in the usage of accumulative feedback adaptation transmission rate (AFAT) [START_REF] Al-Sharah | Accumulative Feedback Adaptation Transmission Rate in Mobile Ad-hoc Networks[END_REF] in the coalition formation; use of maximum transmission rate in security characteristic function; and the necessary conditions needed for the grand coalition formation.

Coation Formation Model According to [START_REF] Ferguson | Game Theory[END_REF], a coalition game is an ordered pair N, v where N = (1, .., n) is the set of players4 and v is the characteristic function. 5 By convention, v(φ) = 0, where φ denotes the empty set [START_REF] Ferguson | Game Theory[END_REF].

The coalition formation process starts with nodes forming small disjoint coalition with neighboring nodes in their range of transmission and then gradually grows until the grand coalition is formed with the testimony of intersecting nodes. Such an intersecting node will serve as the referee for a new node that seeks to join the coalition. Our coalition formation process depends on the transmission rate table that has been stored according to the previous work done by [START_REF] Al-Sharah | Accumulative Feedback Adaptation Transmission Rate in Mobile Ad-hoc Networks[END_REF].

In [START_REF] Al-Sharah | Accumulative Feedback Adaptation Transmission Rate in Mobile Ad-hoc Networks[END_REF], we proposed an accumulative feedback adaptation transmission rate (AFAT). AFAT is a decentralized approach to ensure the communication of transmission rates between neighboring nodes in a network. The knowledge of neighbor's transmission rates helps a node to adjust its own rate accordingly. In other words, AFAT provides the maximum transmission rates for the nodes in order to meet the specific application bandwidth requirements. According to AFAT, the transmission rates of the nodes is adjusted based on the history of neighbors' transmission rates. A list of the transmission rates has been built into the transmission rate table and is updated during every time instant.

The final outcome of the coalition formation process is to form a stable grand coalition which comprises of all nodes in the network. The intersecting nodes would be very key to the formation of the grand coalition because they belong to the smaller coalitions that would be merged into a single coalition.

There are N nodes in the network, for any coalition, C 2 N 6 As mentioned previously, many literature [START_REF] Ferguson | Game Theory[END_REF] [START_REF] Li | Achieving Secure and Cooperative Wireless Networks with Trust Modeling and Game Theory[END_REF] have made use of the characteristic function in modeling a coalition game. This function helps to calculate the payoff of individual nodes such that they can see their joining the coalition as a rational decision since rationality is a key assumption in game theory. 7A node has neighbors in its transmission range that can testify about its cooperation based on the transmission rate table updated at every time-slot. This testimony means that these neighboring node can give a firsthand information about the node when queried. Let |G i | be the set of neighboring nodes in the transmission range of node i, therefore, at time slot t, the support rate for a node i in a coalition C, is:

S t (C) = |G i | -1 (1)
The transmission rate, T t (C), of coalition C at time, t, is another important parameter in the characteristic function, Li et al [START_REF] Li | Achieving Secure and Cooperative Wireless Networks with Trust Modeling and Game Theory[END_REF] on the other hand made use of the overlapping distance. The nodes' sharing of their transmission rate is very key to their admittance into the small coalition. In other to form a coalition with any node, there is a need to know the maximum available transmission rate. The maximum transmission rate ensures that the nodes match with the best nodes in terms of transmission rate before settling for the next best option as seen in the coalition formation algorithm. The maximum transmission rate in a coalition C is given by:

D t (C) = max{T t (C)} (2)
According to [START_REF] Li | Achieving Secure and Cooperative Wireless Networks with Trust Modeling and Game Theory[END_REF] the maximal admitting probability is given by:

A t (C) = max j C { i C P ij |C| |C = {i|i C, i = j, P ij = 0}} (3)
Incorporating these three parameters we can write the characteristic function by weighing each parameter. The characteristic function proposed is then;

v t (C) = 0, if |C|= 1 αS t (C) + βA t (C) + γD t (C), if |C| ≥ 1 (4)
These weight parameters α, β and γ can be used to provide variability for the characteristic function of the nodes. Due to the mobility factor in our model, it is important to keep track of the neighbors of any node at a given time, α helps to weigh the support rate parameter which is responsible for the number of neighbors of a node. Our assumption is that the nodes are slow-moving and there cannot be a rapid change of neighbors. β provides a weight value for the maximal admitting probability. The value assigned to β depends on the size of the coalition, if the coalition size is very big (say about 100 nodes), then it could be important to make it bigger than the other parameters. The transmission rate is affected by two major factors: propagation environment and the degree of congestion. Depending on these two factors, we could assign a weight value for the maximum transmission rate using γ. The weights would have an impact on the coalition as a whole. It is important for these weights to add up to 1 in order to allow prioritization based on the topology of the network. Because of the nature of our network, we will give the highest weight to the maximum transmission rate parameter. α + β + γ = 1 (5) New nodes are accepted into the grand coalition based on the testimony from intersecting nodes in the smaller coalition. Nodes take some time to gain a good reputation within the small coalition before it can be accepted into the grand coalition. There is a possibility that a new node might fail to enter into the grand coalition if it is out of range from the intersecting node when the smaller coalition is merged into a grand coalition. This merging process continues while there are intersecting nodes to testify about the new nodes which ensures that the grand coalition will continue to grow, thereby providing more robust security. Algorithm 1 shows the coalition formation process. The coalition formation is a dynamic process and no matter the location of a node in the network, it still has neighbors that can testify about it. From the coalition formation algorithm we can see that at each round of formation, every coalition looks to find a partner. The grand coalition is eventually formed only when two conditions are met: presence of an intersecting node to aid the merging and if v(N ) is atleast greater than the individual payoff of any disjoint smaller coalition.

There are no fixed number of neighbors for a particular node because of the mobile nature of the wireless environment. From our proposed model the size of the grand coalition could be any size of three nodes and above. For rationality sake it is important to show the individual payoff of the nodes so that they would have a basis for joining a coalition. The individual payoff share is also found in [START_REF] Saad | A Distributed Coalition Formation Framework for Fair User Cooperation in Wireless Networks[END_REF]. For any node i C, | C |> 1, the individual payoff8 share is defined in eqn 6

Algorithm 1 Algorithm for Coalition Formation Broadcast the forming option to the neighbors again 17: end if 18: if there is an intersecting node-nodes that belongs to more than one small coalition then 19:

Merge the small coalitions 20: else 21:

Re-broadcast forming option again to the network 22: end if 23: if v(N ) ≥ payoff from any disjoint set of smaller coalition then 24:

Form a grand coalition 25: else 26:

Repeat step 11 27: end if

x t (i) = 1 |C| (αS t (C) + βA t (C) + γD t (C)) (6)
Based on the characteristic function used, we will be making use of the core. The core states that the sum of total payoff of all members of the coalition must be greater than the value of that single payoff of any individual node [START_REF] Saad | A Distributed Coalition Formation Framework for Fair User Cooperation in Wireless Networks[END_REF] [START_REF] Ferguson | Game Theory[END_REF]. Hence looking at equations 4 and 6, we should be able to conclude that:

i C x t (i) ≥ v t (C) (7)
The game only has a core if it satisfies the concept of core of the coalition game [START_REF] Ferguson | Game Theory[END_REF].

Network Assumptions We assume N mobile nodes with A attackers, where A is less than N/2.9 Below are the assumptions under which we present our work:

-All players (or nodes) are rational (i.e. they would always choose the strategy that benefits them the most). -The network model does not adopt a hierarchical organization, such as, leader-follower or centralized organization. -The goal of the game is to form a stable grand coalition where any node that is unable to join this grand coalition would be designated as a malicious node. -The nodes are moving slowly because fast movement brings about a frequent change in the node's neighbors which may affect the reputation of the nodes adversely.

-A node's continuous membership in the grand coalition is dependent on its reputation value.

Jammer Model

The jammer type modeled in this section is a smart insider jammer who only launches its attack after collecting enough information to cause huge network disruptions. The jammer's goal is to launch a successful attack rather than building a very high reputation, however, it has to wait until it crosses the lower reputation threshold value, q L before attempting to jam the network. The potential jammer is first a member of a smaller coalition where it earns a good reputation from its neighboring nodes. The attack is a combination of both subtle and palpable attacks as explained in [START_REF] Liao | Classification on Attacks in Wireless Ad hoc Networks: A Game Theoretic View[END_REF]. The attacker passively scans the network as an eavesdropper while also sharing its transmission rate with all the neighbors in its range of transmission in the coalition. After a certain time, at which the attacker has gathered enough information about its neighbors and what channel they are transmitting on, the attacker stops sharing its own transmission rate because it needs enough power to jam the channel on which the best transmission rate is used.

The jammer would launch its attack when it knows that such an attack is feasible. By feasible, we mean that the jammer has the required jamming power, the chance of being detected is low and it has specific information about the channel on which the best transmission rate is used. The jammer would launch its palpable attack by intentionally sending a high-powered interference signal to that channel, thereby attempting to disrupt communication. The principal aim of jamming a selected channel is to disable the functionality of that channel. The complexity of the jamming can be seen in the fact the movement of the jammers may hinder the detection capability of the coalition. In figure 1, the jammers are part of two smaller coalitions which merged to become a grand coalition. The node marked yellow is the intersecting node for smaller coalitions.

Proposed Defense Model

Maintaining the Coalition through Reputation

We present a maintenance algorithm that employs the node reputation to track all the history of each node's cooperation as they broadcast their transmission Fig. 1: A Coalition of ten [START_REF] Peleteiro | Fostering Cooperation through Dynamic Coalition Formation and Partner Switching[END_REF] nodes with two (2) jammers rate. Reputation is simply defined as the goodness of a node as observed by other neighbors in its transmission range or the coalition in general. 10 Specifically, we adapt the mechanism used for modeling increase and decrease of reputation values. The reputation of a node is maintained by nodes in the same transmission range as itself. Each node updates the reputation table every time slot. 11 When a node broadcasts it's transmission rate, it receives an increment and if it fails the opposite happens. A new node that joins the network can be assigned a neutral reputation q N . All reputations would be valid for a time period, T v . There is an upper threshold, q U and a lower threshold q L , where q L < q N < q U . Reputation can be increased at the rate of σ and decreased at the rate of λ, where σ, λ < 1 and are both real numbers. For this algorithm, the two parameters are set equal to each other in order to ensure fairness. If these parameters are not made equal, for example when σ is larger than λ, there is the tendency for a node to quickly attain the maximum reputation value in a very short time and then lack the enthusiasm to continue sharing its transmission rate as it should be doing in order for network activity to continue. Also decreasing at a high rate also results in an undeserved punishment for any node in an unpleasant network location due to the mobility of the system.

Algorithm 2 shows the monitoring process and how the reputation is either increased or decreased depending on the node's behavior. m is the number of observations made by node j about node i's refusal to share its transmission rate. T f is the tolerance of the network i.e. m per reputation value before reducing reputation of a node. y is the number of observations made by node j when node i shares its transmission range in the time period b f . b f is the broadcast factor of the network [START_REF] Balasubratuanian | A Reputation Based Scheme for Stimulating Cooperation in MANETs[END_REF]. This algorithm makes use of only firsthand information as the support rate and the intersecting node is enough to cater for the need for a secondhand information.

Algorithm 2 Coalition Maintenance through Reputation

Jammer's Exclusion from the Coalition

The jammer prevention algorithm aims to reduce the number of false positives. False positive occurs when a legitimate node is been classified as a jammer when it fails to share its transmission rate at a particular time-slot due to been out of range, which is typical of MANET. Nodes that belong to the coalition have a monitor for observations and reputation records for first-hand information about the degree of cooperation of their neighbors as regards sharing their transmission rates. The coalition excludes the jammer by algorithm 3.

For our setup, an excluded node will not be granted re-entry. Algorithm 3 provides the needed self-dependency and self-organization in MANET.

Simulation and Results

We evaluate the performance of the reputation-based coalition game by conducting simulations in NS2. We compare the performance of the reputation-based coalition game with non-reputation based mechanism. The non-reputation based scheme is gotten when we remove the reputation mechanism in our coalition maintenance. The evaluation is based on four metrics: the detection accuracy, detection delay, the percentage of false positives and the detection time of the insider jammer.

Simulation Setup

Table II shows a list of the simulation parameters. Twenty percent of the nodes in the network are classified as the insider jammers.

Algorithm 3 Jammer Exclusion from the Coalition

1: Node i checks node j' reputation value after update. 2: Node j is tolerated until its reputation falls below qL 3: Classify misbehaving nodes according to: jammer, if Ri,j < qL regular, if Ri,j ≥ qL [START_REF] Ferguson | Game Theory[END_REF] 4: if Ri,j is below qL then 5: Node i sends an alarm message 6:

All nodes change their channel of transmission 7:

Accused node's payoff reduces due to bad testimony 8:

Node j attempts to jam the communication channel that has the best transmission rate. 9: Jammer records little or no success because of the proactive step taken by the coalition. 10:

Neighbors of node j, blacklist him and exclude him from their small coalition. 11:

Nodes with reputation greater than qL regroup again. 12: else 13:

No alarm is sent and nodes continue their transmission 14: end if 15: Nodes with Ri,j greater than qL are retained 16: Continue transmission

Results

In Fig. 2, we compare the detection accuracy of the reputation-based scheme with a non reputation-based scheme. The non-reputation based scheme only detects the insider jammer half of the time, our reputation-based scheme, however, performs better with increasing coalition size. In our simulation results, the scheme achieves the maximum accuracy with a coalition of 80 nodes. Detection accuracy is of utmost importance because it is the most important factor that helps to reduce the number of false positives and false negatives. Fig. 3 illustrates the time taken by the coalition to detect the insider jammer. The support rate has an impact on the number of neighboring nodes which in turn affects the detection time. For the result shown in fig. 3, the number of attackers is exactly twenty percent of the size of the coalition. The time taken to detect insider jammer reduces significantly with increasing number of nodes in the network.

Conclusion and Future Work

In this paper, we presented a reputation-based coalition game to detect insider threats in MANET. The key components of the game include algorithms for coalition formation, coalition maintenance and jammer exclusion and security characteristic function for admitting nodes into a coalition. Simulation results demonstrate the effectiveness of our reputation-based coalition game to detect insider jammers in a MANET. Specifically, the results demonstrate few false positives and small detection delay. In the future, we would like to investigate a case of a cooperative attacks that could occur when the excluded nodes form a coalition with the aim of jamming communication in the MANET.

Fig. 2 :

 2 Fig. 2: Detection Accuracy Fig. 3: Detection Delay Fig. 4 compares false positives for the reputation-based model and the non reputation-based model. False positives are easily detected with our reputationbased mechanism because the rate of increase (σ) and decrease (λ) of reputation value is equal resulting in fewer instances of errors in detecting insider jammers. As observed in fig. 4, the 80 node coalition has the least false positive percentage.

Fig. 4 :

 4 Fig. 4: False Positives Fig. 5: Jammer Exclusion Time

Fig. 5

 5 Fig. 5 illustrates the time it takes to exclude the insider jammer from the grand coalition after detection. As the size of the coalition increases, the time taken to exclude insider jammers decreases because the jammer's neighboring nodes quickly raises an alarm when the reputation values fall below q L .

Table 1 :

 1 A summary of notations provided for reference

	Notation	Definition
	N	Number of nodes in the network
	C	Coalition of nodes
	G(i)	Nodes in the transmission range of node i
	vt(C)	Security characteristic function for coalition C
	v(N )	Payoff of the grand coalition
	St(C)	Support rate for the coalition C
	Tt(C)	Transmission rate of coalition C
	Pi,j	Probability of cooperation of node i with node j
	At(C)	Maximal admitting probability for coalition C
	xt(i)	Payoff share of node i
	Ri,j	Reputation value of node i by node j
	R * i,j	Previous reputation value of node i by node j
	R i,k	Reputation value of node i by node k
	vi,j(y)	Factor responsible for increasing reputation value
	ki,j(m)	Factor responsible for reducing reputation value
	qL, qN , qU	Lower, neutral and upper threshold value respectively
	T f , b

f Tolerance factor of the network and broadcast factor σ,λ

Rate of increase and decrease of reputation value respectively

:

  Share reputation table with neighbors at every time-slot. 20: return Ri,j 21: All nodes continue to update their reputation table.

	1: Assign values for σ and λ
	2: Start for all nodes
	3: Node i checks its transmission rate table to assign reputation value for neighbor j.
	4: if j shares its transmission rate then
	5: 6:	compute reputation value according to:
			vi,j(y) = y/Ri,j	(8)
	7: else
	8:	Set vi,j(y) = 0 if y/Ri,j ≤ b f
	9: end if
	10: if j refuses to share its transmission rate then
	11:	compute reputation value according to
	12:
	13: else	ki,j(m) = m/Ri,j	(9)
	14:	Set ki,j(m) = 0 if m/Ri,j ≤ T f
	15: end if
	16: Node i updates node j's reputation value according to: 17:
	Ri,j = R * i,j + σ * (vi,j(y)) -λ * (ki,j(m)) 18: Store this reputation value in its reputation table	(10)
	19

Table 2 :

 2 Parameters for Simulation

	Parameter	Level
	Area	2300 x 1300
	Speed	15m/s
	Radio range	250m
	Simulation time	130s
	Number of mobile nodes	5, 10, 20, 40 and 80 nodes
	Network interface & Channel type	Wireless
	Transmission rate	1-11 Mbps
	Percentage of jammer	20 percent
	Thresholds, qU & qL	0.975 & 0.70 respectively

Insider jamming is also known as internal jamming.

Spread spectrum techniques include Frequency-Hopping Spread Spectrum (FHSS) and Direct Sequence Spread Spectrum (DSSS)[START_REF] Pickholtz | Theory of Spread-Spectrum Communications-A Tutorial[END_REF]

Smart insider jammers are capable of passively scanning the network and then launching an attack based on the information gotten.

Any subset of N is called a coalition, and the set involving all players is called the grand coalition.

The characteristic function v: 2 N → R assigns any coalition C ⊆ N a real number v(C), which is called the worth of coalition C.

The number of nodes in C is |C|.

The security characteristic function's key parameters, support rate, maximum transmission rate and maximal admitting probability, captures the node mobility in the MANET, a property not included in[START_REF] Ferguson | Game Theory[END_REF][START_REF] Li | Achieving Secure and Cooperative Wireless Networks with Trust Modeling and Game Theory[END_REF] . The support rate is the neighbors in the node's transmission range. The maximum transmission rate in the coalition is provided by AFAT while the maximal admitting probability or cooperation probability is unchanged.

Payoff computation is calculated using any of core, shapley value, or nucleolus.

The number of attackers should not exceed the number of legitimate nodes.

The maintenance algorithm was inspired by the the work done by[START_REF] Balasubratuanian | A Reputation Based Scheme for Stimulating Cooperation in MANETs[END_REF].

A time slot is defined as a period of time during which one transmission rate is shared.

Acknowledgment

This work is supported by Office of the Assistant Secretary of Defense for Research and Engineering agreement FAB750-15-2-0120, NSF CNS-1405681, and DHS 2014-ST-062-000059.


Marwan Hammouda

Sami Akin

Jürgen Peissig
email: peissig@ikt.uni-hannover.de

Eective Capacity in Broadcast Channels with Arbitrary Inputs

We consider a broadcast scenario where one transmitter communicates with two receivers under quality-of-service constraints. The transmitter initially employs superposition coding strategies with arbitrarily distributed signals and sends data to both receivers. Regarding the channel state conditions, the receivers perform successive interference cancellation to decode their own data. We express the eective capacity region that provides the maximum allowable sustainable data arrival rate region at the transmitter buer or buers. Given an average transmission power limit, we provide a two-step approach to obtain the optimal power allocation policies that maximize the eective capacity region. Then, we characterize the optimal decoding regions at the receivers in the space spanned by the channel fading power values. We nally substantiate our results with numerical presentations.

Introduction

Cooperative communications can provide promising solutions to satisfy the everincreasing demand for wireless data transmission [START_REF] Tao | An overview of cooperative communications[END_REF]. Therefore, it has been investigated from several perspectives. For instance, the authors have explored the communication throughput in broadcast channels by invoking informationtheoretic tools in [START_REF] Cover | Broadcast channels[END_REF][START_REF] Bergmans | Random coding theorem for broadcast channels with degraded components[END_REF][START_REF] Gallager | Capacity and coding for degraded broadcast channels[END_REF][START_REF] Jindal | On the duality of Gaussian multipleaccess and broadcast channels[END_REF][START_REF] Tse | Optimal power allocation over parallel Gaussian broadcast channels[END_REF][START_REF] Li | Capacity and optimal resource allocation for fading broadcast channels. I. Ergodic capacity[END_REF][START_REF] Gupta | Power allocation over parallel Gaussian multiple access and broadcast channels[END_REF]. Particularly, considering one transmitter and two receivers, Cover obtained the achievable rate regions [START_REF] Cover | Broadcast channels[END_REF]. Then, this scheme was generalized to broadcast channels with many receivers in [START_REF] Bergmans | Random coding theorem for broadcast channels with degraded components[END_REF]. Furthermore, the authors in [START_REF] Li | Capacity and optimal resource allocation for fading broadcast channels. I. Ergodic capacity[END_REF] dened the ergodic capacity regions for fading broadcast channels considering dierent spectrum-sharing techniques and derived the optimal resource allocation policies that maximize these regions. Besides, the authors examined parallel Gaussian broadcast channels and obtained the optimal power allocation policies that achieve any point on the capacity region boundary subject to a sum-power constraint [START_REF] Gupta | Power allocation over parallel Gaussian multiple access and broadcast channels[END_REF].

In the aforementioned studies, the authors considered Gaussian input signaling. On the other hand, it is known that many practical systems make use of input signaling with discrete and nite constellation diagrams. In that regard, the authors in [START_REF] Gündüz | Gaussian two-way relay channel with arbitrary inputs[END_REF] studied two-user broadcast channels with arbitrary input distributions subject to an average power constraint and derived the optimal power allocation policies that maximize the weighted sum rate in low and high signalto-noise ratio regimes. Similarly, the authors in [START_REF] Lozano | Optimum power allocation for parallel Gaussian channels with arbitrary input distributions[END_REF] considered the mutual information in parallel Gaussian channels and derived the optimal power allocation policies. In addition, the authors in [START_REF] Nguyen | Outage exponents of blockfading channels with power allocation[END_REF] explored the optimal power policies that minimize the outage probability in block-fading channels when arbitrary input distributions are applied under both peak and average power constraints. In these studies, the authors beneted from the fundamental relation between the mutual information and the minimum mean-square error (MMSE), which was initially established in [START_REF] Guo | Mutual information and minimum mean-square error in Gaussian channels[END_REF].

In another line of research, cross-layer design concerns gained an increasing interest since many of the current wireless systems are to support delay-sensitive applications. Consequently, quality-of-service (QoS) requirements in the form of delay and buer overow were studied in wireless communications from data-link and physical layer perspectives. Eective capacity was proposed as a performance metric that provides the maximum constant data arrival rate at a transmitter buer that can be supported by a given service (channel) process [START_REF] Wu | Eective capacity: A wireless link model for support of quality of service[END_REF]. Subsequently, eective capacity was scrutinized in several dierent communication scenarios [START_REF] Tang | Quality-of-service driven power and rate adaptation over wireless links[END_REF][START_REF] Musavian | Eective capacity for interference and delay constrained cognitive radio relay channels[END_REF][START_REF] Gursoy | MIMO wireless communications under statistical queueing constraints[END_REF][START_REF] Elalem | Eective capacity and interference analysis in multiband dynamic spectrum sensing[END_REF][START_REF] Akin | On the throughput and energy eciency of cognitive MIMO transmissions[END_REF][START_REF] Ozcan | QoS-driven power control for fading channels with arbitrary input distributions[END_REF]. For instance, eective capacity was examined in one-to-one transmission scenarios in wireless fading channels with feedback information [START_REF] Tang | Quality-of-service driven power and rate adaptation over wireless links[END_REF], interference and delay constrained cognitive radio relay channels [START_REF] Musavian | Eective capacity for interference and delay constrained cognitive radio relay channels[END_REF], multiple-input multiple-output channels [START_REF] Gursoy | MIMO wireless communications under statistical queueing constraints[END_REF], and multi-band cognitive radio channels [START_REF] Elalem | Eective capacity and interference analysis in multiband dynamic spectrum sensing[END_REF]. Moreover, the authors in [START_REF] Ozcan | QoS-driven power control for fading channels with arbitrary input distributions[END_REF] studied the eective capacity of point-to-point channels and derived the optimal power allocation policies to maximize the system throughput by employing arbitrary input distributions under an average power constraint. More recently, we explored the eective capacity regions of multiple access channels with arbitrary input distributions and identied the optimal power allocation policies under average transmission power constraints [START_REF] Hammouda | Eective capacity in multiple access channels with arbitrary inputs[END_REF].

In this paper, dierent than the aforementioned studies and our recent study [START_REF] Hammouda | Eective capacity in multiple access channels with arbitrary inputs[END_REF], we focus on a broadcast channel scenario in which one transmitter employs arbitrarily distributed input signaling to convey data to two receivers under average power constraints and QoS requirements. We dene the eective capacity region and provide an algorithm to obtain the optimal power allocation policies that maximize this region by enforcing the relation between the mutual information and the MMSE. Then, we express the optimal decoding regions in the space spanned by the channel fading power values. We nally justify our analytical results with numerical presentations.

2 System Description

Channel Model

As shown in Figure 1, we consider a broadcast channel scenario in which one transmitter communicates with two receivers. We assume that the transmitter is equipped with two data buers each of which stores data to be transmitted to the corresponding receiver. The transmitter, regarding the instantaneous channel Fig. 1: Channel model: A two-user broadcast channel in which one transmitter communicates with two receivers. The transmitter performs superposition coding, while each receiver performs successive interference cancellation with a certain order. The decoding order depends on the channel conditions, i.e., the magnitude of the squares of the channel fading coecients,

z 1 = |h 1 | 2 and z 2 = |h 2 | 2 .
conditions and employing a superposition coding strategy with a given order, sends data from both buers in frames of T seconds. During data transmission, the input-output relation between the transmitter and the j th receiver at time instant t is given by y j (t) = h j (t)x j (t) P j (t) + h j (t)x m (t) P m (t) + w j (t) for t = 1, 2, • • • , [START_REF] Akin | On the throughput and energy eciency of cognitive MIMO transmissions[END_REF] where j, m ∈ {1, 2} and j = m. Above, x j (t) and x m (t) are the channel inputs at the transmitter and carries information to the j th and m th receivers, respectively, and y j (t) is the channel output at the j th receiver. Moreover, w j (t) represents the additive thermal noise at the j th receiver, which is a zero-mean, circularly symmetric, complex Gaussian random variable with a unit variance, i.e., E{|w j | 2 } = 1. The noise samples {w j (t)} are assumed to be independent and identically distributed. Meanwhile, h j (t) represents the fading coecient between the transmitter and the j th receiver, where E{|h j | 2 } < ∞. The magnitude square of the fading coecient is denoted by z j (t), i.e., z j (t) = |h j (t)| 2 . We consider a block-fading channel and assume that the fading coecients stay constant for a frame duration of T seconds and change independently from one frame to another. We further assume that h 1 and h 2 are independent of each other and perfectly known to the transmitter and both receivers. Thence, the transmitter can adapt the transmission power policy and the transmission rate for each receiver accordingly. In addition, the transmission power at the transmitter is constrained as follows:

E t {P 1 (t)} + E t {P 2 (t)} ≤ P , (2)
where P 1 (t) and P 2 (t) are the instantaneous power allocation policies for the 1 st and 2 nd receivers, respectively, i.e., E x1 {x 1 (t)} ≤ P 1 (t) and E x2 {x 2 (t)} ≤ P 2 (t), and P is nite. We nally note that the available transmission bandwidth is B Hz. In the rest of the paper, we omit the time index t unless otherwise needed for clarity.

Achievable Rates

In this section, we provide the instantaneous achievable rates between the transmitter and the receivers given the input signal distributions. We can express the instantaneous achievable rate between the transmitter and the j th receiver by invoking the mutual information between the channel inputs at the transmitter and the channel output at the j th receiver. Given that h j and h m are available at the transmitter and the j th receiver and that the j th receiver does not perform successive interference cancellation, the instantaneous achievable rate is given as [START_REF] Gallager | Information theory and reliable communication[END_REF]

I(x j ; y j ) = E log 2 f yj |xj (y j |x j ) f yj (y j ) for j ∈ {1, 2},
where f yj (y j ) = xj p xj (x j )f yj |xj (y j |x j ) is the marginal probability density function (pdf) of the received signal y j and f yj |xj (y j |x j ) = 1 π e -|yj -hj xj Pj | 2 . On the other hand, if the j th receiver performs successive interference cancellation, i.e., the j th receiver initially decodes x m and then decodes its own data, we have the achievable rate as follows:

I(x j ; y j |x m ) = E log 2 f uj |xj (u j |x j ) f uj (u j ) ,
where u j = y j -h j x m √ P m . Above, f uj (u j ) = xj p xj (x j )f uj |xj (u j |x j ) is the marginal pdf of u j and f uj |xj (u j |x j ) = 1 π e -|uj -hj xj Pj | 2 . We assume that each receiver, regarding the channel conditions and the encoding strategy at the transmitter, performs successive interference cancellation with a certain order if it is possible to do so. For instance, if the decoding order is (j, m) for j, m ∈ {1, 2} and j = m, the j th receiver decodes its own data by treating the signal carrying information to the m th receiver as interference. On the other hand, the m th receiver initially decodes the data sent to the j th receiver and subtracts the encoded signal from the channel output, and then decodes its own signal. Recall that both receivers perfectly know the instantaneous channel fading coecients, h 1 and h 2 , and the decoding order depends on the relation between the magnitude squares of channel fading coecients z 1 and z 2 . Therefore, we consider Z as the region in the (z 1 , z 2 )-space where the decoding order is (2,1) and Z c , the complement of Z, as the region where the decoding order is [START_REF] Akin | On the throughput and energy eciency of cognitive MIMO transmissions[END_REF][START_REF] Bergmans | Random coding theorem for broadcast channels with degraded components[END_REF]. Noting that the transmitter can set the transmission rates to the instantaneous achievable rates, we can express the instantaneous transmission rate for the 1 st receiver as

r 1 (z 1 , z 2 ) = I(x 1 ; y 1 |x 2 ), Z, I(x 1 ; y 1 ), Z c , (3)
and the instantaneous transmission rate for the 2 nd receiver as

r 2 (z 1 , z 2 ) = I(x 2 ; y 2 ), Z, I(x 2 ; y 2 |x 1 ), Z c . ( 4
)
The decoding regions can be determined in such a way to maximize the objective throughput.

Eective Capacity

Recall that the transmitter holds the data initially in the buers. As a result, delay and buer overow concerns become of interest. Therefore, focusing on the data arrival processes at the transmitter, a 1 and a 2 in Fig. 1, we invoke eective capacity as the performance metric. Eective capacity provides the maximum constant data arrival rate that a given service (channel) process can sustain to satisfy certain statistical QoS constraints [START_REF] Wu | Eective capacity: A wireless link model for support of quality of service[END_REF]. Let Q be the stationary queue length at any data buer. Then, we can dene the decay rate of the tail distribution of the queue length Q as

θ = -lim q→∞ log e Pr(Q ≥ q) q .
Hence, for a large threshold q max , we can approximate the buer overow probability as Pr(Q ≥ q max ) ≈ e -θqmax . Larger θ implies stricter QoS constraints, whereas smaller θ corresponds to looser constraints. For a discrete-time, stationary and ergodic stochastic service process r(t), the eective capacity at the buer is expressed as

-lim t→∞ 1 θt log e E{e -θS(t) },
where S(t) = t τ =1 r(τ ).

Since the transmitter in the aforementioned model has two dierent transmission buers, we assume that each buer has its own QoS requirements. Therefore, we denote the QoS exponent for each queue by θ j for j ∈ {1, 2}. Noting that the transmission bandwidth is B Hz, the block duration is T seconds, and the channel fading coecients change independently from one transmission frame to another, we can express the eective capacity at each buer in bits/sec/Hz as

a j = - 1 θ j T B log e E e -θj T Brj (z1,z2) , (5)
where the expectation is taken over the space spanned by z 1 and z 2 . Now, utilizing the denition given in [START_REF] Qiao | Achievable throughput regions of fading broadcast and interference channels under QoS constraints[END_REF], we express the eective capacity region of the given broadcast transmission scenario as follows:

C E (Θ) = r1,r2 C(Θ) ≥ 0 : C j (θ j ) ≤ a j , (6)
where Θ = [θ 1 , θ 2 ] is the vector of decay rates, C(Θ) = [C 1 (θ 1 ), C 2 (θ 2 )] is the vector of the arrival rates at the transmitter buers, and 0 is the vector of zeroes.

Performance Analysis

In this section, we concentrate on maximizing the eective capacity region dened in [START_REF] Gallager | Capacity and coding for degraded broadcast channels[END_REF] under the QoS requirements for each transmitter buer and the total average power constraint given in [START_REF] Bergmans | Random coding theorem for broadcast channels with degraded components[END_REF]. Notice that the eective capacity region is convex [START_REF] Qiao | Achievable throughput regions of fading broadcast and interference channels under QoS constraints[END_REF]. Hence, we can reduce our objective to maximizing the boundary surface of the region and express it as follows [START_REF] Tse | Multiaccess fading channels. I. Polymatroid structure, optimal resource allocation and throughput capacities[END_REF]:

max Z,Z c E{P1}+E{P2}≤P λ 1 a 1 + λ 2 a 2 , (7)
where λ 1 , λ 2 ∈ [0, 1] and λ 1 +λ 2 = 1. In order to solve this optimization problem, we rst obtain the power allocation policies in dened decoding regions, Z and Z c , and then, we provide the optimal decoding regions.

Optimal Power Allocation

Here, we derive the optimal power allocation policies that maximize the eective capacity region [START_REF] Gündüz | Gaussian two-way relay channel with arbitrary inputs[END_REF] given Z and Z c . In the following analysis, we provide the proposition that gives the optimal power allocation policies: Proposition 1. The optimal power allocation policies, P 1 and P 2 , that maximize the expression in [START_REF] Gündüz | Gaussian two-way relay channel with arbitrary inputs[END_REF] are the solutions of the following equalities:

λ 1 ψ 1 e -θ1T Br1(z) dr 1 (z) dP 1 + λ 2 ψ 2 e -θ2T Br2(z) dr 2 (z) dP 1 = ε, (8)
λ 2 ψ 2 e -θ2T Br2(z) dr 2 (z) dP 2 = ε, (9)
for z = [z 1 , z 2 ] ∈ Z, and

λ 1 ψ 1 e -θ1T Br1(z) dr 1 (z) dP 1 = ε, (10)
λ 1 ψ 1 e -θ1T Br1(z) dr 1 (z) dP 2 + λ 2 ψ 2 e -θ2T Br2(z) dr 2 (z) dP 2 = ε, (11)
for z ∈ Z c . Above, ψ 1 = E z e -θ1T Br1(z) and ψ 2 = E z e -θ2T Br2(z) , and ε is the Lagrange multiplier of the average power constraint in (2).

Proof. Omitted due to the page limitation.

In Proposition 1, the derivatives of the transmission rates with respect to the corresponding power allocation policies are given as for m, j ∈ {1, 2} and m = j.

In the following theorem, we provide the derivatives of the mutual information with respect to the power allocation policies: Theorem 1. Let z 1 and z 2 be given. The rst derivative of the mutual information between x j and y j with respect to the power allocation policy, P j , is given by dI(x j ; y j ) dP j = z j MMSE(x j ; y j ) + z j

P m P j Re(E{x j x * m -xj (y j )x *
m ((y j ))}) [START_REF] Jeong | MIMO channel measurement and analysis for 4G mobile communication[END_REF] for j, m ∈ {1, 2} and j = m. Above, (•) * is the complex conjugate operation and Re(•) is the real part of a complex number. Meanwhile, the derivative of the mutual information between x j and y j with respect to P j given x m is dI(x j ; y j |x m ) dP j = z j MMSE(x j ; y j |x m ). , respectively.

Proof. Omitted due to the page limitation.

As clearly noticed in ( 8)-( 11), a closed-form solution for P 1 or P 2 cannot be obtained easily, which is mainly due to the tied relation between P 1 and P 2 . For instance, P 1 is a function of P 2 as observed in [START_REF] Guo | Mutual information and minimum mean-square error in Gaussian channels[END_REF] for z ∈ Z, whereas P 2 is a function of P 1 as seen in [START_REF] Hammouda | Eective capacity in multiple access channels with arbitrary inputs[END_REF] for z ∈ Z c . Therefore, we need to employ numerical techniques that consist of iterative solutions. Hence, in the following, we carry out an iterative algorithm that provides the optimal power allocation policies given decoding regions: Algorithm 1 1: Given λ 1 , λ 2 , Z and Z c ; 2: Initialize ψ 1 , ψ 2 ; For given P 1 , compute the optimal P 2 by solving (9) ;

2 f

 2 MMSE and MMSE estimate are dened asMMSE(u; v|s) = 1 -1 π u up(u)f v|u,s (v|u, s) v|s (v|s) dvand û(v) = u up(u)f v|u (v|u) fv(v)

This work was partially supported by the European Research Council under Starting Grant306644.

9:

With obtained P 2 , compute the optimal P 1 by solving (8) ; For given P 1 , compute the optimal P 2 by solving [START_REF] Hammouda | Eective capacity in multiple access channels with arbitrary inputs[END_REF] ; 12: For computed P 2 , compute the optimal P 1 by solving [START_REF] Gursoy | MIMO wireless communications under statistical queueing constraints[END_REF] ; 13: end if If not, update ε and return to Step 5 22: Compute ψ 1 = E z e -θ1nr1(z) and ψ 2 = E z e -θ2nr2(z) Set ψ 1 = ψ 1 and ψ 2 = ψ 2 ; 27: end if 28: end while Given λ j and ψ j for j ∈ {1, 2}, it is shown in [START_REF] Ozcan | QoS-driven power control for fading channels with arbitrary input distributions[END_REF] that both ( 9) and ( 10) has at most one solution. We can further show that (8) has at most one solution for P 1 when P 2 is given, and that [START_REF] Hammouda | Eective capacity in multiple access channels with arbitrary inputs[END_REF] has at most one solution for P 2 when P 1 is given. Consequently, we can guarantee that Steps 8, 9, 11 and 12 in Algorithm 1 will converge to a single unique solution. In addition, it is clear that [START_REF] Guo | Mutual information and minimum mean-square error in Gaussian channels[END_REF] and [START_REF] Gursoy | MIMO wireless communications under statistical queueing constraints[END_REF] are monotonically decreasing functions of P 1 , and that (9) and ( 11) are monotonically decreasing functions of P 2 . Hence, in region Z, we rst obtain P 2 by solving (9) for given P 1 , and then we nd P 1 by solving (8) after inserting P 2 into (8). Similarly, in region Z c , we rst obtain P 2 by solving [START_REF] Hammouda | Eective capacity in multiple access channels with arbitrary inputs[END_REF] for given P 1 , and then we nd P 1 by solving [START_REF] Gursoy | MIMO wireless communications under statistical queueing constraints[END_REF] after inserting P 2 into [START_REF] Gursoy | MIMO wireless communications under statistical queueing constraints[END_REF]. We can employ bisection search methods to obtain P 1 and P 2 . In the above approach, when either P 1 or P 2 becomes negative, we set it to zero.

Optimal Decoding Order

Obtaining the optimal power allocation policies, we investigate the optimal decoding regions in this section. We initially notice that with no QoS constraints, i.e., θ 1 = θ 2 = 0, the eective capacity region is reduced to the ergodic capacity region. In this case, the symbol of the receiver with the strongest channel is always decoded last [START_REF] Jindal | On the duality of Gaussian multipleaccess and broadcast channels[END_REF]. Specically, when z j ≥ z m the symbol of the j th receiver is decoded last. This result is based on the assumption of Gaussian input signaling. To the best of our knowledge, no such a result is obtained for broadcast channels when QoS constraints are applied, i.e, θ 1 > 0 and θ 2 > 0, and/or when arbitrary input signaling is employed. In the following, we consider a special case of θ 1 = θ 2 for θ > 0 and provide the optimal decoding order regions when arbitrary input distributions are employed by the transmitter: Theorem 2. Let z 1 , z 2 and P be given. Dene z 1 for any given z 2 ≥ 0 such that the decoding order is (2,1) when z 2 > z 1 . Otherwise, it is [START_REF] Akin | On the throughput and energy eciency of cognitive MIMO transmissions[END_REF][START_REF] Bergmans | Random coding theorem for broadcast channels with degraded components[END_REF]. With arbitrary input distributions and power allocation policies at the transmitter, the optimal z 1 for any given z 2 value is the solution of the following equality:

Proof. Omitted due to the page limitation.

Numerical Results

In this section, we present the numerical results. Throughout the paper, we set the available channel bandwidth to B = 100 Hz and the transmission frame duration to T = 1 second. We further assume that h 1 and h 2 are independent of each other and set

In addition, we assume that signals transmitted to both receivers are independent of each other, i.e., E{x j x * m } = 0.

Unless indicated otherwise, we set the QoS exponents θ 1 = θ 2 = 0.01. We nally assume that both receivers have the same noise statistics, i.e.,

and we dene the received signal-to-noise ratio at each receiver with P E{|w| 2 } = P . In Fig. 2, we initially consider binary phase shift keying (BPSK) employed at the transmitter for both receivers and investigate the eect of channel statistics on the eective capacity region in Rician fading channels with a line-of-sight parameter K, which is the ratio of the power in the line-of-sight component Fig. 3: Eective capacity region boundary with dierent modulation techniques and signal-to-noise ratio values when K = -6.88 dB.

to the total power in the non-line-of-sight components. The empirical values of K are determined to be -6.88 dB, 8.61 dB and 4.97 dB for urban, rural and suburban environments at 781 MHz, respectively [START_REF] Jeong | MIMO channel measurement and analysis for 4G mobile communication[END_REF]. Considering these K values, we obtain results for dierent signal-to-noise ratio values, i.e., P = 0 and -5 dB. We can clearly see that the eective capacity region broadens as K increases because the line-of-sight component becomes more dominant with increasing K. We also observe that the eect of K is more apparent when the signal-to-noise ratio is greater.

Subsequently, setting K = -6.88 dB, we investigate the eect of dierent signal modulation techniques with dierent signal-to-noise ratio values in Fig. 3. We consider BPSK, quadrature amplitude modulation (QAM) and Gaussian input signaling. We can easily notice the superiority of the Gaussian input signaling over the others, while BPSK has the lowest performance. However, the performance gap is reduced with decreasing P . Lastly, we explore the eect of the QoS exponent θ on the eective capacity performance in Fig. 4. We set P = 5 dB and K = -6.878 dB and plot results for dierent modulation techniques. Increasing θ results in a smaller eective capacity region as the system is subject to stricter QoS constraints.

Conclusion

In this paper, we have examined optimal power allocation policies that maximize the eective capacity region of a two-user broadcast transmission scenario with arbitrarily distributed input signals. We have invoked the relation between MMSE and the rst derivative of mutual information with respect to transmission power. We have proposed an iterative algorithm that converges to optimal power allocation policies given decoding regions under an average Fig. 4: Eective capacity region boundary with dierent modulation techniques and decay rate parameters, θ = θ 1 = θ 2 when K = -6.88 dB and P = 5 dB. power constraint. Obtaining power allocation policies, we have further characterized decoding regions for successive interference cancellation by the receivers. Through numerical solutions, we have substantiated our results. In general, there is an apparent superiority of Gaussian input signaling over the other modulation techniques, whereas the gap between Gaussian input signaling and the others decreases with decreasing signal-to-noise ratio. Therefore, it is reasonable to employ simple modulation techniques in low signal-to-noise ratio regimes.


Zeki Bilgin
email: zbilgin@egm.gov.tr

Murat Gunestas
email: mgunestas@egm.gov.tr

Omer Demir
email: odemir@egm.gov.tr

Sahin Buyrukbilen
email: sbuyrukbilen@egm.gov.tr

Optimal Link Deployment for Minimizing Average Path Length in Chain Networks

Keywords: Chain networks, average path length, link deployment

This study considers chain-topology networks, which has certain inherent limitations, and presents an optimization model that augments the network by the addition of a new link, with the objective of minimizing Average Path Length (APL). We built up a mathematical model for APL, and formulated our problem as Integer Programming. Then, we solved the problem experimentally by brute-force, trying all possible topologies, and found the optimal solutions that minimize APL for certain network sizes up to 1000 nodes. Later on, we derived analytical solution of the problem by applying Linear Regression method on the experimental results obtained. We showed that APL on a chain-topology network is decreased by the proposed optimization model, at a gradually increasing rate from 24.81% to asymptotic value of 41.4% as network grows. Additionally, we found that normalized length of the optimal solutions decreases logarithmically from 100 % to 58.6048 % as network size gets larger.

Introduction

Many industries, today, prefer chain topology on their networks comprised of nodes connected each other consecutively throughout both long and narrow deployment areas like railways [START_REF] Kim | Container Security Device Chain Network for Safe Railway Transportation[END_REF], highways [START_REF] Agbinya | Design Considerations of MoHotS and Wireless Chain Networks[END_REF], underground mines [START_REF] Haifeng | Energy Optimal Routing for Long Chain-type Wireless Sensor Networks in Underground Mines[END_REF][START_REF] Yuan | Long Distance Wireless Sensor Networks Applied in Coal Mine[END_REF], as well as in some special type of wireless sensor and mesh networks [START_REF] Haifeng | Energy Optimal Routing for Long Chain-type Wireless Sensor Networks in Underground Mines[END_REF][START_REF] Yuan | Long Distance Wireless Sensor Networks Applied in Coal Mine[END_REF][START_REF] Zhou | Source-aware Redundant Packet Forwarding Scheme for Emergency Information Delivery in Chain-typed Multihop Wireless Sensor Networks[END_REF][START_REF] Chen | Lifetime Maximization Algorithm for Chain Wireless Sensor Networks[END_REF][START_REF] Leu | Maximum Capacity in Chain-topology Wireless Mesh Networks[END_REF] and backbones of telecommunication systems [START_REF] Flammini | Wireless ATM Layouts for Chain Networks[END_REF]. Similarly, it is also a well-known implementation to connect (wi-fi) routers in daisy-chain topology to provide internet access at each floor in towers or high buildings.

A major disadvantage of chain networks is to have high Average Path Length (AP L) relative to network size, unlike many other types of networks owning the properties of "small-world" networks [START_REF] Watts | Collective Dynamics of 'small-world[END_REF]. AP L is generally desired to be small, and is investigated analytically and numerically in many studies related to network design and optimization [START_REF] Xu | Research of Scalability of the Belt-type Sensor Networks[END_REF][START_REF] Chen | The Average Path Length of Scale Free Networks[END_REF][START_REF] Yen | An Efficient Approach to Updating Closeness Centrality and Average Path Length in Dynamic Networks[END_REF][START_REF] Gulyás | An Estimation of the Shortest and Largest Average Path Length in Graphs of Given Density[END_REF][START_REF] Guo | Effect of Random Edge Failure on the Average Path Length[END_REF][START_REF] Reppas | Tuning the Average Path Length of Complex Networks and Its Influence to the Emergent Dynamics of the Majorityrule Model[END_REF][START_REF] Peng | Average Path Length for Sierpinski Pentagon[END_REF][START_REF] Zhang | Analytical Solution of Average Path Length for Apollonian Networks[END_REF][START_REF] Fronczak | Average Path Length in Random Networks[END_REF], social networks [START_REF] Reppas | Tuning the Average Path Length of Complex Networks and Its Influence to the Emergent Dynamics of the Majorityrule Model[END_REF][START_REF] Zhang | Analytical Solution of Average Path Length for Apollonian Networks[END_REF][START_REF] Fronczak | Average Path Length in Random Networks[END_REF], computing [START_REF] Mao | Analysis of Average Shortest-path Length of Scale-free Network[END_REF], and logic design [START_REF] Butler | Average Path Length of Binary Decision Diagrams[END_REF].

In this paper, we examine AP L for chain networks, and propose an optimization model based on an additional link deployment to the network, with the objective of minimizing AP L. We derive analytical formulation for AP L prior to and subsequent to optimization process, as well as obtain numerical results which precisely agreed with analytical analysis.

Suppose we have a chain-topology network with n nodes, containing bidirectional links between consecutive nodes. This network can be represented as a path graph, P n , with undirected edges1 as depicted in Figure 1.

Fig. 1: A path graph representing a chain-topology network with n nodes Suppose, we aim at augmenting this network further by adding a new performance enhancing link between a certain pair of nodes on the network2 as illustrated in Figure 2. We should notice at this point that the augmentation process (i.e. adding a new link) is intentionally confined by just one new link in order to keep the optimization cost minimum, and that the implementation cost of such a new link can be assumed fixed regardless of the distance between connected nodes, which is true especially for the leased lines obtained from ISPs. We are now ready to ask our optimization problem: Main Problem: Which nodes should be connected to reach the objective of minimizing average path length (APL) on the network?

Not only does the proposed optimization model minimize AP L, but also it improves robustness on chained networks by means of generating alternative routes, as well as reduces cost of packet transmissions.

Related Work

Chain Networks

Given the side effects of unbalanced energy consumptions at nodes in chain networks used in underground mines or on trains, the studies of [START_REF] Kim | Container Security Device Chain Network for Safe Railway Transportation[END_REF][START_REF] Haifeng | Energy Optimal Routing for Long Chain-type Wireless Sensor Networks in Underground Mines[END_REF][START_REF] Yuan | Long Distance Wireless Sensor Networks Applied in Coal Mine[END_REF][START_REF] Chen | Lifetime Maximization Algorithm for Chain Wireless Sensor Networks[END_REF] proposed different protocols or node deployment strategies, aiming to provide balanced energy consumptions at nodes in order to increase network lifetime.

Agbinya [START_REF] Agbinya | Design Considerations of MoHotS and Wireless Chain Networks[END_REF] discussed a specific application of chain networks on highways, and addressed certain characteristics of the network such as interference level, coverage area and path loss; on the other hand, Zhou et al. [START_REF] Zhou | Source-aware Redundant Packet Forwarding Scheme for Emergency Information Delivery in Chain-typed Multihop Wireless Sensor Networks[END_REF], in a recent study, considered Chain-typed Wireless Sensor Networks (CWSN) deployed in coal mines, and proposed a source-aware redundant packet forwarding scheme for emergency information delivery in CWSN.

Leu and Huang [START_REF] Leu | Maximum Capacity in Chain-topology Wireless Mesh Networks[END_REF] proposed a mathematical model that calculates the maximum throughput of a Wireless Mesh Network in chain-topology, dealing with signal interference, hidden nodes and STDMA time slots among nodes.

Flammini et al. [START_REF] Flammini | Wireless ATM Layouts for Chain Networks[END_REF] considered the construction of wireless ATM layouts for a chain of base stations, and showed that the problem studied was NP-complete for special instances, and provided optimal solutions for certain cases.

Average Path Length (APL)

Several researchers derived analytical formulation of AP L for different type of networks. For instance, Kleinrock and Silvester [START_REF] Kleinrock | Optimum Transmission Radii for Packet Radio Networks or Why Six is a Magic Number[END_REF] considered random graphs; Fronczak et al. [START_REF] Fronczak | Average Path Length in Random Networks[END_REF] and Guo et al. [START_REF] Guo | Effect of Random Edge Failure on the Average Path Length[END_REF] studied a large class of uncorrelated random networks with hidden variables; Zhang et al. [START_REF] Zhang | Analytical Solution of Average Path Length for Apollonian Networks[END_REF] examined Apollonian networks; Peng [START_REF] Peng | Average Path Length for Sierpinski Pentagon[END_REF] dealt with Sierpinski pentagon; Gulyás et al. [START_REF] Gulyás | An Estimation of the Shortest and Largest Average Path Length in Graphs of Given Density[END_REF] focused on the networks with given size and density; Chen et al. [START_REF] Chen | The Average Path Length of Scale Free Networks[END_REF] investigated Barabási-Albert scale free model; Zhi-guang et al. [START_REF] Xu | Research of Scalability of the Belt-type Sensor Networks[END_REF] discussed belt-type networks; and Gao et al. [START_REF] Gao | Asymptotic Formula on Average Path Length of Fractal Networks Modeled on Sierpinski Gasket[END_REF] analysed Sierpinski gasket in a recent article.

In the field of logic design, Butler et al. [START_REF] Butler | Average Path Length of Binary Decision Diagrams[END_REF] studied AP L of binary decision diagrams by deriving the AP L for various functions, and showed that the AP L for benchmark functions is typically much smaller than for random functions.

Mao and Zhang [START_REF] Mao | Analysis of Average Shortest-path Length of Scale-free Network[END_REF] considered the computation problem of AP L for large scale-free networks, and presented a dynamic programming model to solve the load-balancing problem for coarse-grained parallelization. Yen et al. [START_REF] Yen | An Efficient Approach to Updating Closeness Centrality and Average Path Length in Dynamic Networks[END_REF] presented an efficient method for updating the closeness centrality of each vertex and the AP L of a network, where edges change dynamically as in the case of social networks. In a recent study, Reppas et al. [START_REF] Reppas | Tuning the Average Path Length of Complex Networks and Its Influence to the Emergent Dynamics of the Majorityrule Model[END_REF] introduced rewiring rules to tune AP L on a network while keeping the degree and clustering coefficient distribution unchanged.

To the best of our knowledge, ours is the first study to propose an optimization model aiming to minimize AP L for chain networks by optimal deployment of an incremental link.

Mathematical Model

Pure Path

Average path length, AP L, of a network is an important parameter showing the efficiency of information transmission on the network, and can be calculated by finding the shortest path between all pairs of nodes, adding their lengths3 up, and then dividing by the total number of pairs.

To find the mathematical expression for AP L of a chain network, let P n be a path graph including n vertices indexed in sequence from 1 to n, like v 1 , v 2 , ..., v n , as depicted in Figure 1. It is obvious that the shortest path between a certain pair of nodes on a path graph is the subpath, having no alternative, between this pair of nodes. Moreover, the length of such a subpath is equal to the number of edges on itself. Thus, since the vertices are indexed in order, length of a subpath (P L) between vertices of v j and v k on P n can be stated rigorously as follows.

P L (vj ,v k ) = |k -j|
Then, the Equation 1gives the sum of path lengths for all (unordered) pairs4

P L (AllP airs) = n-1 i=1 n-i k=1 k (1)
After rewriting the Equation 1, and dividing by the number of all pairs, which is n(n-1)

2

, we find the AP L for the path graph of P n as given in Equation 2.

AP L Pn = P L (AllP airs) n(n-1) 2 = n + 1 3 (2)
According to Equation 2, the AP L for a chain-topology network is linearly proportional with the length of the chain or the number of nodes, i.e. O(n), and almost equal to one third of network diameter.

Path with an Additional Edge

Let P n be a graph obtained by adding a new edge (v x , v y ) to the path graph P n as depicted in Figure 2. Rigorously,

P n = P n ∪ (v x , v y )
To built a general mathematical expression for AP L on P n , we first studied on small networks (e.g. around 10 nodes), manually calculated AP L, and produced a sketchy formula for AP L. Then, we extended our work with larger networks, as repeatedly checking accuracy of the formula, and revised it when needed until the formula persistently gave correct values for all networks investigated. This process yielded Equation 3. Yet we also verified its correctness via experiments as described in the following sections.

AP L P n = t-1 i=1 t-i k=1 k + (h -1)( x i=1 i + n-y+1 i=1 i) -1 + R n(n-1) 2 (3)
where h = y -x, t = n -h + 1, and

R = (2n -h -1) h/2 i=0 i -h(n -h + 1) + 2, if h is even (2n -h -1) (h-1)/2 i=0 i + (h+1) 2 4 -(h-1)(n-h+3) 2 , if h is odd
Thus, we obtained analytical expressions for AP L prior to and subsequent to additional link attachment into a path graph, as in Equations 2 and 3, which allows us to formulate our problem in the form of Integer Linear Programming (IP) as follows: minimize AP L P n subject to n, x, y are integer

x < y

1 ≤ x ≤ n 1 ≤ y ≤ n
where AP L P n is given in Equation 3.

It is known that IP is NP-hard [START_REF] Cormen | Introduction to Algorithms[END_REF], which implies that there is no known polynomial-time solution for IP problems. Yet, in the following sections, we will solve certain instances of the problem above by experimentally in the first place, and then, construct a general analytical solution for any value of network size (i.e. n) by means of linear regression method.

Finding Optimal Solutions

Numerical Solutions by Experiment

To find optimal solutions for certain cases of the problem introduced, we prepared an experimental set-up shown as pseudo-code in Figure 3. return AP L

In the experiment, we incremented network size from 3 nodes to 1000 nodes, and varied attachment points (i.e. vertices) of the additional link for all possible cases as a brute-force approach. At each step of network size, we first defined network topology by entering adjacency list for the network, for all possible deployment of the additional link as varying variables of x and y, which represent the relative location of vertices v x and v y . Then, for each topology, we found the shortest paths for all pairs by implementing Dijkstra's well-known shortest path algorithm [START_REF] Dijkstra | A Note on Two Problems in Connection with Graphs[END_REF][START_REF] Cormen | Introduction to Algorithms[END_REF]. Notice that Dijkstra determines the shortest path between only one pair of nodes, and for this reason, we iteratively employed it for all pairs in the graph (i.e. topology). After calculating lengths (i.e. hop counts) of the shortest paths for all pairs, we took average of them, and thus found APL. Finally, we identified the minimum APL among all calculated APLs yielded as varying locations of v x and v y . This experimental process was repeated for certain network sizes of 3, 5, 10, 20, 50, 100, 200, 500 and 1000 nodes. Table 1 contains some of the numerical results acquired in the experiments, including optimal solutions that minimize APL as well as results belong to ring topologies (i.e. the cases in which the first and the last nodes of paths are connected each other by the additional link). The first column in the table includes network size in terms of the number of nodes, while the second and the third columns contain AP L for pure path (P n ) and ring topology (i.e. P n ∪ (v 1 , v n )) respectively. Notice that ring topology occurs when the first and the last nodes on a path are connected each other. The fourth column involves minimum AP L which appears when the additional link is placed optimally (i.e. P n ∪ (v x opt , v y opt )). The last column shows optimal values of (v x , v y ) that minimize AP L. Verification of the mathematical model: One might doubt the accuracy of our mathematical model presented in Section 4, i.e. Equation 3. To verify correctness of this mathematical expression, we first computed AP L values by using Equations 3 as assigning all possible values to the variables up to network size of 1000 nodes, and then searched out the instances giving minimum AP L for each network size. Afterwards, we compared minimum AP L values computed in Equation 3 with the AP L values yielded from the experimental calculations for certain network sizes as listed in Table 1. We eventually observed that both the mathematical model and the experimental calculations give precisely the same outcomes for AP L, which shows the consistency between these two different approaches.

Analytical Solution by Linear Regression

Table 1 contains numerical results of optimal solutions for certain network sizes. However, to make a comprehensive analysis including asymptotic behaviour of optimal solutions and other variables, we need to establish analytical relations between these variables. For this purpose, we applied a linear regression method on the numerical results at hand, based on least square technique, and consequently, found the following relations.

AP L P n (n) = 0.195331 * n + 0.559447 (4)
x opt = Round(0.207174 * n -0.0251311) ( 5)

y opt = Round(0.793222 * n + 0.0497688) (6)
where Round(z) is a function which returns the nearest integer to z.

In fact, Equations 5 & 6 give precise answers to the main problem asked at the beginning of this paper. Equation 4, on the other hand, yields exact outcome for AP L when an optimal solution is applied.

Discussions

Average Path Length (APL)

Figure 5 depicts AP L for both P n and P n when optimal values of (v x , v y ) is applied, as network size varies from 3 nodes to 1000 nodes. As seen in the figure, AP L linearly increases for both cases as network size grows. However, notice that P n has higher slope than P n , which means that adding extra edge reduces AP L on a network. Notice that there is also model fit (i.e. regression line) which is obtained by linear regression. Goodness of fit can even be visually evaluated in Figure 5, as the fitted line and numerical data exactly matches each other.

Improvement

Figure 6 exhibits the Improvement, i.e. the rate of decrement, on AP L when an additional edge is placed to the network at optimal positions. As can be followed in the figure, the improvement rate begins with a slow growth at around 24.81 % when n = 3, followed by a period of moderate growth, and then back to a period of slow growth asymptotically approaching to 41.4 %, which is consistent with the analytical analysis below.

Optimal Solutions

Equations 5 & 6 are optimal solutions in analytic form, while values on the fifth column in Table 1 are numeric solutions for certain network sizes. Thanks to Equations 5 & 6, one can readily determine optimal values of (v x , v y ) for any network size. It is interesting to observe that the optimal solutions, when n = 3 and n = 5, are two end points of the path (i.e. (v x , v y ) equals to (v 1 , v 3 ) and (v 1 , v 5 ) respectively) . As network size grows, the optimal values of v x and v y slide gradually towards the center of the network. This observation motivated us to investigate normalized length between two end points (i.e. v x and v y ) of optimal solutions in the next part.

Another observation here is that there is only one (i.e. unique) optimal solution when the network size (n) is odd, whereas there may emerge many optimal solutions when n is even, as can be observed in the fifth column of Table 1. We discovered that alternative optimal solutions for the same network yield isomorphic graphs when they are applied.

Normalized Length of Optimal Solutions (NLOS)

N LOS represents the normalized distance between two end points (i.e. v x opt and v y opt ) of optimal link deployments that minimize AP L. The normalization process is performed with respect to network size. Figure 6 includes N LOS as network size logarithmically grows. It can be deduced from the figure that the N LOS is reduced logarithmically beginning from 100 % to around 58.6 %, which is consistent with the analytical analysis below. This means that the optimal solutions occur at around two end points of chain-topology when network size is small, whereas attachment points of optimal solutions move away from this end points as network size grows.

Conclusion

Chain-topology networks performs poorly in certain performance metrics such as throughput, robustness, energy efficiency in data transmissions [START_REF] Kim | Container Security Device Chain Network for Safe Railway Transportation[END_REF][START_REF] Agbinya | Design Considerations of MoHotS and Wireless Chain Networks[END_REF][START_REF] Haifeng | Energy Optimal Routing for Long Chain-type Wireless Sensor Networks in Underground Mines[END_REF][START_REF] Yuan | Long Distance Wireless Sensor Networks Applied in Coal Mine[END_REF][START_REF] Zhou | Source-aware Redundant Packet Forwarding Scheme for Emergency Information Delivery in Chain-typed Multihop Wireless Sensor Networks[END_REF][START_REF] Chen | Lifetime Maximization Algorithm for Chain Wireless Sensor Networks[END_REF][START_REF] Leu | Maximum Capacity in Chain-topology Wireless Mesh Networks[END_REF]. This is mostly due to fact that average path length (AP L) in chain-topology is extremely high, which is almost one third of network size as we showed.

In this study, we aimed at compensating this deficiency by presenting an optimization model in which incremental link deployment was considered, with the objective of minimizing AP L on a chain network. For this purpose, we first discovered mathematical expression of the objective, as well as formulated it in the form of Integer Programming (IP). Then, we prepared an experimental setup in order to determine AP Ls of all possible topologies generated by placing an additional link to varying locations on a chain-topology network. Thus, we found optimal solutions that minimize AP L for specific network sizes up to 1000 nodes, and also verified accuracy of our mathematical model. Through the experiments, for each specific network size, we implemented Dijkstra's shortest path algorithm for all pairs, and took average of their lengths in terms of hop count to calculate corresponding AP L values. Afterwards, we derived analytical solution by implementing Linear Regression method on the data obtained experimentally, which allowed us to see asymptotic behaviour of the solutions.

Our analyses showed that the optimization model proposed was able to reduce AP L on chain-topology networks at a rate of between 24.81% and 41.4%, with gradually increasing ratio as network size grows. Moreover, we found that normalized length of the additional link for optimal solution asymptotically approached to 58.6% of network size.

Besides contribution of such an additional link optimally implanted for minimizing the APL, further research is required to improve other performance characteristics of chain-topology networks, such as ensuring load balancing.

Fig. 2 :

 2 Fig. 2: Adding a new enhancement link (i.e. edge) connecting v x and v y

Fig. 3 :

 3 Fig. 3: Experimental Setup for Determining AP L1: for n ← 3 to 1000 do Varying network size 2: Enter Adjacency List of the Graph Defining network topology for all cases 3: function AP L(Graph) 4: Find the minimum AP L among all calculated values at each step of n 5: function APL(G) Determines AP L for G 6: c ← 0 Counter 7: AP L ← 0 8: for all Pairs (vi, vj) in G do 9: function Dijkstra(vi, vj) Runs Dijkstra 10: return Shortest Path (SP) between vi and vj 11: AP L ← (AP L * c + Length(SP )/(c + 1) 12: c ← c + 1 13: return AP L

Figure 4 Fig. 4 :

 44 Figure4shows experimental results in the form of 3-dimensional color mapping when network size equals to 100 nodes. As can be seen in the figure, AP L has the minimum value (i.e. dark blue color) at around x = 21 and y = 80, or equivalently, vice versa. Notice that the red area from left bottom corner to right upper corner represent Path topology, whereas the points both at the left up corner and at the right down corner produce Ring topology.

Fig. 5 :

 5 Fig. 5: Average Path Length (APL) for different topologies as network size grows

Improvement = 100 * 1 =Fig. 6 :

 10016 Fig. 6: Improvement on APL and Normalized Length of Optimal Solutions (NLOS) as network size grows (smoothed)

N L = 100 * |y opt -x opt | n - 1 =

 1 Round(58.6048 * n + 7.48999) n -1 lim n→+∞ N L = 58.6048%

Table 1 :

 1 Experimental Results Obtained by Brute Force Computation

	Network	AP L	AP L	Min AP L	Optimal Solutions
	Size (n)	for P ath	for Ring	(Optimal)	(xopt, yopt)
		Pn	Pn ∪ (v1, vn)	Pn ∪ (vx opt, vy opt)
	3	1.33	1.0	1.0	(x=1, y=3)
	5	2.0	1.5	1.5	(x=1, y=5)
					(x=2, y=8)
	10	3.66	2.77	2.53	(x=3, y=9)
					(x=4, y=16)
	20	7.0	5.26	4.5	(x=5, y=17)
					(x=10, y=40)
	50	17.0	12.75	10.37	(x=11, y=41)
	100	33.66	25.25	20.13	(x=21, y=80)
					(x=41, y=159)
	200	67.0	50.25	39.66	(x=42, y=160)
	500	167.0	125.25	98.24	(x=104, y=397)
					(x=207, y=793)
	1000	333.66	250.25	195.87	(x=208, y=794)

The edges are undirected because of bidirectional transmissions between nodes.

This could be realized via several ways like obtaining a leased line connection from an ISP between the two points of interest, or using a long-range radio link.

The length of a path is measured here in terms of hop count

By all pairs we mean all unordered pairs because the edges are undirected, and for this reason, it is enough to count path lengths in only one direction.