Jin Wang and Kejie Lu Mobile relay placement in hybrid MANETs with secure network coding
coding capability. In the literature, the relay placement
problem has been investigated in a few existing work.
In [16], the authors proposed an analytical model to pre-
dict both uplink and downlink connectivity probabilities
in infrastructure-based vehicular networks (consisting of a
group of basestations along the road). In [17], the authors
investigated the number of mobile relays needed to main-
tain a certain level of connectivity in a mobile network.
Given the node density of the mobile network, they also
quantified the relationship between network connectivity
and the number of gateway nodes. In [22], the authors
investigated the relay placement problem to achieve fault
tolerance in the hybrid MANET. In [23], the authors stud-
ied the cost performance trade-offs of adding supporting
infrastructure, including basestations, meshes, and relays,
to improve the performance of vehicular networks. In [24],
the authors showed that unmanned air vehicles can provide
important communication advantages to ground-based
wireless ad hoc networks. The location and movement of
unmanned air vehicles are optimized to improve the con-
nectivity of a wireless network in [24]. Whereas in this
paper, we optimize the mobile relay placement in terms of
maximizing the network throughput. Moreover, we com-
pare the network throughput obtained in hybrid MANETs
with optimal mobile relays’ placement to that with random
mobile relays’ placement. For the secure communication,
secure network coding is a promising method to pro-
vide content confidentiality. In [20,21], we studied the
secure network coding scheme to provide weakly secu-
rity and information theocratical security defending against
the intermediate nodes eavesdropping on the flows pass-
ing through itself to acquire as much information. In this
paper, we optimize the mobile relay placement to maxi-
mizing the secure network throughput when using secure
network coding.
The rest of the paper is organized as follows. We
first show network models and notations in Section 2.
For the case that mobile relays have been installed at
fixed positions, we then model the mobile relay place-
ment problem as a linear programming (LP) in Section 3
for calculating the achievable secure network through-
put. In Section 4, we study the mobile relay place-
ment problem, which aims to place the mobile relays
to maximize the secure network throughput, and formu-
late the problem as an integer LP to optimally solve
the problem studied in this paper. We also develop an
efficient near-optimal approximation algorithm based on
LP relaxation. We conduct extensive simulation experi-
ments in Section 5. And finally, we conclude the paper
in Section 6.
2. PROBLEM FORMULATION
In this section, we will define the mobile relay placement
problem in hybrid MANETs with secure network coding
capability. Specifically, we first introduce the network
model. We then give the important parameters decision
variables to be used in this paper.
2.1. The network model
The MANET consists of a set of mobile devices. Each
mobile device only can directly communicate with the
mobile nodes within its transmission range. In the hybrid
MANET, mobile relays can be used to improve both
the network throughput and security. Mobile relays are
equipped with possibly multiple interfaces and conse-
quently have multi-channels. They are also interconnected
by high bandwidth wireless channels, which compose a
high bandwidth mobile relay subnetwork. The high band-
width mobile relay subnetwork can help mobile nodes in
the MANET to relay their traffics. We assume the topol-
ogy of the MANET is not changed for a certain duration
and is known by a mobile relay management entity. We
also assume that the movement of mobile relays can be
controlled to maximize the secure network throughput.
We also assume that there exists a gateway station in the
hybrid MANET, which can provide mobile relay manage-
ment and relay mobile nodes’ traffics to external network
(e.g., Internet).
We modeled a hybrid MANET as a directed graph
G =(N, E) where N consists of a gateway denoted as
node g, a set of potential installation positions for mobile
relays’ deployment denoted as M
p
and a set of mobile
nodes denoted as M
N
. Each mobile node is equipped
with one radio working on the same channel with channel
capacity c. We want to find K mobile relays’ positions to
install them denoted as M
r
, M
r
M
p
.
We suppose that all mobile nodes have the same trans-
mission range. The transmission range and the interference
range are denoted as R
T
and R
I
, respectively, where R
I
=
ˇR
T
, ˇ 1. There are wireless links between any two
mobile nodes if they are in each other’s transmission range.
Mobile relays can communicate with each other through
the high bandwidth mobile relay subnetwork through com-
munication technologies such as optical communication
[25–27], cognitive radio [28,29], and so on. Therefore, the
bandwidth of the wireless channels between the mobile
relays and between the mobile relays and the gateway is
much larger than that between mobile nodes; we model that
there is a direct communication between any two mobile
relays and between each mobile relay and the gateway with
a capacity C (much larger than c). Because each mobile
relay communicates with the gateway and other mobile
relay using different channels, the interference set of such
links is set to be ;.
A secure network coding scheme is applied for each
traffic flow for providing different secure requirements
at each source and destination, whereas the intermedi-
ate mobile nodes only store and forward the data packets
[20,21]. The source transmitted coded data packet instead
of original data packet to the destination through the public
MANET such that each intermediate wireless mobile node
cannot decode and acquire the original data if the num-
Security Comm. Networks
(2013) © 2013 John Wiley & Sons, Ltd.
DOI: 10.1002/sec