Minimized Cost Gateway Deployment in Cyber-Physical Systems

Abstract

Wireless networks have been widely used in Cyber-Physical System (CPS) for data transmission. A CPS usually contains lots of sensors, and these sensors generate massive data. To make use of these data, we have to collect them through wireless communication. Sensors in a certain CPS do not always adopt same wireless technology, and these sensors formed heterogeneous wireless networks. Communication between different types of wireless networks can only be achieved by utilizing wireless gateways. In this paper, we address the problem of gateway placement for satisfying the bandwidth-requirement of each node by using minimum gateways. This problem can be formulated as a variant of Minimum Geometric Disk Cover problem which has been proved NP-complete. In order to solve our problem, one heuristic gateway placement algorithm and one grid-based heuristic algorithm are proposed. The result of simulation demonstrates that the heuristic algorithm can offer a good solution with big probability.

1. Introduction

Cyber-Physical System (CPS) has great influence on the way we observe and change the world. CPS obtains the information of the physical world through many sensors and impacts the environment by actuators. Data sensed and sampled by sensors usually contains valuable information about the physical world, and its volume is growing big. For better understanding and changing the physical environment, data collection and analysis is of the essence [1]. The knowledge extracted from the data also guides the behavior of actuators in CPS. All the work mentioned above depends on the effective data collection. And data transmission is a significant part of data collection. If we consider sensors as the eyes and actuators as the hands of human, then the data transmission is as important as the neural pathway.

In CPS, data transmission usually takes advantage of wireless communication. For instance, sensors and actuators generally adopt wireless technology to exchange data and cooperate with each other to monitor some area [2, 3] and react when certain event is detected [4, 5]. Different types sensors have been arranged to obtain comprehensive information about the area and send data to process center [6]. Also, actuators in this area need commands from the center or sensors to take proper actions. Due to the rapid development of wireless communication technology, today, CPS with multiwireless technology or heterogeneous sensors coexisting become familiar [7, 8]. Bluetooth, WiFi, Zigbee, and cellular wireless communication technologies have been widely employed by modern wireless devices. These technologies according to their technique features play different role in people's life and in the near future.

Different wireless communication technologies are complementary but also bring challenges. One of the biggest challenges is that these technologies cannot communicate mutually. But the requirement of intercommunication is increasing. Equipping each wireless device with all these technologies is costly and adding new wireless technology to existing terminal is almost impossible. Gateway is a device whose basic functions are data distribution and aggregation [9]. Gateway is designed to communicate with multitechnology wireless network [10]. Under this condition, gateways are indispensable when combining these devices with heterogeneous technologies together.

To achieve better performance in a hybrid wireless network, the locations of gateways must be carefully selected. In wireless mesh network (WMN) [11], gateway placement problem attracts considerable attentions. In WMN, gateway placement application scenario can be described as follows. The mesh nodes are deployed on the roof of houses in a neighborhood, which serve as access points for users inside the houses and along the roads. All these mesh nodes are fixed and form a mesh network. The mesh service provider needs to decide where to place the gateway devices to connect the mesh network to the internet. Since different gateway placement causes different mesh backbone topology and cost, it is important to find optimal gateway placement to minimize the total cost while ensuring the quality of service, for example, coverage.

This application is similar with gateway placement in hybrid wireless network.

Traditional multihop wireless network has several problems in modern wireless network. Take an example of people taking wireless devices, it is hard to believe a person would like to transfer other's packets and let his packets be transferred by others. Taking battery and privacy to one's concern, multihop is not that convenient and credible.

Gateway placement studies in WMN often consider multihop wireless network [12, 13]. And they mainly consider the hybrid network of wired-wireless network [14]; a hybrid network with two different types of wireless technologies is rarely addressed.

In this paper, we consider a scenario that two kinds of wireless nodes equipped with different wireless technologies randomly placed in an area. We focus our work on communication between different kinds of devices. The data transmission among some types of devices can be achieved by many techniques, such as multicast or ad hoc [15, 16]. These two kinds of nodes have the requirement of communication with different types of nodes and the internet. Gateways are used to fulfill their communication needs. For quality of service demands, each node must keep in touch with gateways and obtain a regular bandwidth. A gateway has limited capacity of providing bandwidth to the nodes connected to it. All the nodes in this area must be covered by a gateway. We investigate where to place the gateways can minimize the number of gateways placed.

The contributions of our work are as follows.

We consider the minimizing gateway placement problem in a hybrid wireless network with two different kinds of wireless communication technologies.

We propose two heuristic algorithms to address the problem.

Finally, we make simulations to evaluate our method. And the results of simulations demonstrate that our method is effective.

The paper is organized as follows. We discuss the related work in Section 2. The network models and some assumptions are given in Section 3. Our problem definition is in Section 4. In Section 5, we propose our two algorithms. Simulation is in Section 6. Conclusions and future work are given in Section 7.

2. Related Work

Bejerano [17] studied gateway placement in multihop wireless networks where network nodes were partitioned into minimal number of disjoint clusters that satisfied throughput and delay constraints. Various gateway or backbone nodes placement algorithms were proposed for WMNs [18, 19]. Some work has been done for relay device placement [20] and problems in sensors forming backbone situation [21]. However, all the above investigation focused on network connectivity of WMNs or WSNs by selecting a minimum number of fixed positions.

The capacity of hybrid ad hoc networks was investigated in [22–24]. All the above throughput results have been obtained as asymptotic value by assuming that the size of the network goes to infinity. In practice the above assumption cannot be satisfied.

Le and Nguyen [25] studied the problem of optimizing gateway placement for throughput in WMNs. In [25], a step by step updated scheme was proposed. Router node placement in a dynamic network scenario has been studied in [26]. They have proposed a particle swarm optimization approach to determine the dynamic placement of routers to maximize network connectivity and client coverage. Reference [27] investigated a router node placement problem considering service priority of client node and proposed a simulated annealing approach to solve it. Population size of client node affects the performance of gateway placement method. Reference [28] investigated the effect of population size for WMN genetic algorithm. This research is outstanding. However, the problem of gateway placement which aims to cover all client nodes in hybrid wireless network remains unstudied.

Coverage problem has been well studied in [29], which uses unit disks to cover points in an area. Their method is efficient under simple network model. However, in hybrid wireless network, many client nodes are uncovered when adopting this method.

3. Model and Assumption

There are three kinds of nodes in our network model. One of them is gateway nodes represented by $G = {g_{1}, g_{2}, \dots, g_{k}}$ . And the others are client nodes $A = {a_{1}, a_{2}, \dots, a_{n}}$ and client nodes $B = {b_{1}, b_{2}, \dots, b_{m}}$ . A and B require communicating mutually and having access to the internet. These communication demands are fulfilled by making client nodes connected with gateways. Gateways are wired connected with each other and have access to external network. Every node $a_{i}$ or $b_{i}$ is directly connected with the designated gateway node.

Gateway Node Model. The network bandwidth of each single gateway $g_{i}$ is $W_{g a}$ bps for nodes A and $W_{g b}$ bps for nodes B. And every gateway node $g_{i}$ can offer $M_{a}$ orthogonal channels for nodes A and $M_{b}$ orthogonal channels for nodes B. All the gateways nodes share the same channels.

Client Node Model. Every node of A and B requires bandwidth of $W_{a}$ bps and $W_{b}$ bps, respectively, and they need to keep the connection with its associated gateway node. Communication between two types of nodes can only be realized by connecting them to gateway nodes. As mentioned above, each node $a_{i}$ or $b_{i}$ has the ability to utilize $M_{a}$ or $M_{b}$ orthogonal channels, and its transmission range is $R_{a}$ or $R_{b}$ , respectively. In our paper, we set $R_{a} ⩾ R_{b}$ .

Interference Model. Signals from different types of nodes will not interfere mutually. And signal from the same kind of nodes will generate interference only when they are in the same channel. Every node has an interference range. For convenience, let interference range be equal to its transmission range. So when $‖a_{i} - a_{j}‖ < R_{a}$ ( $‖b_{i} - b_{j}‖ < R_{b}$ ) and the two nodes are using the same channel, interference will be caused.

4. Problem Definition

Consider an L meters by W meters area in which nodes $A = {a_{1}, a_{2}, \dots, a_{n}}$ and nodes $B = {b_{1}, b_{2}, \dots, b_{m}}$ have been randomly placed. Bandwidth for communication with gateways required by each $a_{i}$ or $b_{i}$ is $W_{a}$ bps or $W_{b}$ bps. All nodes A take advantage of $M_{a}$ orthogonal channels to communicate with gateways and nodes B use $M_{b}$ conflict-free channels for communication. Every gateway $g_{i}$ can offer $W_{g a}$ ( $W_{g b}$ ) bps for all the nodes A (B) that connected to $g_{i}$ . Our object is to select positions to place gateways $G = {g_{1}, g_{2}, \dots, g_{k}}$ in order to minimize k and guarantee that all the nodes obtain their required bandwidths.

Our problem can be formulated as follows.

Given two sets in the Euclidean plane, set $A = {a_{1}, a_{2}, \dots, a_{n}}$ of n points, set $B = {b_{1}, b_{2}, \dots, b_{m}}$ of m points. Every point has a location ( $x_{i}$ , $y_{i}$ ). We wish to select locations to place a minimum set $G = {g_{1}, g_{2}, \dots, g_{k}}$ of k points to cover set A and set B, $a_{i}$ or $b_{i}$ is covered by $g_{i}$ means $‖a_{i} - g_{i}‖ \leq R_{a}$ or $‖b_{i} - g_{i}‖ \leq R_{b}$ , and the number of points of A or B covered by $g_{i}$ must be less than $W_{g a}$ / $W_{a}$ or $W_{g b}$ / $W_{b}$ .

There is an additional restriction of node density on the plane. Because the number of orthogonal channel is limited, when the density of nodes is more than a threshold, the signal of each other node will interfere mutually. The threshold does not have to be the number of physical channels. There are many techniques to enhance the ability of concurrence wireless communication, such as TDMA or CDMA. These technologies increase the number of actual available channels. We call these channels orthogonal channels. So the threshold can be demonstrated as follows. The number of nodes is less than $M_{a}$ or $M_{b}$ in any circle with a node as center and transmission radius as radius. This can be proven easily by using pigeonhole principle.

This problem can be seen as a variant of Minimum Geometric Disk Cover problem which is NP-complete [30]. The Minimum Geometric Disk Cover problem is to find a set of unit disks of minimum cardinality whose union covers a given set of points in the plane, and the disk centers are located at any position in the plane [29].

Obviously our problem is not easier than the Minimum Geometric Disk Cover problem. So at least, our problem is NP-complete.

5. Algorithms

In this section, we propose two methods to determine the locations of gateways.

5.1. Algorithm 1: Farthest Node First Cover (FNFC)

To deal with the asymmetry of nodes distribution, we consider finding an origin of our gateway placement strategy and a direction to move on. The origin in this strategy is one of the farthest two nodes on the plane. And we conduct the gateway placement from the origin to the other one which we call it destination point (DP). In the process of gateway placement, DP is fixed. The strategy will iteratively find the node whose distance to the DP is the longest. We denote the farthest node as start point (SP).

Algorithm 1: Farthest node first cover.

Input: Node set $N = {n_{i} = (x_{i}, y_{i}) | 0 ⩽ i ⩽ n + m}$ with transmission radius $R_{i}$ on Plane P. $N = A \cup B$ , $A = {a_{i} = (x_{i}, y_{i}) | 0 ⩽ i ⩽ n}$

and $B = {b_{i} = (x_{i}, y_{i}) | 0 ⩽ i ⩽ m}$ . $R_{i}$ is $R_{a}$ when $n_{i} \in A$ and $R_{b}$ when $n_{i} \in B$ .

Bandwidth requirement $W_{a}$ and $W_{b}$ for $a_{i}$ and $b_{i}$ , gateway bandwidth $W_{g a}$ and $W_{g b}$ for $a_{i}$ and $b_{i}$

Output: $G = {g_{i} = (x_{i}, y_{i}) | 0 ⩽ i ⩽ k}$

(1) Calculate the distances between any two nodes

(2) Find the farthest two nodes $n_{s}$ and $n_{d}$

(3) Let $SP = n_{s}$ , and $DP = n_{d}$

(4) For all $n_{i}$ , calculate $| | n_{i} - n_{s} | |$ ; if $| | n_{i} - n_{s} | | ⩽ R_{i} + R_{s}$ , add $n_{i}$ to point set Q.

(5) Calculate the intersections of circle with $n_{s}$ as center and circle with each $q_{i} \in Q$ as center, with radius $R_{s}$ and $R_{q i}$ .

If the intersections do not exist, go to (6); If there is only one intersection $c_{i 1}$ ( $x_{i 1}$ , $y_{i 1}$ ), add $c_{i 1}$ to point set P;

If there are two intersections $c_{i 1}$ ( $x_{i 1}$ , $y_{i 1}$ ) and $c_{i 2} (x_{i 2}, y_{i 2})$ , add the one whose distance to $n_{d}$ is shorter to point set P.

(6) If $n_{s}$ and $q_{i}$ belong to different node set and $| | n_{s} - q_{i} | | < R_{a} - R_{b}$ , let $R_{b}$ be their radius, return to (5).

(7) For all nodes in P, calculate $| | p_{i} - n_{d} | |$ ; Let $g_{i} = p_{m}$ , where $| | p_{m} - n_{d} | | = \max {| | p_{i} - n_{d} | |}$

(8) Add $n_{i}$ , where $| | n_{i} - g_{i} | | ⩽ R_{i}$ , to node set $C_{A}$ when $n_{i} \in A$ or $C_{B}$ when $n_{i} \in B$ .

(9) Sort $C_{A}$ and $C_{B}$ order by $| | n_{i} - n_{d} | |$ . Keep the last $W_{g a} / W_{a}$ and $W_{g b} / W_{b}$ points in $C_{A}$ and $C_{B}$ , remove the other.

(10) Mark nodes in $C_{A}$ and $C_{B}$ .

(11) Check each $n_{i}$ ; If all nodes are marked, algorithm terminated; Else go to (12)

(12) Choose the farthest node to DP as new SP from the unmarked nodes; Go to (3).

After SP has been found, we calculate the intersection of two circles. One takes SP as its center, and the other one will take each of the nodes adjacent to SP as its center. Their radiuses are the transmission radiuses of the central nodes. If the two circles have two intersections, the one closer to DP will be reserved. And if there is only one intersection, it will be reserved. In a few cases that the distance between two centers is shorter than the discrepancy of their radiuses, there will be no intersection. In this case, we replace the longer radius with shorter one and calculate their intersection again. In all the intersections we reserved, the one whose distance to the segment (DP, SP) is the longest will be selected to arrange a gateway. In accordance with the order of distance to SP, we mark the nodes which can be covered by the gateway. The algorithm repeats the above process until all nodes are marked.

Take Figure 1 as example. There are two kinds of nodes in this area, and they are indicated as blue points or red points. Their transmission radius is $R_{a}$ or $R_{b}$ . Firstly, the algorithm finds out the farthest two points in this area. As shown in the figure, they are point D and point S. We take S as start point and D as destination point. Then we make circles with S and its adjacent points as center and their transmission radiuses as radius. Circles with adjacent points as center will intersect the circle with S as center. If the two circles have two intersections, we keep the one with shorter distance to D. Among all the kept intersections, we select point O to arrange a gateway, because O is the nearest point to segment $D S .$ In the next step, depending on their types, nodes in the solid circle will be marked. If the number of nodes A (B) in the circle is more than $W_{g a}$ / $W_{a}$ ( $W_{g b}$ / $W_{b}$ ), we mark the nodes whose distance to point D is farther. And then the algorithm will take the farthest point to point D among the unmarked nodes as new start point. The algorithm repeats this process until all nodes have been marked. The time complexity of FNFC is $O ({(m + n)}^{2})$ , $n = | A |$ and $m = | B |$ .

Figure 1

Demonstration of FNFC: D is DP; S is SP; and O is the position to place gateway.

5.2. Algorithm 2: Grid-Based Heuristic Cover (GBHC)

Here we propose a more intuitional method to arrange gateways. Also, in some instances, it is unacceptable to place gateway at arbitrary location; for example, the wiring system of a build is usually prefixed, and the FNFC algorithm is inappropriate. And we proposed the second method to choose some locations based on a grid to arrange gateways. Since the grid is predefined, these locations can be reserved for gateways. We divide the area into grids with diagonal length $R_{b}$ , so when we place gateways on the intersections, the whole area can be covered and no node will be missed. GBHC will place a gateway on the intersection where it can cover maximum nodes and mark these covered nodes. GBHC repeats previous process till all nodes have been covered. Figure 2 is an example of how to select an intersection to place gateway. This gateway placement method is much easier to be realized than FNFC. So it is a reasonable choice at a quick-deployment situation. The time complexity is $O (k {(n + m)}^{2})$ ; k is the number of grids.

Algorithm 2: Grid-Based Heuristic Cover.

Input: Node set $N = {n_{i} = (x_{i}, y_{i}) | 0 ⩽ i ⩽ n + m}$ with transmission radius $R_{i}$ on Plane P. $N = A \cup B$ , $A = {a_{i} = (x_{i}, y_{i}) | 0 ⩽ i ⩽ n}$

and $B = {b_{i} = (x_{i}, y_{i}) | 0 ⩽ i ⩽ m}$ . $R_{i}$ is $R_{a}$ when $n_{i} \in A$ and $R_{b}$ when $n_{i} \in B$ . Bandwidth requirement $W_{a}$ and $W_{b}$ for $a_{i}$ and $b_{i}$ ,

gateway bandwidth $W_{g a}$ and $W_{g b}$ for $a_{i}$ and $b_{i}$

Output: $G = {g_{i} = (x_{i}, y_{i}) | 0 ⩽ i ⩽ k}$

(1) Calculate the side length of the grid, $l = \sqrt{2} \cdot R_{b} / 2$

(2) Divide the area into grids

(3) Count the number of nodes in each grid

(4) For every grid intersection, calculate the number of uncovered nodes in its nearby four grids. The intersection with max number

is marked as $P (p_{x}, p_{y})$

(5) Add $g_{i} = P$ to G.

(6) For all nodes in this area, calculate its distance to $g_{i}$ , and add $n_{i}$ , which $| | n_{i} - g_{i} | | ⩽ R_{i}$ , to node set $C_{A}$ when $n_{i} \in A$ or $C_{B}$ when

$n_{i} \in B$ .

(7) Sort the nodes in $C_{A}$ and $C_{B}$ order by $R_{i}$ . Keep the last $W_{g a} / W_{a}$ and $W_{g b} / W_{b}$ nodes in $C_{A}$ and $C_{B}$ , remove the other

(8) Mark nodes in $C_{A}$ and $C_{B}$ as covered.

(9) Check each $n_{i}$ ; If all nodes have been marked, algorithm terminated; Else go to (3).

Figure 2

Demonstration of GBHC: O is the intersection to place gateway.

5.3. Discussion

The consideration of FNFC is similar to the greedy solution of line cover problem. The problem in this paper is 2-dimentional, so the start of FNFC is to determine a direction. This is the reason why we need to find two farthest nodes in the area. The procedure of FNFC algorithm is operable. The idea is that we rotate gateway O around node SP on a circle whose center is SP and radius is transmission radius. In this process, nodes may enter O's coverage. When one of these nodes is going to leave O's coverage, we stop rotating and place O at that position. This method has been proved effective by our simulation. GBHC is easy to understand and implement. Though its solution contains more gateways, it is stable. In some cases, when the density of nodes is high, two or more gateways will be arranged at some point. In that situation, the whole proportion covered by gateways using GBHC will be smaller than it could be. This may lead to a higher possibility that we have to add a new gateway if a new node have been added to this area.

Figure 3 is an example of the gateway placement given by FNFC.

Figure 3

Gateway placement given by FNFC.

6. Simulation

In this section, we conduct several simulations to study the performance of FNFC and GBHC. We compare the solutions of FNFC and GBHC under different conditions, and the results show that FNFC will give better solutions in most cases.

6.1. Simulation Setup

We consider an area of 200 meters by 200 meters. Nodes A and nodes B have been placed in this region in two distributions. The first situation is that all the nodes are randomly arranged in the whole area, and the second is that eighty percent of nodes are randomly placed in two small parts of the area, and the rest are randomly placed in the whole area. $R_{a}$ is set to 30 meters and $R_{b}$ is set to 25 meters. And we set $W_{g a}$ / $W_{a}$ = 20, $W_{g b}$ / $W_{b}$ = 15, $M_{a}$ = 25, and $M_{b}$ = 20, if there is no additional statement. These settings are mainly based on the technical parameters of WIFI and are used to test the performances of proposed algorithms. We conducted the simulation on a PC with i7 4770k CPU, 16 GB memory, and 256 GB SSD.

6.2. Results Discussion

In the first kind of simulation, we increase the number of nodes A and nodes B from 100 to 1000, and the quantity of nodes A equals that of nodes B. As shown by Figure 4(a), gateways generated by FNFC are much fewer than GBHC. And the difference becomes smaller when nodes number increased. Also, the numbers of gateways generated by FNFC and GBHC both increase along with the growth number of nodes. The velocity of increase slows down when the number of nodes becomes large. This is because as the number of nodes increases, the gateways generated by both algorithms have almost covered nearly the whole area, and in this case nodes added to the region have great probability to fall in the scopes of gateways already there. It is also the reason why the numbers of gateways generated by two algorithms become closer. Figure 4(b) has a similar tendency with Figure 4(a), but the number of gateways used is much smaller. This phenomenon is quite reasonable, for nodes concentrated in small regions are easy to be covered by few gateways.

Figure 4

Number of gateways generated by FNFC and GBHC.

Figure 5(a) shows the nodes covered rate when we adopting random gateway placement method. We randomly place the same number of gateways generated by GBHC into the area. For each number of nodes, we conduct one hundred times random gateway placement and calculate the average value of cover rate. When the number of nodes is small, random placement misses a large number of nodes. Such situation becomes better when the number of nodes increased, since we have placed more gateways and larger area will be covered. But random placement rarely covers more than ninety percent of nodes. Same situation has been observed in Figure 5(b), but in that distribution, when the number of gateways is relatively smaller, randomly placed gateways miss much more nodes. This is because when nodes are concentrated, randomly placed gateways will miss more nodes by missing the nodes-intensive area.

Figure 5

Nodes covered and uncovered rate in random gateway placement.

In the second kind of simulation, we fix the number of nodes, 150 nodes A and 150 nodes B, and increase the transmission radiuses, $R_{a}$ from 15 meters to 60 meters and $R_{b}$ from 10 meters to 55 meters. The results are shown in Figure 6.

Figure 6

Number of gateways generated by FNFC and GBHC.

When the radius is very small, the difference between results of two algorithms is significant. Gateways generated by FNFC are as few as sixty percent of GBHC in Figure 6(a). With radius rising, the numbers of gateways generated by two algorithms become similar. The reason is similar with the first kind simulation. As radius grows, the arranged gateways will cover most area of the region. Thus the position of each gateway will make less difference. These results of randomly placement can also be interpreted, as shown in Figure 7(a).

Figure 7

Nodes covered and uncovered rate in random gateway placement.

In the situation of nodes placed in two small parts of the area, fewer gateways have been used to cover all the nodes, as shown by Figure 6(b). The reason is similar with the first kind simulation. And random gateways placement also follow the same condition of the first kind simulation, which is shown in Figure 7(b).

In the third simulation, the total number of nodes A and nodes B is set to 240, and we change the ratio between nodes A and nodes B from : B = 0 : 10 to A : B = 10 : 0. We conduct such simulation to see the influence of the quantity of different nodes on the performance of the algorithms. The results are shown in Figure 8.

Figure 8

Gateways generated by two algorithms with different ratio between A and B.

The number of gateways is downtrend, because $W_{g a}$ / $W_{a}$ is bigger than $W_{g b}$ / $W_{b}$ . That means one gateway is able to cover more nodes A than nodes B. When number of nodes B declined and number of nodes A increased, fewer gateways are required.

In the fourth kind of simulation, we set the number of nodes A as 150 and so does the number of nodes B. We conduct twenty times of each algorithm with different random distributions of nodes in the area. Figure 9 shows the results. From Figure 9, we find that distribution has obvious influence on the results of two algorithms. With one of these nodes distribution, GBHC can achieve nearly the same performance of FNFC. But in most of the cases, FNFC is much better than GBHC.

Figure 9

Results of two algorithms with different nodes distribution.

We compare FNFC with the method proposed by [29], named discrete unit disk cover (DUDC). This method chooses minimum disk to cover all the nodes which is similar to our problem. We use the same setting of the first simulation with random distribution. The radius is set to 25 meters. We run DUDC based on our results. From Figure 10 we can see although DUDC can reduce the number of gateways, about 5 to 10 percent, it leads to many nodes becoming uncovered, about 10 to 20 percent. This is because DUDC only consider how to cover the nodes without taking communication requirement into its account.

Figure 10

Number of gateways reduced by DUDC and percentage of uncovered nodes.

7. Conclusion and Future Work

In this paper, we investigated the optimizing gateway placement problem in CPS. We proposed two algorithms to address the problem. The effectiveness of the algorithms has been evaluated by our simulations. Our method can offer a good solution containing a small number of gateways. Actually, the situation will be more complicated, and much more work is needed to be done. According to the discussion in the paper, we only consider two types of client nodes in this paper, and the distribution of nodes is constant and known. There are two questions needed to be solved in the future. The first question is how to determine gateway locations if there are multiple types of client nodes. The second is how solve the problem of gateway placement, when the nodes' positions are unknown or changing overtime.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

This work was partially supported by the National Natural Science Foundation of China (NSFC) under Grants nos. 61190115 and 61033015 and the National Science Foundation Distinguished Young Scholars of China under Grant no. 61300225.

References

Cheng

Gao

Cai

Approximate physical world reconstruction algorithms in sensor networks

IEEE Transactions on Parallel and Distributed Systems 2014 25 12 3099 3110

10.1109/tpds.2013.2297121

Cheng

Thaeler

Xue

Chen

TPS: a time-based positioning scheme for outdoor wireless sensor networks

Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM ‘04)

2004

2685 2696

Cheng

Cai

Curve query processing in wireless sensor networks

IEEE Transactions on Vehicular Technology 2014 PP 99 1

10.1109/tvt.2014.2375330

Ding

Chen

Xing

Cheng

Localized fault-tolerant event boundary detection in sensor networks

Proceedings of 24th Annual Joint Conference of the IEEE Computer and Communications Societies(INFOCOM '05)

March 2005

902 913

10.1109/INFCOM.2005.1498320

Guo

Cai

Minimum-latency aggregation scheduling in wireless sensor network

Journal of Combinatorial Optimization 2014

2-s2.0-84901731672

10.1007/s10878-014-9748-7

Cai

Cheng

Wang

Approximate aggregation for tracking quantiles in wireless sensor networks

Proceedings of the 8th Annual International Conference on Combinatorial Optimization and Applications (COCOA ‘14)

2014

161 172

10.1007/978-3-319-12691-3_13

Becchetti

Priscoli

F. D.

Inzerilli

Mähönen

Muñoz

Enhancing IP service provision over heterogeneous wireless networks: a path toward 4G

IEEE Communications Magazine 2001 39 8 74 81

10.1109/35.940039

2-s2.0-0035416626

Gao

Cai

Gao

Composite event coverage in wireless sensor networks with heterogeneous sensors

Proceedings of the 34rd Annual IEEE International Conference on Computer Communications (INFOCOM '15)

April 2015

Hong Kong, China

Shen

C.-C.

Srisathapornphat

Jaikaeo

Sensor information networking architecture and applications

IEEE Personal Communications 2001 8 4 52 59

10.1109/98.944004

2-s2.0-0035428428

10.

Hwang

K.-I.

Park

Eom

D.-S.

A design and implementation of wireless sensor gateway for efficient querying and managing through world wide web

IEEE Transactions on Consumer Electronics 2003 49 4 1090 1097

10.1109/tce.2003.1261201

2-s2.0-1542542758

11.

Akyildiz

I. F.

Wang

Wireless mesh networks: a survey

Computer Networks 2005 47 4 445 487

2-s2.0-13844296355

10.1016/j.comnet.2004.12.001

12.

Wang

X.-Y.

Nusairat

Gateway placement for throughput optimization in wireless mesh networks

Mobile Networks and Applications 2008 13 1-2 198 211

10.1007/s11036-008-0034-8

2-s2.0-48449097274

13.

Chandra

Qiu

Jain

Mahdian

Optimizing the placement of Internet TAPs in wireless neighborhood networks

Proceedings of the 12th IEEE International Conference on Network Protocols (ICNP ‘04)

October 2004

Berlin, Germany

271 282

2-s2.0-17744379156

10.1109/icnp.2004.1348117

14.

Muthaiah

S. N.

Rosenberg

C. P.

Single gateway placement in wireless mesh networks

Proceedings of the 8th International Symposium on Computer Networks (ISCN ‘08)

June 2008

5 10

2-s2.0-58149137001

15.

Cai

Lin

Xue

Improved approximation algorithms for the capacitated multicast routing problem

Computing and Combinatorics 2005 3595

Berlin, Germany

Springer

136 145 Lecture Notes in Computer Science

10.1007/11533719_16

MR2190278

16.

Cai

Goebel

Lin

Size-constrained tree partitioning: approximating the multicast

k

-tree routing problem

Theoretical Computer Science 2011 412 3 240 245

10.1016/j.tcs.2009.05.031

MR2789646

2-s2.0-78650610629

17.

Bejerano

Efficient integration of multi-hop wireless and wired networks with QoS constraints

Proceedings of the 8th Annual International Conference on Mobile Computing and Networking

September 2002

215 226

2-s2.0-0036963533

18.

Srinivas

Zussman

Modiano

Mobile backbone networks—construction and maintenance

Proceedings of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC ‘06)

May 2006

166 177

2-s2.0-33748037385

19.

Wang

Xie

Cai

Agrawal

D. P.

Efficient mesh router placement in wireless mesh networks

Proceedings of the IEEE Internatonal Conference on Mobile Adhoc and Sensor Systems (MASS ‘07)

October 2007

1 9

10.1109/mobhoc.2007.4428616

2-s2.0-50249102282

20.

Cheng

D.-Z.

Wang

Relay sensor placement in wireless sensor networks

Wireless Networks 2008 14 3 347 355

10.1007/s11276-006-0724-8

2-s2.0-43949136957

21.

Boukerche

Cheng

Linus

Energy-aware data-centric routing in microsensor networks

Proceedings of the 6th ACM international workshop on modeling analysis and simulation of wireless and mobile systems (MSWIM ‘03)

September 2003

42 49

2-s2.0-1542286866

22.

Liu

Towsley

On the capacity of hybrid wireless networks

Proceedings of the 22nd Annual Joint Conference on the IEEE Computer and Communications Societies (Infocom ‘03)

April 2003

1543 1552

2-s2.0-0042014447

23.

Kozat

U. C.

Tassiulas

Throughput capacity of random ad hoc networks with infrastructure support

Proceedings of the 9th Annual International Conference on Mobile Computing and Networking (MobiCom ‘03)

September 2003

55 65

2-s2.0-1542269187

24.

Zemlianov

de Veciana

Capacity of ad hoc wireless networks with infrastructure support

IEEE Journal on Selected Areas in Communications 2005 23 3 657 667

10.1109/jsac.2004.842536

2-s2.0-15244352493

25.

Nguyen

A new evolutionary approach for gateway placement in wireless mesh networks

International Journal of Computer Networks and Wireless Communications 2012 2 5 550 555

26.

Lin

C.-C.

Dynamic router node placement in wireless mesh networks: a PSO approach with constriction coefficient and its convergence analysis

Information Sciences 2013 232 294 308

10.1016/j.ins.2012.12.023

MR3036655

2-s2.0-84875452659

27.

Lin

C.-C.

Shu

Deng

D.-J.

Router node placement with service priority in wireless mesh networks using simulated annealing with momentum terms

IEEE Systems Journal 2014

10.1109/jsyst.2014.2341033

28.

Oda

Barolli

Spaho

Barolli

Xhafa

Younas

Effects of population size for location-aware node placement in WMNs: evaluation by a genetic algorithm—based approach

Personal and Ubiquitous Computing 2014 18 2 261 269

10.1007/s00779-013-0643-5

2-s2.0-84897671461

29.

Das

G. K.

Fraser

Lóopez-Ortiz

Nickerson

B. G.

On the discrete unit disk cover problem

International Journal of Computational Geometry and Applications 2012 22 5 407 419

10.1142/S0218195912500094

2-s2.0-84874076899

30.

Fowler

R. J.

Paterson

M. S.

Tanimoto

S. L.

Optimal packing and covering in the plane are NP-complete

Information Processing Letters 1981 12 3 133 137

10.1016/0020-0190(81)90111-3

MR618923

2-s2.0-0019573312