AN EFFICIENT RELAY PLACEMENT ALGORITHM FOR CONTENT-CENTRIC WMNS 265
Table I. Comparison with related works.
Methods Network type Designs Traffic type
References [17], [20] FiWi networks ONU placement Peer-to-peer communications
References [25], [26] Traditional WMNs Gateway placement Internet access traffic
Our scheme Content-Centric WMNs Communication relay Peer-to-peer communications,
placement and Internet access traffic
content allocation and content delivery
FiWi, fiber-wireless; ONU, optical network unit; WMN, wireless mesh network.
The content allocation scheme has been studied in several existing works. Leong et al. showed that
the problem to find the optimal allocation on subset of storage nodes that maximizes the probability
of successful recovery by the data collector, is a complex non-convex optimization problem[28].
They also demonstrated that a symmetric data assignment is an optimal assignment when the size of
the storage node set tends to infinity[29]. When the size of the storage node set is small, an optimal
allocation strategy can be found to minimize the total storage budget under the requirement that the
recovery probability[30] is exactly 1.
Clearly, although the relay placement problem in WMNs and the content allocation problem in
content distribution network have been investigated, there has been no previous work that addresses
both of them in content-centric wireless mesh networks. In this paper, we will tackle this channeling
problem. To the best of the authors’ knowledge, this is the first study on the optimal relay placement
for content-centric WMN. We show the differences between our work and related works in Table I.
The rest of the paper is organized as follows. We first study the communication relay place-
ment and content storage problem in Section 2, which aims to maximize the network throughput by
placing the communication relays and storing contents in storage nodes. We also introduce system
models, important notations, and formulate the problem as an integer linear programming in the
same section. We then propose a linear programming (LP) in Section 3 to calculate the achievable
network throughput when the positions of communication relays are fixed. We then develop an effi-
cient near-optimal approximation algorithm based on LP-relaxation in Section 4. Simulation results
are presented in Section 5. And finally, we conclude the paper in Section 6.
2. PROBLEM FORMULATION
In this section, we will define the communication relay placement problem and content allocation
problem in content-centric WMNs. Specifically, we first introduce the network model and give the
definition of the communication relay placement problem studied in this paper. We then give the
notations to be used in this paper.
2.1. The Network Model
The WMN consists of a set of wireless mesh routers, which are distributed over a planar geographic
area. Each wireless mesh router has a transmission range constraint, that is, it can only directly
communicate with the wireless mesh routers within its transmission range. Communication relays
are used to improve the network throughput and extend communication coverage. Communication
relays are multichannel nodes with possibly multiple interfaces and interconnected through high
bandwidth wireless channels, which help wireless mesh routers in the WMN to relay their traffics.
We assume that the placement of communication relays can be controlled to maximize the network
throughput. There exists a station severing as gateway to relay wireless clients’ traffics to external
network, such as the Internet, and providing communication relay management.
Moreover, in the content-centric WMN, a subset of mesh routers (called as storage nodes) can
be exploited to store content in order to increase the network throughput. Each storage node has a
storage capacity constraint, which means the amount of content stored on the node cannot exceed
its storage capacity. Each storage node may store a set of coded blocks (coded by network coding
Copyright © 2013 John Wiley & Sons, Ltd. Int. J. Commun. Syst. 2015; 28:262–280
DOI: 10.1002/dac