This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
into Q1 23: ENDIF
Fig. 4. DBR packet forwarding algorithm
buffer Q2. If the packet is found in Q2, it is dropped as it has been forwarded recently. Otherwise, the node calculates the sending time for the packet based on the current system time and the holding time and inserts the packet into the priority queue Q1. Note that if the packet is already in Q1, the sending time is updated to the earlier time. Later, the packets enqueued in Q1 will be sent out according to their scheduled sending times.
4
Performance Evaluation
In this section, we evaluate the performance of DBR and compare it with the Vector Based Forwarding (VBF) protocol[17]. 4.1
Simulation Settings
All simulations are performed using the Network Simulator (ns2) [12] with an underwater sensor network simulation package (called Aqua-Sim) extension. In our simulations, sensor nodes are randomly deployed in a 500m × 500m × 500m
DBR: Depth-Based Routing for Underwater Sensor Networks
81
3-D area. Multiple sinks are randomly deployed at the water surface. While we assume that the sinks are stationary once deployed, the sensor nodes follow the random-walk mobility pattern. Each sensor node randomly selects a direction and moves to the new position with a random speed between the minimal speed and maximal speed, which are 1 m/s and 5 m/s respectively unless specified otherwise. Although the source node can be anywhere in the network, for easy simulations, we place it at a random position at the bottom layer in our experiment. The data generating rate at the source node is one packet per second, with a packet size of 50 bytes. The communication parameters are similar to those on a commercial acoustic modem, LinkQuest UWM1000 [10]: the bit rate is 10k bps; the maximal transmission range is 100 meters (in all directions); and the power consumption in sending, receiving, and idling mode are 2w, 0.1w, and 10mw, respectively. The same broadcast Media Access Control (MAC) protocol as in [17] is used in our simulations. In this MAC protocol, when a node has a packet to send, it first senses the channel. If the channel is free, it continues to broadcast the packet. Otherwise, it backs off. The packet will be dropped if the maximal number of backoffs have been reached. We use the following metrics to evaluate the performance of routing protocols. – Packet Delivery Ratio is defined as the ratio of the number of distinct packets received successfully at the sinks to the total number of packets generated at the source node. Although a packet may reach the sinks multiple times, these redundant packets are considered as only one distinct packet. – Average End-to-end Delay represents the average time taken by a packet to travel from the source node to any of the sinks. – Total Energy Consumption represents the total energy consumed in packet delivery, including transmitting, receiving, and idling energy consumption of all nodes in the network. 4.2
Impact of Design Parameters
Now we examine how the performance of DBR is affected by algorithm parameters and network settings: parameter δ, depth threshold dth , node mobility, and number of sinks. Parameter δ. The parameter δ decides the holding time of packets at each node. With a larger δ, each node has a shorter holding time and hence the average end-to-end delay will be reduced; but more nodes will forward the same packet, which results in more energy consumption. On the other hand, with a smaller δ, a node will have longer holding time and hence the average end-to-end delay is increased; but less nodes will forward the same packet, as helps to reduce energy consumption. Fig. 5 shows how the energy consumption and average end-to-end delay change with three different values of δ: R/4, R/2, and R, where R is the maximal transmission range. In this set of simulations, the number of sinks is set to 5 and the depth threshold is set to 0. From Fig. 5(a), we observe that the average
82
H. Yan, Z.J. Shi, and J.-H. Cui 14000 Total Energy Consumption
Average E2E Delay (sec)
6 R/4 R/2 R
5 4 3 2 1
R/4 R/2 R
12000 10000 8000 6000 4000 2000 0
0 200
300
400 500 600 Number of Nodes
700
200
800
(a) Average end-to-end delay
300
400 500 600 Number of Nodes
700
800
(b) Energy consumption
1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0
16000 Total Energy Consumption
Packet Delivery Ratio
Fig. 5. DBR’s performance with different δ values
0 20 40
14000
0 20 40
12000 10000 8000 6000 4000 2000 0
200
300
400 500 600 Number of Nodes
700
(a) Packet delivery ratio
800
200
300
400 500 600 Number of Nodes
700
800
(b) Energy consumption
Fig. 6. DBR’s performance with different depth thresholds
end-to-end delay when δ = R4 is about three times of the delay when δ = R. Fig. 5(b) shows that the energy consumption does increase as δ is lifted, but not significantly (less than 5%). Hence, we choose δ = R in later simulations. Depth Threshold. Fig. 6 shows how the depth threshold, dth , affects the packet delivery ratio and energy consumption. In this set of simulations, the number of sinks is set to 5. From Fig. 6, we see that when the depth threshold increases, both the packet delivery ratio and the total energy consumption decrease. This is because increasing the depth threshold has a similar effect to reducing the number of available nodes in the network. Therefore, the number of forwarding nodes will decrease. Consequently, the packet delivery ratio decreases and less energy is consumed. Node Mobility. To evaluate how node mobility affects the performance of DBR, we simulate DBR with different fixed node speeds at 1 m/s, 5 m/s, and 10 m/s. The depth threshold is set to 0 and the total number of sinks deployed is 5. The simulation results are plotted in Fig. 7. From Fig. 7, we observe that the packet delivery ratio, total energy consumption, and average delay do not change much with node speed. The reason is that all routing decisions in DBR are made locally based on a node’s depth information. No topology or route information needs to be exchanged among neighboring
DBR: Depth-Based Routing for Underwater Sensor Networks
83
16000 Average E2E Delay (sec)
Packet Delivery Ratio
4
1 0.98 0.96 0.94 0.92 0.9 0.88 0.86 0.84 0.82 0.8
1 m/s 5 m/s 10 m/s
14000 12000 10000 8000
1 m/s 5 m/s 10 m/s
6000 4000 2000
(a) Packet delivery ratio
3 2.5 2 1.5
1 m/s 5 m/s 10 m/s
1 0.5 0
0
200 300 400 500 600 700 800 Number of Nodes
3.5
200
300
400
500
600
700
800
Number of Nodes
(b) Energy consumption
200
300
400 500 600 Number of Nodes
700
800
(c) Average end-to-end delay
Fig. 7. DBR’s performance with different node mobility
nodes. Therefore, DBR can handle dynamic network topologies well. For example, Fig. 7(a) shows that DBR successfully delivers at least 88% of the packets in all cases. When the total number of nodes is larger than 400, almost all packets can be successfully delivered. From Fig. 7 we can also see how node density affects the performance of DBR. The figure shows that the packet delivery ratio and the energy consumption increase as the number of nodes increases. The average end-to-end delay, however, decreases. This is because when the number of nodes increases, the number of forwarding nodes also increases, which leads to a higher packet delivery ratio and higher energy consumption. At the same time, the probability that a forwarding node has a shorter distance to the sinks increases as more nodes participate in packet forwarding. As a result, the average end-to-end delay decreases. Number of Sinks. Fig. 8(a) shows how the packet delivery ratio changes with different number of sinks. DBR with multiple sinks has a better packet delivery ratio than DBR with only one sink. Since DBR is a greedy algorithm trying to deliver data packets to the water surface, increasing the number of sinks at the water surface will increase the chance that a packet is received by a sink. This explains the higher delivery ratio when multiple sinks are deployed. The total energy consumption for different number of sinks is shown in Fig. 8(b). We observe that the energy consumption is almost the same for different number of sinks. The reason is that in DBR, the number of sinks does not affect the forwarding process. Therefore, all different settings have almost the same energy consumption. From Fig. 8(c), we observe that DBR with multiple sinks has a slightly better average end-to-end delay than DBR with one sink. This is because in the multiple-sink case, a packet is considered successfully delivered whenever it reaches any of the sinks. 4.3
Comparison with VBF
Now we compare DBR with VBF [17]. In this set of simulations, we consider two settings for DBR: one sink and multiple sinks. For one-sink DBR, the depth threshold is set to 0. In multiple-sink DBR, 5 sinks are randomly deployed at
H. Yan, Z.J. Shi, and J.-H. Cui
3
1 sink 3 sinks 5 sinks 10 sinks
Average E2E Delay (sec)
12000
1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0
Total Energy Consumption
Packet delivery Ratio
84
1 sink 3 sinks 5 sinks 10 sinks
10000 8000 6000 4000
2.5 2 1.5 1 sink 3 sinks 5 sinks 10 sinks
1 0.5
2000
0 200
300
400 500 600 Number of Nodes
700
800
(a) Packet delivery ratio
0
200 200
300
400 500 600 Number of Nodes
700
800
(b) Energy consumption
300
400 500 600 Number of Nodes
700
800
(c) Average end-to-end delay
Fig. 8. DBR’s performance with different number of sinks
the water surface and the depth threshold is set to 20 meters. For VBF, we set the routing pipe radius to 100 meters, which is the maximal transmission range. Fig. 9 compares DBR and VBF with respect to the three metrics. Fig. 9(a) shows that for the one-sink setting, DBR achieves a similar packet delivery ratio to VBF. With the multi-sink setting, however, DBR can achieve a much better delivery ratio, especially for sparse networks. For example, in a network with 200 nodes, DBR with five sinks has a packet delivery ratio of around 70%, which is more than four times larger than 15%, the delivery ratio of VBF. Fig. 9(b) shows that DBR has better energy efficiency compared with VBF. In all cases, the total energy consumption of DBR is about half that of VBF. This is mainly due to the the redundant packet suppression techniques adopted by DBR. The two-queue mechanism in DBR has greatly reduced the redundant packet transmissions in the network. It should be noted, however, that this comparison is made based on the basic settings of VBF. VBF may get better energy efficiency when advanced adaptation algorithms are applied and optimal parameters are chosen. Fig. 9(c) shows that the best end-to-end delay is achieved in multiple-sink DBR while VBF has a better end-to-end delay than one-sink DBR. This is because VBF tries to find the shortest path from the source node to the sink along the virtual vector between them. Thus the delay in VBF is shorter than that in one-sink DBR. In multiple-sink DBR, however, packets can be delivered to any sink, instead of a fixed sink as in VBF. It should be noted that DBR and VBF target different network settings and have quite different network assumptions. For example, VBF is designed for networks with a single sink. Although DBR can work in one-sink networks, it has better performance in multiple-sink settings. 4.4
Summary
The simulation results show that DBR protocol works well for dense networks. However, the delivery ratio in sparse networks is relatively low. The reason is that DBR has only a greedy mode. The greedy method alone is not able to achieve high delivery ratios in sparse networks. We will investigate recovery algorithms for DBR in the future.
1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0
5
one-sink multiple-sink VBF
20000
Average E2E Delay (sec)
one-sink multiple-sink VBF
15000 10000 5000
300
400 500 600 Number of Nodes
700
800
(a) Packet delivery ratio
4 3 2
one-sink multiple-sink VBF
1 0
0
200
85
6
25000 Total Energy Consumption
Packet Delivery Ratio
DBR: Depth-Based Routing for Underwater Sensor Networks
200
300
400 500 600 700 Number of Nodes
200
800
(b) Energy consumption
300
400 500 600 Number of Nodes
700
800
(c) Average end-to-end delay
Fig. 9. Comparison of DBR and VBF
The DBR protocol requires more memory in sensor nodes to maintain two buffers. Since the underwater sensor nodes normally are equipped with more resources than land-based sensor nodes, the memory overhead is not significant in most systems. Moreover, the applications for underwater sensor networks have relatively low data rate so only small buffers need to be maintained. For example, we observed in our simulations that the average number of packets in the sending queue of each node is less than 10. As a result, the cost of extra memory is affordable for underwater sensor nodes.
5
Conclusions and Future Work
In this paper, we presented Depth Based Routing (DBR), a routing protocol based on the depth information of nodes, for underwater sensor networks. DBR uses a greedy approach to deliver packets to the sinks at the water surface. Different from other geographical-based routing protocols that require full-dimensional location information of nodes, DBR only needs the depth information, which can be easily obtained locally at each sensor node. Further, DBR can naturally takes advantages of the multiple-sink underwater sensor network architecture without introducing extra cost. Our simulation results have shown that DBR can achieve high packet delivery ratios (at least 95%) for dense networks, with reasonable energy consumption. To achieve better performance for sparse networks, recovery algorithms need to be explored to avoid the “void” areas where the greedy strategy fails. Advanced recovery algorithms should be developed for higher energy efficiency and delivery ratio. DBR provides a distributed routing protocol based on local information of the sensor nodes. Besides the depth information, other information, such as the residual energy level and estimated distance to neighboring nodes, could also be useful in making routing decisions that can further reduce energy consumption and extend the network’s life time. For multiple-sink network settings, we only consider some simple cases in which the sinks are randomly, uniformly deployed on the water surface. Given the routing protocol and the node deployment model, we may find better deployment locations for the multiple sinks to achieve better performance.
86
H. Yan, Z.J. Shi, and J.-H. Cui
References 1. Akyildiz, I.F., Pompili, D., Melodia, T.: Challenges for efficient communication in underwater acoustic sensor networks. ACM SIGBED Review 1(1) (July 2004) 2. Basagni, S., Chlamtac, I., Syrotiuk, V.R., Woodward, B.A.: A distance routing effect algorithm for mobility (dream). In: MOBICOM 1998 (1998) 3. Braginsky, D., Estrin, D.: Rumor routing algorithm for sensor networks. In: WSNA 2002 (September 2002) 4. Cui, J.H., Kong, J., Gerla, M., Zhou, S.: Challenges: Building scalable mobile underwater wireless sensor networks for aquatic applications. Special Issue of IEEE Network on Wireless Sensor Networking (May 2006) 5. Grossglauser, M., Vetterli, M.: Locating nodes with ease: Mobility diffusion of last encounters in ad hoc networks. In: IEEE INFOCOM 2003 (March 2003) 6. Heidemann, J., Ye, W., Wills, J., Syed, A., Li, Y.: Research challenges and applications for underwater sensor networking. In: IEEE Wireless Communications and Networking Conference (April 2006) 7. Heinzelman, W.R., Kulik, J., Balakrishnan, H.: Adaptive protocols for information dissemination in wireless sensor networks. In: Mobicom 1999 (August 1999) 8. Intanagonwiwat, C., Govindan, R., Estrin, D.: Directed diffusion: A scalable and roust communication paradigm for sensor networks. In: MOBICOM 2000 (August 2000) 9. Karp, B., Kung, H.T.: Gpsr: Greedy perimeter stateless routing for wireless networks. In: Proc. Mobicom (2000) 10. Linkquest, http://www.link-quest.com/ 11. Nicolaou, N., See, A., Xie, P., Cui, J.-H., Maggiorini, D.: Improving the robustness of location-based routing for underwater sensor networks. In: Proceedings of IEEE OCEANS 2007 (June 2007) 12. The ns mannual (2002), http://www.isi.edu/nsnam/ns/doc/index.html 13. Partan, J., Kurose, J., Levine, B.N.: A survey of practical issues in underwater networks. In: Proc. of ACM International Workshop on UnderWater Networks (WUWNet), September 2006, pp. 17–24 (2006) 14. Proakis, J., Sozer, E.M., Rice, J.A., Stojanovic, M.: Shallow water acoustic networks. IEEE Communications Magazines, 114–119 (2001) 15. Seach, W.K., Tan, H.X.: Multipath virtual sink architecture for underwater sensor networks. In: OCEANS (May 2006) 16. Xie, G.G., Gibson, J.: A networking protocol for underwater acoustic networks. Technical Report TR-CS-00-02 (2000) 17. Xie, P., Cui, J.-H., Lao, L.: Vbf: Vector-based forwarding protocol for underwater sensor networks. In: Proceedings of IFIP Networking (May 2006) 18. Ye, F., Luo, H., Cheng, J., Lu, S., Zhang, L.: A two-tier data dissemination model for large-scale wireless sensor networks. In: MOBICOM 2002 (September 2002) 19. Ye, F., Zhong, G., lu, S., Zhang, L.: Gradient broadcast: A robust data delivery protocol for large scale sensor networks. ACM Wireless Networks(WINET) 11(2) (2005)
Channel Allocation for Multiple Channels Multiple Interfaces Communication in Wireless Ad Hoc Networks Trung-Tuan Luong, Bu-Sung Lee, and C.K. Yeo School of Computer Engineering Nanyang Technological University, Nanyang Avenue, Singapore 639798 {Y050089,bslee,asckyeo}@ntu.edu.sg
Abstract. A major drawback of multi-hop communication in ad hoc network is the bandwidth scarcity along the forwarding path of data packet. The main reason for the lack of bandwidth or the exponential reduction in the bandwidth is the contention for bandwidth between nodes along the path. In this paper we will demonstrate one way to overcome this problem through the use of multiple channels multiple interfaces (MCMI). We investigate different forwarding channel selection schemes for MCMI communication with Destination Sequenced Distance Vector protocol: same channel, random and round robin. Based on our analysis and simulation results we have shown that MCMI protocol significantly improves the channel capacity while maintaining low end-to-end delay. Forwarding channel selection policies play an important role in determining the performance of the MCMI. Among the channel assignment policies under study, round robin policy provides the best performance. The results provide a baseline for evaluating bandwidth of multiple channels multiple interfaces networks. Keywords: Multiple channel communication, channel interference, channel assignment, bandwidth.
1
Introduction
Wireless communication has become an indispensable part of modern day-to-day life. Research in ad hoc networks has focused on single channel networks, in which a common channel is desired for simple routing control in multi-hop networks. A well known fact that is affecting the performance of ad hoc networks is the significant throughput degradation along the multi-hop path [1]. When a single channel is used both for incoming and outgoing traffic, throughput is halved as they use the same radio channel. That means when one node is transmitting, its neighbors nodes must all be in listening mode otherwise collision will occur. This problem is amplified across the network, and after a few hops the bandwidth is reduced significantly. To overcome the throughput degradation problem, a natural approach is to use multiple channels in which nodes work on different channels in an interference area. A. Das et al. (Eds.): NETWORKING 2008, LNCS 4982, pp. 87–98, 2008. c IFIP International Federation for Information Processing 2008
88
T.-T. Luong, B.-S. Lee, and and C.K. Yeo
Recent research and commercial efforts in the wireless networking industry have focused on a new class of ad hoc networks: multiple channels multiple interfaces ad hoc networks [1]. These networks are characterized by a set of fixed nodes with multiple wireless interfaces utilizing multiple orthogonal channels at the same time over a given swath of spectrum such as IEEE 802.11 a/b/g. Simultaneous operation of multiple channels provides the following advantages: – Capacity enhancement: A node with two interfaces can send packets on two channels simultaneously. More importantly, forwarding nodes can both send and receive at the same time. Using appropriate protocols for channel selection and assignment, such a system can provide significantly greater capacity than a single interface system – Load sharing: Load sharing occurs where a traffic flow is distributed among the available connections to achieve lower latency and increase robustness to network. – Channel failure recovery: Graceful degradation and robustness against channel errors is possible by employing frequency diversity. Frequency diversity can be achieved by using multiple interfaces and operating each on different channel frequencies. In this paper, we implement the Destination Sequenced Distance Vector (DSDV) for multiple channels multiple interfaces wireless ad hoc networks (DSDV-MCMI) to reduce the bandwidth degradation problem. In DSDV-MCMI, we investigated three different policies for forwarding channel selection: same channel, random channel and round robin channel to evaluate the channel interference along the multi-hop path. Our simulation results show that DSDVMCMI protocol significantly improves the network goodput while maintaining low end-to-end delay. Among the three different channels selection policies for MCMI, round robin policy, where the packets are forwarded based on the packet incoming channel, is the best at preventing channel interference; which results in shortest end-to-end delay time. Our paper outline is as follows. Section 2 briefly discusses the related work. In Section 3, we present the multiple channels multiple interfaces protocol with DSDV-MCMI. The simulation and results analysis are given in Section 4. Finally, Section 5 concludes the paper.
2
Related Work
We can categorize strategies for using multiple channels into two groups depending on the number of interfaces used: single interface and multiple interfaces. The first strategy is to enable a single wireless interface card to access multiple channels [2,3]. For example, So and Vaidya [3] propose a scheme that allows wireless devices to communicate on multiple channels using a single interface card. The scheme requires frequent channel switching, which incurs considerable overhead on the current hardware. The other strategy is to use multiple interface cards; Nasipuri et al. [4,5,6] propose a class of multi-channel carrier sense multiple access
Channel Allocation for MCMI Communication
89
MAC protocols where all nodes have an interface on each channel. These proposed protocols use different metrics to choose the channel for communication between nodes. The metric may simply use the idle channel [4], or the signal power observed at the sender [5], or the received signal power at the receiver [6]. Wu et al [7] propose a MAC layer solution that requires two interfaces. One interface is assigned to common channel for control purposes, and the second interface is switched between the remaining available channels for transmitting data. Lee [8] proposed a class of proactive routing protocol for multi channels, which uses one control channel and N data channels. The nodes exchange control packages on the control channel to negotiate the best channel for the receiver’s data channel. Most past research in the use of multiple channels require either modification of the MAC layer protocol or changes to IEEE 802.11. Compared to previous research, our proposed protocol focus on exploit the multiple channels by using concurrent multiple interfaces. The protocol does not require channel synchronization among nodes. Although there is some additional control overhead, the simulation results show that the proposed protocol significantly increase network goodput while decreasing end-to-end delay efficiently.
3 3.1
Multiple Channels Multiple Interfaces Routing with DSDV Model Description
Module based node for ns-2. Wireless nodes are becoming multimodal. They are equipped with multiple interfaces possibly using different technologies, including wired access, and may use them concurrently. Paquereau [9] designed module based wireless node (MW-Node), a more flexible and better integrated wireless and mobile support in ns-2[10]. It is not a new implementation but primarily a reorganization of already existing components. The MW-Node enables new features to be supported by the simulator. For instance, true support for multiple wireless interfaces on a single node, each may have its own routing protocol. DSDV-MCMI. Based on the MW-Node model, we developed destination sequenced distance vector for multiple channels multiple interfaces, DSDV-MCMI, to demonstrate the multiple channels multiple interfaces routing scheme. Nodes can have more than one network interfaces as shown in Fig. 1. These interfaces are assigned to orthogonal channels so that they will not interfere with each other. Every interface has one DSDV [11] routing agent for generating control messages and forwarding data packets. Destination-Sequenced Distance-Vector Routing (DSDV) is a table-driven routing protocol based on the Bellman-Ford algorithm. Each mobile node maintains a route to every other node in a routing table. Route entry contains destination address, next hop address and number of host to reach the destination. In order to prevent routing loop, each entry is marked with a sequence number assigned by the destination node. The sequence numbers enable node to
90
T.-T. Luong, B.-S. Lee, and and C.K. Yeo
Fig. 1. Multi-interface node
distinguish stale routes from new ones. The DSDV routing agent at each interface maintains its’ own routing table for all available destinations. To maintain the consistency of routing tables in a dynamically varying topology, each node’s interface periodically transmits full updates or immediately transmits incremental updates when significant new information is available, such as a topology changes. We design a channel assignment module on top of the network interfaces. This module is in charge of selecting the network interface for forwarding each data packets. 3.2
Channel Assignment Policy
The purpose of channel assignment is to determine the forwarding channel for packet to minimize interference with other nodes. We apply the static approach [12] that assigning a common set of channels for node’s interfaces. Every node has N interfaces, which are assigned to the same set of N orthogonal channels. At the source node, data packet is sent out on an interface which is randomly selected. When an intermediate node along the path receives a data packet on incoming channel Chin ; the node uses one of the following three policies to select the outgoing channel Chout for relaying data packet: – Policy 1 Same channel: node will relay the packet on the same channel as the packet was received. This approach incurs high channel interference in multi-hop route, which results in long delay and packet drops that degrade the performance significantly. Chout = Chin – Policy 2 Random channel: node relays data packet on a randomly selected channel. The probability that the forwarding channel is the same as the received channel is N1 . When a node has more interfaces, the less chance that the forwarding channel is the same as the received channel. Chout = Random(Ch0 ,Ch1 ,..,ChN −1) – Policy 3 Round robin channel: when a node receive data packet need to be forwarded on ith channel it will forward that packet on the (i+1)th channel. Chout = (Chin + 1) mod (N)
Channel Allocation for MCMI Communication
3.3
91
Channel Interference
Assuming that nodes are ideally placed along the route with hop distance ’d’ as in Fig.2, all the node has transmission range ’T’ and carrier sensing range ’C’. The ideal placement of a node is d ≤ T < 2∗d
(1)
The transmissions of a node interfere with transmissions of other nodes within its’ sensing range. Thus sensing range is also called as interference range. The interference distance in term of number of hops along a path is: M = Cd hops where Cd is floor of Cd This means that transmission of a node may interfere with transmission of the next M nodes and transmission of the previous M nodes along the path. We will prove the throughput by using multiple channels for transmission; the minimum number of channels required to eliminate the channel interference among forwarding nodes along the path is (M+2). As shown in Fig. 2, nodes A1 , A2 ,..,
Fig. 2. Multi-hop path
AM+1 are within interference range of each other, because the distance between A1 and AM+1 is M hops. Therefore the (M+1) data transmissions from Ai to Ai+1 (i=1,2,..,M+1) can interfere with each other. Due to the exposed node problem, data transmission from node AM+1 to node AM+2 can also interfere with CTS/ACK packet sent from node A1 to node S. Thus we can see that there are (M+2) data transmissions interfering with each other. Hence we need at least (M+2) channels so that every data transmission can work on different channel to ensure these communications will not interfere with each other. In Fig. 3, we apply policy 3 for forwarding channel selection among the set of (M+2) channels { Ch0 , Ch1 ,..,ChM+1 }. We can see that two transmissions use the same channel, such as link S-A1 and link AM+2 -AM+3 , are (M+1) hops apart along the path, hence they will not interfere with each other. Thus with (M+2) available channels, we can use policy 3 for channel assignment for data transmission so that we can eliminate channel interference
92
T.-T. Luong, B.-S. Lee, and and C.K. Yeo
Fig. 3. Channel assignment for communication link in multi-hop path
3.4
Capacity of a Chain of Multiple Channels Multiple Interfaces Nodes
In this subsection, we evaluate the capacity of a single chain of nodes where packets are originated at first node and forwarded along the chain to the last node. We investigate chain of nodes under saturated condition that every node along the chain always has packet to forward. When node A select channel to forward packet, we denote PI (A) the probability that the selected channel will be interfered. Let S be the set of N available channels; B is channel bandwidth; B(A) is bandwidth experienced by node A. BChain is the maximum bandwidth can be achieved for transmission from source to destination of the chain. M is the interference distance in term of number of hops and L is hops length of the chain. Along the chain, we can see that the middle node such as node AM+1 in Fig. 2 is the bottleneck node, because its’ data transmission may share the same channel with most number of other transmissions. Bandwidth of chain is reduced significantly because of those nodes. Thus we will evaluate the bandwidth can be experienced by the middle node A in the chain. Policy 1. we have Chout = Chin , therefore two consecutive data transmissions along the path always interfere with each other. Thus channel interference always happens, PI (A) =1. If the chain is long enough, which is equal or more than (2*M+2) hops long. We examine the middle node AM+1 as in Fig. 2; AM+1 will share the same channel with the next M nodes AM+2 ,.., A2M+1 and the previous M nodes A1 ,.., AM along the path. However due to the exposed node problem, transmission from node AM+1 to node AM+2 will also interfere with CTS/ACK packet sent from node A1 to node S. Therefore we can say that node AM+1 shares the same B channel with (2*M+1) other node.; this makes B(AM+1 ) = 2∗M+2 . Thus the B chain of nodes can achieve a maximum bandwidth of 2∗M+2 . If hops length L < (2*M+2); the middle node will have carrier sensing range cover the whole chain, thus its’ data transmission will share the same channel with all the other (L-1) transmissions along the path. So its’ experienced bandwidth B will be B L . Therefore the chain can achieve a maximum bandwidth of L . B if L ≥ (2 ∗ M + 2) BChain = 2∗M+2 (2) B if L < (2 ∗ M + 2) L Policy 2. we denote PN I (A) the probability that the selected channel of A will not be interfered. PN I (A) = 1 - PI (A). Let K be number of forwarding nodes
Channel Allocation for MCMI Communication
93
along the chain excluding A stay inside carrier sensing range of A. As discussed in policy 1, K is (2*M+1) if L ≥ (2*M+2); otherwise K is (L-1). We can see that PN I (A) equals to the probability that node A selects channel Chi and the other K nodes select among the rest (N-1) channels (S\ {Chi }) multiply by N. K *N = NN−1 K PI (A) = 1- PN I (A) = 1- NN−1
PN I (A) =
1 N
*
N −1 K N
we denote PI (A,J) the probability that the selected channel of A will be shared with other J nodes J+1 N −1 K−J J N −1 K−J PI (A,J) = N1 ∗ N ∗ N = N1 ∗ N J=0..K where 1 K K K (N −1)K−J B B(A) = J=0 PI (A, J) ∗ J+1 =B ∗ N J=0 J+1
BChain = B ∗
1 N
K K (N − 1)K−J (2 ∗ M + 1) if L ≥ (2 ∗ M + 2) whereK = L−1 if L < (2 ∗ M + 2) J + 1 J =0 (3)
Policy 3. We first evaluate the long chain of nodes that L ≥ (2*M+2). If N ≥ (M+2), policy 3 can help to eliminate channel interference; thus PI (A) = 0 and B(A)= B. Else if N < (M+2), PI (A) = 1 and node A will share the same M channel with next M along the chain. Node A N nodes and previous N nodes may share the same channel with the exposed node if M+1 = M+1 N N . Therefore B(A) = M + BM +1 +1 . N N Then we evaluate the short chain that L< (2*M+2). If L ≤ N then all the transmissions use different channel thus PI (A) = 0 and B(A)= B. Else if L > L N, data transmission of node A will share the same channel with other N -1 L L transmission. Therefore PI (A) = 1 and B(A)= B where N is ceiling of N L N ⎧ B if L ≥ (2 ∗ M + 2)andN ≥ (M + 2) ⎪ ⎪ B ⎪ ⎨ M if L ≥ (2 ∗ M + 2)andN < (M + 2) N + MN+1 +1 BChain = (4) B if N < L < (2 ∗ M + 2) ⎪ L ⎪ ⎪ N ⎩ B if L ≤ N
4 4.1
Simulation and Results Verification of Chain Results
First we simulate MCMI in a chain of nodes setup, where nodes are placed ideally 150m apart from each other. The transmission range is 250m and carrier sensing range is 550m. This is the worst-case placement, where node is placed at just above half of transmission range of each other. In this scenario, interference distance M is 3 hops. Packet is originated at source node with the rate of 2Mbps, which equals to channel bandwidth; so that data transmission of the chain is
94
T.-T. Luong, B.-S. Lee, and and C.K. Yeo Table 1. Bandwidth drop rate when chain’s length increases Chain length (hops) 1 2 3 4 5 5
Interface Interface Interface Interface Interface Interface
with with with with with
Policy Policy Policy Policy Policy
3 3 3 2 3
1 2
3
4
5
6
7
8
9
10
1 2
1 3 1 2
1 4 1 2 1 2
1 5 1 3 1 2 1 2
1 6 1 3 1 2 1 2
1 7 1 4 1 3 1 2
1 8 1 4 1 3 1 2
1 8 1 4 1 3 1 2
1 8 1 4 1 3 1 2
1 1 1 1 1 1
1 1 1 0.9 1
1 1 1 0.73 0.59 0.47 0.38 0.30 0.24 0.24 0.24 1 1 1 1 1 1 1 1
under saturated condition. We will measure the bandwidth can be achieved when the chain is 1-hop length and measure how the bandwidth drops when chain is longer. We increases numbers of interfaces equipped by nodes and apply different channel selection policy to verify our analysis. We calculate the drop rate of maximum bandwidth achieved of chain of Nhops length compared to 1-hop length chain according to equation (2), (3), (4). The result is summarized in Table 1 Fig. 4 shows the comparison results of our
Fig. 4. Bandwidth drop rate when number of hops increases
simulation and analysis. We can see that our simulation’s results are very close to the analysis results shown in Table 1. When the chain gets longer, packet must traverse more hops. Packets’ end-to-end delay increases while bandwidth decreases. 4.2
Simulation of MCMI in Two Dimensions Multihops Network Environment
We evaluated the performance of MCMI in static ad hoc network of map size 1200mx800m with network node density of 80 nodes. This setting helps to ensure that network is crowded enough so that we can have a path between any nodes; and network is also scarce enough so that the path length is long for evaluating effects of different channel allocation policies. The average hop counts of our
Channel Allocation for MCMI Communication
95
Table 2. Simulation Setting Parameter
Setting
Traffic model Packet size Packet sending rate Mac Transmission range Carrier sensing range Map size Node number Simulation time
20CBR connections 512 bytes 2pkt/s-12pkts/s 802.11 2Mbps 250m 550m 1200mx800m 80 300s
simulation are 3.5 hops. We simulate 20 CBR connections with 512bytes packet size in 300 seconds. The packet rate increases from 2 packets/s to 12 packets/s to vary the traffic load. A summary of the simulation setting is given as shown in Table 2. The following performance metrics are used to evaluate the simulation results: – Goodput: the number of useful bits per unit of time forwarded by the network from a certain source address to a certain destination, excluding protocol overhead, and excluding retransmitted data packets – End-to-end delay: the average time it takes for a packet to traverse the network from its source to destination. 4.3
Result Analysis
Goodput Experiment 1: Effects of number of Interfaces,N. Fig. 5 shows the goodput results at different traffic load for different number of channels. The goodput performance of N-interfaces is normalized against the performance of 1-interface. With increasing number of node’s interface, nodes can receive packet on one interface and send packet on other interface at the same time. Thus with more interfaces, node can share the traffic load better, which help to reduce the congestion. Therefore as expected when number of interfaces increases, the goodput increases. We do not expect the goodput to increase linearly as the number of interfaces increases, because communication paths can crossover and interfere each others. This causes bandwidth reduction in all the crossover communication path. Experiment 2: Effects of Forwarding Channel Assignment Policy. The normalized goodput performances of three channel assignment policies is compared against policy 1 in three-interface network are shown in Fig. 6. Policy 3 is the best as it diversifies channel usages, which results in greatest goodput achieved. Policy 1 does nothing to prevent channel interference, thus its’ goopdut performance is much less than that of policy 3. Policy 2 does a little effort to prevent
96
T.-T. Luong, B.-S. Lee, and and C.K. Yeo
Fig. 5. Normalized goodput regarding number of interfaces
Fig. 6. Normalized goodput regarding forwarding channel selection policy
channel interference by selecting forwarding channel randomly, which still has probability of channel interference. Thus policy 2 performs slightly worse than policy 3. End-to-End Delay Experiment 1: Effects of number of Interfaces,N. Fig. 7 shows the corresponding results of end-to-end delay for different number of network interface used for transmission, as the traffic load is increased. A key observation is that, in a congested network, packets will be kept in queue for very long, waiting for channel availability; which resulted in either long end to end delay or packet dropped. When node has more interfaces, it will be able to forward packets through all the interfaces. Thus packets need not wait long in queue; as the result, with more interface the end-to-end delay decreases considerably. For example at packet sending rate of 10pkt/s, the end to end delay can be reduced by 2, 4, 6 times that of a single interface when node has 2, 3 and 4 interfaces respectively.
Channel Allocation for MCMI Communication
97
Fig. 7. End-to-end delay regarding number of interfaces
Experiment 2: Effects of Forwarding Channel Assignment Policy. Fig. 8 presents the end to end delay performance of three channel assignment policies in three-interface node configuration with varying traffic load. Forwarding data packets on the same channel as the receiving channel incurs the greatest channel interference, thus policy 1 has the highest end-to-end delay. Policy 3 is the best as it diversifies channel usages, thus it can help reduce channel interference, which results in shortest end-to-end delay. The performance of policy 2 is slightly worse than policy 3.
Fig. 8. End-to-end delay regarding forwarding channel selection policy
5
Conclusion
We presented a multiple channels multiple interfaces ad hoc network routing protocol, DSDV-MCMI, which utilizes multiple channels to enable simultaneous multiple transmission to improve network capacity. This proposed scheme does not require modification to the current IEEE 802.11 MAC protocol. Simulation
98
T.-T. Luong, B.-S. Lee, and and C.K. Yeo
results shows that DSDV-MCMI exploits multiple channels multiple interfaces to improve network capacity and reduce channel interference. With more equipped network interfaces, we can achieve higher goodput and shorter end-to-end delay time. We also suggested some policies for forwarding channel selection: same channel, random channel and round robin channel; these policies play an important role in determining performance of MCMI. However, there is also an issue of crossover interference among the communication path and one needs a deeper understanding before a satisfactory solution is found.
References 1. Bahl, P., Adya, A., Padhye, J., Walman, A.: Reconsidering wireless systems with multiple radios. SIGCOMM Comput. Commun. Rev. 34(5), 39–46 (2004) 2. Chandra, R., Bahl, P., et al.: Multinet: Connecting to multiple ieee 802.11 networks using a single wireless card. In: Proceedings of IEEE Infocom 2004, Hongkong (March 2004) 3. So, J., Vaidya, N.H.: Multi-channel mac for ad hoc networks: handling multichannel hidden terminals using a single transceiver. In: MobiHoc 2004: Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, pp. 222–233. ACM Press, New York (2004) 4. Nasipuri, A., Zhuang, J., Das, S.R.: A multichannel csma mac protocol for multihop wireless networks. In: Wireless Communications and Networking Conference. WCNC, vol. 3, pp. 1402–1406. IEEE, Los Alamitos (1999) 5. Nasipuri, A., Das, S.: Multichannel csma with signal power-based channel selection for multihop wireless networks. In: Vehicular Technology Conference, 2000. IEEE VTS-Fall VTC 2000. 52nd, vol. 1(1), pp. 211–218 (2000) 6. Jain, N., Das, S., Nasipuri, A.: A multichannel csma mac protocol with receiverbased channel selection for multihop wireless networks. In: Proc. IEEE IC3N, Phoenix (October 2001) 7. Wu, S.-L., Lin, C.-Y., Tseng, Y.-C., Sheu, J.-P.: A new multi-channel mac protocol with on-demand channel assignment for multi-hop mobile ad hoc networks. In: ISPAN ’00: Proceedings of the 2000 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN 2000), p. 232. IEEE Computer Society Press, Washington (2000) 8. Lee, U., Midkiff, S.F., Park, J.S.: A proactive routing protocol for multi-channel wireless ad-hoc networks (dsdv-mc). In: International Conference on Information Technology: Coding and Computing (ITCC 2005), vol. 2, pp. 710–715 (2005) 9. Paquereau, L., Helvik, B.E.: A module-based wireless node for ns-2. In: WNS2 2006: Proceeding from the 2006 workshop on ns-2: the IP network simulator, p. 4. ACM Press, New York (2006) 10. network simulator version 2 (ns 2): http://www.isi.edu/nsnam/ns/ 11. Perkins, C.E., Bhagwat, P.: Highly dynamic destination-sequenced distance-vector routing (dsdv) for mobile computers. Computer Communications Review 24(4), 234–244 (1994) 12. Katzela, I., Naghshineh, M.: Channel assignment schemes for cellular mobile telecommunication systems: a comprehensive survey. Personal Communications, IEEE [see also IEEE Wireless Communications] 3(3), 10–31 (1996)
Resilience to Dropping Nodes in Mobile Ad Hoc Networks with Link-State Routing Ignacy Gawędzki and Khaldoun Al Agha Laboratoire de Recherche en Informatique Université Paris-Sud 11, CNRS F-91405 Orsay, France [email protected], [email protected]
Abstract. Currently emerging standard routing protocols for MANETs do not perform well in presence of malicious nodes that intentionally drop data traffic but otherwise behave correctly with respect to control messages of the routing protocol. In this paper, we address the problem of coping with the presence of such nodes in networks that use a linkstate routing protocol. The solution, based on the verification of the principle of flow conservation, is purely protocolar and does not rely on any specific underlying OSI layer 1 or 2 technical feature. In addition, it is well suited for integration into existing link-state routing protocols for ad hoc networks, by using existing periodic control messages and by not requiring any clock synchronization between the nodes. The method, once implemented in an actual routing protocol, proves to increase the ratio of successfully delivered data packets significantly. Keywords: ad hoc networks, link-state routing, security, resilience.
1
Introduction
Routing protocols for mobile ad hoc networks (MANETs) have received much attention in the past decade, but currently the most mature solutions still rely on the full cooperation of the participating nodes. The presence of one or more malicious nodes may have negative consequences on the proper operation of the network. In the case of proactive protocols, nodes exchange control messages allowing them to maintain their routing table and data packet forwarding is performed on a hop-by-hop basis, using a traditional protocol stack (most commonly TCP/IP). This makes these protocols easy to implement as userspace processes while the operating system’s kernel remains unchanged. The downside is that securing the protocol itself is not enough to make the network resilient to malicious nodes, since they can always play nice with control packets, while not as much with data packets. The presented solution aims to reduce the impact of malicious nodes as much as possible, allowing others to route data packets around nodes that tend to lose traffic, provided that malicious nodes are not colluding. A. Das et al. (Eds.): NETWORKING 2008, LNCS 4982, pp. 99–111, 2008. c IFIP International Federation for Information Processing 2008
100
I. Gawędzki and K. Al Agha
After related work in the field is summarized in Sect. 2, the solution is detailed in Sect. 3. Performance evaluation is presented in Sect. 4, followed finally by a conclusion and some perspectives in Sect. 5.
2
Related Work
The issue of Byzantine robustness of network operations has received attention for as long as the network administration of the Internet has become more decentralized and thus more exposed to attacks. The problem reemerged for MANETs, since the direct application of solutions for wired networks appeared to be either impossible or ineffective. In the family of reactive routing protocols — of which DSR [9] and AODV [13] are notorious examples — various solutions have been proposed [2,7,1] to provide Byzantine robustness. Since route discovery and maintenance as well as data packet forwarding is taken care of by the protocol, cryptographic methods can be used to ensure that every packet has been forwarded to the destination, without being corrupted, misrouted nor forged. As for proactive routing protocols, the OLSR [5] protocol has received attention from Raffo et al. [14] who proposed to secure the content of control messages to prevent nodes from advertising false or expired information. Fourati et al. also proposed a way to secure control messages [6] by requiring neighbors to validate and sign TC messages using threshold cryptography. While these propositions aim to guarantee the correctness of the protocol in presence of malicious nodes, they do not protect against data packet dropping. Protecting data packets in the same (intrusive) way as proposed for reactive protocols would break the principle of separate table-driven hop-by-hop routing, so it is not desirable in this case. Additional cryptographic tools such as key distribution systems to allow sender authentication should be used, but they still do not enable the prevention or detection of intentional packet dropping. In order to make packet dropping detectable, Marti et al. proposed [12] to exploit the ability of nodes to overhear the transmissions of their neighbors to check whether they have retransmitted the packets as requested. Unfortunately, such an approach does not work anymore when directional antennae or multiple network interfaces (or simply different communication channels) are used on nodes. Other approaches, based on active probing of nodes to detect droppers, have also been proposed [10,2,11]. They rely on the inability of nodes to either distinguish probes from plain data packets or identify their originator. It is worth noting that many solutions to encourage cooperation [4,15] have been proposed as well. Although they may be very effective to discourage selfishness, they do not protect against malicious nodes that drop data traffic, be it at their own expense. In the context of static wired networks, Bradley et al. proposed [3] that nodes should periodically verify that each of their neighbors satisfies the principle of flow conservation based on their advertised packet counters. Nodes that fail to pass these tests are flagged as bad and excluded from the network. Their
Resilience to Dropping Nodes in MANETs with Link-State Routing
101
assumptions about the network have later been criticized as being too strong and a few possible attacks have been exposed by Hughes et al. [8]. However, this solution is also hardly applicable to MANETs, because of mobility and the difficulty to maintain tightly synchronized clocks between nodes.
3 3.1
Proposed Solution Motivations and Assumptions
Our experience in implementation of MANET routing protocols taught us that the less a solution is intrusive in the existing framework the easier it is to implement, maintain and port. Besides, relying only on basic features of drivers allows wider hardware support. With a protocolar approach, we sought a solution easy to implement by requiring little or no change at all in the OS kernel while no cross-layer requirement eases support for a wide range of network interface cards. The solution assumes that cryptographic mechanisms allow any node, be it the destination host or an intermediate router, to check a packet’s integrity and authenticate its source. The network is assumed to be running a linkstate routing protocol that exchanges periodic control packets. The bound P on the time separating two successive control packets is assumed to be finite and known. 3.2
Solution Outline
The solution is composed of three distinct phases, that are performed continuously during the operation of the network. First, perform unicast packet accounting, exchange counters periodically and verify the principle of flow conservation. Second, maintain a local degree of distrust in each other node, based on how often it fails the flow conservation tests and diffuse that value in the network. Third, combine local degrees of distrust from other nodes into a single, uniform metric (i.e. every other node comes up with the same values) and use it for routing table calculation. Note that intentional and unintentional packet droppings are not distinguished, which is desirable since in the third phase, intentional as well as unintentional packet droppers are simply avoided. This should have a positive effect on the overall operation of the network. 3.3
Checking Flow Conservation
In this section, the method used to check whether nodes’ counter values do not satisfy the flow conservation principle is presented. Definition 1. Let the network be a graph G = (V, E) with V the set of vertices (the nodes) and E : R+ → V × V a function mapping instants in time t to sets of arcs E(t) (the one-way links) existing at these instants.
102
I. Gawędzki and K. Al Agha
j i Definition 2. Let Iij (t) and Iij (t) be respectively i’s and j’s counter of the amount of bytes that flowed on link (i, j) up to instant t in packets which desj i tination was not j. Similarly, let Oij (t) and Oij (t) be respectively i’s and j’s counter of what flowed on (i, j) up to t in packets which source was not i.
The flow conservation principle states that i i ∀t, ∀i, Iji (t) − Oij (t) = 0 .
(1)
j i i If i advertised its counters Iji (t) and Oij (t) periodically, its neighbors could check (1) for each instant t at which i sent an advertisement. But since that simple check is based on i’s counters only, i could as well have advertised false values. Additional checks are thus needed to ensure that these are correct, namely:
∀t, ∀i, j,
j j i i Iji (t) = Iji (t) and Oij (t) = Oij (t)
and Tiji (t) = Tijj (t) ,
(2)
where Tiji (t) and Tijj (t) are respectively i’s and j’s counter of the total amount of bytes that flowed on (i, j) up to t. Because of mobility, the neighborhoods are changing and so absolute values of counters are inconvenient. Differential values are better advertised instead: a differential value is simply the difference between the current absolute value of a counter and its absolute value at the time of last advertisement. Definition 3. Let Si (t) be the value of i’s sequence counter at instant t and let Ti (n) be the instant at which the sequence counter is incremented from n − 1 to n and i’s advertisement set with sequence number n is transmitted. In the following, X is used to represent either I, O or T , to avoid repeating three times each formula that holds for each type of counter. j i i Definition 4. For each counter in the form Xij (t) or Xij (t), let X˙ ij (t) and j ˙ Xij (t) be their differential values.
∀t, ∀i, j, ∀k ∈ {i, j},
k k k X˙ ij (t) = Xij (t) − Xij (Tk (Sk (t)))
(3)
Definition 5. Let T− i (n) be the instant right before i’s nth advertisement set is sent. This notation is used only with differential values to avoid ambiguity. ∀t, ∀i, Si T− (4) i (Si (t)) = Si (t) − 1 Using periodic messages of the routing protocol, nodes advertise successive differential values of their counters. Definition 6. An advertised values of counters (AVC) tuple from i for neighbor j with sequence number n has the following form: i − − i I˙ij Ti (n) , O˙ ij Ti (n) , T˙iji T− i (n) , i Vj (n) = i − . (5) − i I˙ji T (n) , O˙ ji T (n) , T˙jii T− (n) i
i
i
Resilience to Dropping Nodes in MANETs with Link-State Routing P
P Ti (n)
Ti (n + 1)
103
P
Ti (n + 2)
Ti (n + 3) from i time from j
Tj (m − 2)
Tj (m − 1) P
Tj (m) Tj (m + 1) P
P
Fig. 1. Desynchronized advertisements: differential counter values from i and j are not advertised at the same time and thus do not represent flow on the same interval. Vertical arrows indicate instants at which advertisements from i (above) and j (below) are sent. Upper bound on the advertisement interval P is shown as well.
Between two successive transmissions of an AVC tuple for some neighbor j, a node i may receive zero or more AVC tuples regarding itself from j. Definition 7. Let Sij (n) be the (possibly empty) set of sequence numbers of j’s AVC tuples received by i between its (n − 1)th and nth advertisements. ∀i, j, ∀n, Sij (n) = m : Ti (n − 1) ≤ Tj (m) < Ti (n) ∧ (j, i) ∈ E (Tj (m)) (6) To allow neighbors of i to verify (2), i has to retransmit, along with each AVC tuple about a neighbor j, a set of reverse AVC tuples. In all, values of counters are diffused to the whole 2-hop neighborhood. Definition 8. Node i’s nth advertisement set contains nth link advertisements about each of its neighbor j. ⎧⎛ ⎞ ⎫ ⎬ ⎨ ⎝n, Vji (n), Ai (n) = m, Vij (m) ⎠ (7) ⎩ ⎭ i j
m∈Sj (n)
Given that advertisements are sent asynchronously, (1) can be performed directly, whereas (2) most probably cannot. The question is then how to decide that those equations are not satisfied, based on desynchronized counters, i.e. differential counter values over different intervals of time (see Fig. 1). The idea is to consider what can be called desynchronized link balances. Definition 9. A desynchronized link balance in terms of counter X for the link (k, l) (either (i, j) or (j, i)), computed from advertisement number n from node i about node j has the following form: − j − i ∀i, j, ∀n, ∀(k, l), BX ikl (n) = X˙ kl Ti (n) − X˙ kl Tj (m) . (8) m∈Sij (n)
When a node k receives the nth advertisement set from i, it can compute BX iij (n), i i i ˙j − since X˙ ij (T− i (n)) and every Xij (Tj (m)) with m ∈ Sj (n) are contained in A (n).
104
I. Gawędzki and K. Al Agha
Obviously, BX iij (n) and BX iji (n) are seldom zero, unless the counters in Ai (n) are zero themselves. Instead of looking at desynchronized link balances for individual advertisements, let us consider the sum of several desynchronized link balances for successive advertisements. It appears that these accumulated link balances have interesting properties. Definition 10. Let Δij (n) be the difference in time between the instant Ai (n) is sent and last j’s advertisement set was received by i.
∀i, j, ∀n,
Δij (n) =
⎧ ⎨Ti (n) − max Tj (m) i
if Sij (n) =∅ ,
⎩T (n) − T (n − 1) + Δi (n − 1) i i j
otherwise.
m∈Sj (n)
(9)
Suppose that k receives M successive advertisement sets from i, calculates the desynchronized link balances and sums them. That sum is expressed quite simply in terms of absolute counters. The intuitive argument can be seen on Fig. 1: the summed desynchronized link balance (the gray rectangles) from i’s advertisements n + 2 to n + 3 (i’s (n + 2)th advertisement contains j’s (m − 1)th counters and i’s (n + 3)th advertisement contains j’s mth and (m + 1)th counters), is clearly equal to the difference between the amount of bytes that flowed on interval [Tj (m + 1), Ti (n + 3)) and on interval [Tj (m − 2), Ti (n + 1)). Definition 11. Let F X iij (n) (resp. F X iji (n)) be i’s end flow on link (i, j) (resp. (j, i)), i.e. the quantity expressed by: ∀i, j, ∀n, ∀(k, l),
i i F X ikl (n) = Xkl (Ti (n)) − Xkl Ti (n) − Δij (n) .
(10)
j i Theorem 1. If Xkl (t) = Xkl (t) (for any i, j, (k, l) = (i, j) or (k, l) = (j, i) and any t), the summed values of desynchronized link balances over an interval of sequence numbers [n, n + M ] are exactly:
∀i, j, ∀n, ∀M ≥ 0, ∀(k, l),
n+M
BX ikl (p) = F X ikl (n + M ) − F X ikl (n − 1) . (11)
p=n
Proof. By induction on M ≥ 0. The case of M = 0 is trivially shown: i i ∀i, j, ∀n, ∀(k, l), BX ikl (n) = Xkl Ti (n) − Xkl Ti (n) −Δij (n) (12) j j i − Xkl Ti (n−1) + Xkl Ti (n−1) −Δj (n−1) . j i The induction hypothesis holds since we have that Xkl (t) = Xkl (t).
From the expression of (11), bounds on the accumulated desynchronized link balances can be expressed as follows.
Resilience to Dropping Nodes in MANETs with Link-State Routing
105
j i Theorem 2. If Xkl (t) = Xkl (t) (for any i, j, (k, l) = (i, j) or (k, l) = (j, i) and any t), then the accumulated desynchronized link balances are bound in the q n+M following way: i X Xi ∀i, j, ∀n, ∀M ≥ 0, ∀(k, l), max B kl (p) − F kl (q) ≤ BX ikl (p) q∈[n,n+M ]
p=n
≤
min
q
q∈[n,n+M ]
p=n
BX ikl (p)
+ F X ikl (n + M ) .
(13)
p=n
The proof of Theorem 2 is straightforward but omitted for brevity. Definition 12. Let Γji (n), be the minimum difference in time between the instant Ai (n) is sent and first j’s advertisement set was received by i since Ai (n−1) was sent. ∀i, j, ∀n : Sij (n) = ∅, Γji (n) = Ti (n) − min Tj (m) (14) i m∈Sj (n)
i ˙i − In Ai (n), the quantities X˙ ij (T− i (n)) and Xji (Ti (n)) are i’s claim about how much has flowed on links (i, j) and (j, i) respectively for each class X, during interval [Ti (n−1), Ti (n)). If that advertisement also contains at least one reverse j i AVC tuple for the links (i.e. Sij (n) = ∅), then the quantities X˙ ji (T− i (n) − Γj (n)) j − i ˙ and Xij (Ti (n) − Γj (n)) are j’s corresponding claim on interval [Ti (n − 1) − Δij (n − 1), Ti (n) − Γji (n)).
Definition 13. Let Lij (n) and Nij (n) be the sequence numbers defined as follows. ∀i, j, ∀n,
Lij (n) = max m : m ≤ n ∧ Sij (m) =∅ Nij (n) = min m : m > n ∧ Sij (m) =∅
(15)
It appears that we have the following properties: ∀i, j, ∀n, Ti (n) − Δij (n), Ti (n) ⊆ Ti Lij (n) − 1 , Ti (n) Ti (n) − Δij (n), Ti (n) ⊆ Ti (n) − Δij (n), Ti Nij (n) − Γji Nij (n) .
(16)
It immediately follows that bounds for the end flow can be expressed in terms of differential values of counters contained in advertisements. ⎞ ∀i, j, ∀n, ∀(k, l), ⎛ n − i i i i ˙j ⎠ (17) F X ikl (n) ≤ min ⎝ X˙ kl T− i (p) , Xkl Ti Nj (n) − Γj Nj (n) p=Lij (n)
If there is no discrepancy between i and j’s counters about link (k, l) (either (i, j) or (j, i)), then the bounds on the accumulated desynchronized link balances of (13) are verified. Even more so if upper bounds of the end flows from (17)
106
I. Gawędzki and K. Al Agha
are used instead of their actual values. In the following we call this verification the link coherence check. When such a check fails, the absolute value of the excess of accumulated desynchronized link balances with respect to the (loose) bounds is itself a lower bound on the amount of actual discrepancy, which is used directly in the second phase of the solution (detailed in Sect. 3.4). Then the corresponding accumulated values have to be reset to zero and the bounds to be initialized anew upon reception of the next advertisement. 3.4
Distrust System
A failed check is a proof of counter discrepancy, caused by dropped data traffic or false AVCs. Since usually some data packet loss is to be legitimately expected, a check failure should not be a direct reason for the exclusion of nodes. Nodes that drop data traffic should thus be avoided if possible, but not excluded. In the second phase of the solution, tests from the first phase are used to maintain a distrust metric on nodes which is used for path calculation. Unlike in usual trust or reputation systems, this metric cannot be individually maintained by each node, based on first-hand observations combined with second-hand observations from neighbors. The metric has to be uniform across all the nodes, so that every node tends to know of the same value for any given node in the topology, otherwise hop-by-hop routing may not be loop-free. Therefore, the metric is a combination of all the nodes’ local observations, diffused in the network. The local observations (failures to pass checks from the first phase) are used to maintain a local degree of distrust. This value is initially zero and each time a check fails, it is incremented as follows: Di ← max(1, Di ) · 1 + Li · r+ , (18) where Di , Li and r+ are respectively the degree of distrust in i, the lower bound on the amount of actual discrepancy and the ratio used as a parameter of the system set to how fast a degree has to increase. The value recovers over time in the following way: Di ← max 0, Di − Δt · r− , (19) where Di , Δt and r− are respectively the degree of distrust in i, the interval of time elapsed since last update and the ratio used as a parameter of the system set to how quickly a degree has to decrease with time. The local degree of distrust is diffused to other nodes, to allow them to compute the distrust metric for each other node. To make the calculation resilient to slander, we propose to combine the different degrees by calculating a kind of median value, which is insensitive to pathological samples that deviate too much. Using the local degrees of distrust directly is too simplistic and we require nodes to advertise a confidence factor along. That factor is used to enable each node to say to what extent its degree has to be taken into account in the calculation of the median. It is based on the amount of traffic that the observed
Resilience to Dropping Nodes in MANETs with Link-State Routing
107
node supposedly transmitted, according to its counters. The confidence factor increases with traffic: ci ← ci + Ti · r+ (20) (with ci , Ti and r+ being respectively the confidence factor for Di , the amount of traffic of i and the ratio used as a parameter of the system set to how quickly the confidence has to grow) and decreases with time passing: ci ← max(0, ci − Δt · r− )
(21)
(with ci , Δt and r− being respectively the confidence factor of Di , the interval of time elapsed since last update and the ratio used as a parameter of the system set to how quickly the confidence has to decrease with time). This way, the more (alleged) traffic goes through a node, the higher the confidence factor of its neighbors in their degree of distrust in that node. The value of the confidence factor that is actually advertised is required to be in the interval [0, 1), Ci = 1 −
1 , 1 + ci · ra
(22)
where Ci , ci and ra are respectively the advertised confidence factor of Di , the (internal) confidence factor of Di and the ratio used as a parameter of the system set to how quickly an advertised confidence factor has to come close to 1. The actual calculation of the metric based on individual couples (Dij , Cij ) (distrust and associated confidence in i diffused by j) is a weighted median: ∀i,
Di1 , Ci1 , . . . , (Din , Cin ) , j 1 j Ci ≤ · C 2 j i j j:Di <Wi
and
Cij ≤
j:Dij >Wi
1 j · C , (23) 2 j i
where Wi is the combined metric for node i. A simple route calculation using a shortest path algorithm on the global topology graph is to set the weight wij of each link (i, j) to 1 + Wi (instead of 1 for a simple hop-count metric).
4 4.1
Performance Evaluation Simulation Model
We have implemented our solution on top of a model of the OLSR protocol for the OPNET 12.0 simulator. Mobile nodes move on an area of 1000 m × 1000 m, with constant velocity (chosen uniformly on [0, 1] m/s) and constant direction (chosen uniformly on [0, 2π)) during an interval of time chosen exponentially with rate 1/600 per second. Data packets are generated exponentially with rate 5 per second, source and destination are chosen uniformly and data length is chosen uniformly between 40 and 1500 bytes. Cheaters, also chosen uniformly among the
108
I. Gawędzki and K. Al Agha
nodes, drop data packets with a parametrized probability. A IEEE 802.11 MAC layer is used on all nodes with 11 Mbps carrier, 50 mW transmission power, flow control (RTS/CTS) and default power thresholds (-85 dBm for carrier sense and -70 dBm for reception, resulting in ranges of respectively 1200 m and 214 m). The method presented in Sect. 3.3 and 3.4 has been implemented, along with a simple retransmission protocol for lost advertisements (omitted here for brevity), with r+ = 1/50, r+ = 1, r− = r− = 1/10 and ra = 10−6 . The MPR selection heuristic has been adapted so as to prefer neighbors with lower local distrust (details omitted here as well). MPRs diffuse local degrees of distrust and confidence factors of their selectors in TC messages. Cheaters do slander by always advertising a very high degree of distrust and a confidence factor of 1. The data packet delivery rate (total received data packets over total generated data packets) has been measured in each run and compared to several reference runs: in the No Cheater run, plain OLSR is used and the drop probability is forced to zero to see what OLSR achieves at best without cheaters; in the Plain run, plain OLSR is faced with non-zero drop probability to see how bad it does alone; in the Known run, OLSR has an oracle telling which node is a cheater and routing table calculation is performed as suggested at the end of Sect. 3.4 with Wi = 9 for each cheater i. That last reference run is used to see what performance could be achieved at best. Cheaters that intentionally drop data packets have many possible ways in which they can manipulate their counters. Among possible strategies, we have chosen four different ones: increment counters as though the packets were forwarded indeed; increment counters on all outgoing links so that the total added sum is the amount of lost data bytes; do not increment counters on outgoing links; increment counters only for every second packet. 4.2
Simulation Results
In the first batch of simulations, there were 100 nodes with 10% of cheaters. We have checked that the system stabilizes pretty quickly and after a few dozen seconds, the delivery ratio of our method is stable (though we checked for up to 10 1.0 0.9 delivery ratio
delivery ratio
0.9
0.8 Known Average Plain
0.7
0.8 0.7 0.6
No Cheater Known
Average Plain
0.5 0.25
0.5
0.75
drop probability
1.0
25 (3)
50 (5) 75 (8) total nodes (cheaters)
100 (10)
Fig. 2. Delivery ratio: with fixed density of 100 nodes and variable drop probability (left); with variable density and fixed drop probability of 1.0 (right)
Resilience to Dropping Nodes in MANETs with Link-State Routing
109
1.0
delivery ratio
0.8 0.6 Known Average Plain
0.4 0.2 0
5
10
15
20
25
30
35
40
45
50
55
60
percentage of cheaters
Fig. 3. Delivery ratio vs. cheaters: 1.0 drop probability and a total of 100 nodes
hours) and much closer to the Known case than to the Plain one. Lowering the drop probability, apart from raising the Plain curve, only lengthened by a small factor the time required for the delivery ratio to be as close to the Known curve (approximately 3 minutes for a drop probability of 0.25). The average delivery ratios of the Plain, Known and the average of the four cheating strategies (which results turned out to be very similar) after one hour of simulation, with 100 nodes, 10% cheaters with 1.0 drop probability, are presented in Fig. 2 (left). It appears clearly that in dense networks, the performance of our method sticks to the Known reference. To evaluate the performance of our method with respect to varying network density, we have run a batch of simulations with a different total number of nodes but a (almost) constant ratio of 10% of cheaters, each dropping with a probability of 1.0. The results presented in Fig. 2 (right) show that while the delivery ratio degrades with decreasing density, the performance of our method is still very close to the Known reference. The reason why maximum achievable performance decreases with the density is that there are fewer and fewer alternative paths for a given destination, hence fewer ways to avoid the cheaters. A last batch of simulations has been run with a duration of 15 minutes, a total number of 100 nodes but a varying number of cheaters with 1.0 drop probability. Results show (see Fig. 3) that our method improves the delivery ratio significantly, but less and less than the Known reference as the number of cheaters increases. 4.3
Discussion
Hughes et al. strongly criticized [8] the use of the principle of flow conservation as a way to detect malicious nodes in a network. They presented a number of attack scenarios which make simplistic approaches fail anyway. In our solution, we require all packets to be checked for integrity and their source address to be authenticated by all intermediate nodes, to exclude the possibility of packet modification or forgery going unnoticed. Some attacks, like “ghost routers” or the ones based on the reactivity of link-state routing protocols,
110
I. Gawędzki and K. Al Agha
are targeted at the routing protocol itself, which we assume here to be already protected. Note that the “kamikaze” attack, in which a malicious node intentionally advertises false counter values in order to be excluded along with some of its neighbors is simply handled by our solution, in which nodes are never excluded.
5
Conclusion
We have presented a way to augment a link-state routing protocol to make it resilient to the presence of nodes intentionally dropping data traffic. The method consists in three parallel operations: detect flow non-conservation on neighboring nodes, maintain a degree of distrust in all checked nodes, combine all degrees of distrust into a metric for routing table calculation. The method is very little intrusive into the system, provided that necessary cryptographic tools are available and that the routing protocol itself is protected. It is independent of OSI Data Link and Physical layers which makes it easier to implement and workable with different hardware setups (unidirectional antennae, multiple interfaces, etc). The method showed satisfactory performance, very close to an ideal case in which all cheating nodes are known to an oracle. Among the possible future works, we intend to explore the possibility of making the method work even in the presence of colluding cheaters. The interaction with some intrusion detection system can also be studied, in order to counter the “premature aging” attack.
References 1. Avramopoulos, I., Kobayashi, H., Wang, R., Krishnamurthy, A.: Highly secure and efficient routing. In: IEEE (ed.) INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies, March 2004, vol. 1, pp. 208–220. IEEE, Los Alamitos (2004) 2. Awerbuch, B., Holmer, D., Nita-Rotaru, C., Rubens, H.: An on-demand secure routing protocol resilient to byzantine failures. In: WiSE 2002: Proceedings of the 3rd ACM workshop on Wireless security, pp. 21–30. ACM Press, New York (2002) 3. Bradley, K.A., Cheung, S., Puketza, N., Mukherjee, B., Olsson, R.A.: Detecting disruptive routers: a distributed network monitoring approach. Network, IEEE 12(5), 50–60 (1998) 4. Buttyán, L., Hubaux, J.-P.: Stimulating cooperation in self-organizing mobile ad hoc networks. MONET 8(5), 579–592 (2003) 5. Clausen, T., Jacquet, P.: Optimized link state routing (OLSR) protocol. In: RFC 3626, IETF (October 2003) 6. Fourati, A., Agha, K.A.: A shared secret-based algorithm for securing the OLSR routing protocol. Telecommunication Systems 31(2–3), 213–226 (2006) 7. Hu, Y.-C., Perrig, A., Johnson, D.B.: Ariadne: a secure on-demand routing protocol for ad hoc networks. In: MobiCom 2002: Proceedings of the 8th annual international conference on Mobile computing and networking, pp. 12–23. ACM Press, New York (2002)
Resilience to Dropping Nodes in MANETs with Link-State Routing
111
8. Hughes, J.R., Aura, T., Bishop, M.: Using conservation of flow as a security mechanism in network protocols. In: IEEE Symposium on Security and Privacy, pp. 132–141 (2000) 9. Johnson, D.B., Maltz, D.A., Hu, Y.-C.: The dynamic source routing protocol (DSR) for mobile ad hoc networks for IPv4. RFC 4728, IETF (February 2007) 10. Just, M., Kranakis, E., Wan, T.: Resisting malicious packet dropping in wireless ad hoc networks. In: Pierre, S., Barbeau, M., Kranakis, E. (eds.) ADHOC-NOW 2003. LNCS, vol. 2865, pp. 151–163. Springer, Heidelberg (2003) 11. Mahajan, R., Rodrig, M., Wetherall, D., Zahorjan, J.: Sustaining cooperation in multi-hop wireless networks. In: 2nd Symposium on Networked System Design and Implementation, Boston, MA, USA (May 2005) 12. Marti, S., Giuli, T.J., Lai, K., Baker, M.: Mitigating routing misbehavior in mobile ad hoc networks. In: MobiCom 2000: Proceedings of the 6th annual international conference on Mobile computing and networking, pp. 255–265. ACM Press, New York (2000) 13. Perkins, C., Belding-Royer, E., Das, S.: Ad hoc on-demand distance vector (AODV) routing. RFC 3561, IETF (July 2003) 14. Raffo, D., Adjih, C., Clausen, T., Mühlethaler, P.: An advanced signature system for olsr. In: SASN 2004: Proceedings of the 2nd ACM workshop on Security of ad hoc and sensor networks, pp. 10–16. ACM Press, New York (2004) 15. Zhong, S., Chen, J., Yang, Y.R.: Sprite: A simple, cheat-proof, credit-based system for mobile ad-hoc networks. In: INFOCOM (2003)
3-D Localization Schemes of RFID Tags with Static and Mobile Readers Mathieu Bouet and Guy Pujolle Université Pierre et Marie Curie (UPMC) – Laboratoire d’Informatique de Paris 6 (LIP6) 104 avenue du Président Kennedy, 75016 Paris, France {Mathieu.Bouet,Guy.Pujolle}@lip6.fr
Abstract. RFID is an automatic identification technology that enables tracking of people and objects. We propose a scalable and robust 3-D localization method of RFID tags, derived in two schemes, that uses the diversity of pervasive environments to improve its accuracy. RFID readers are placed on the floor and ceiling of a room. In the first scheme, static and mobile tags are localized using only connectivity information obtained through this structure. The second scheme involves in addition mobile RFID readers. They are used here to refine the localization process by adding more inclusive constraints to the calculation. We study the impact of the number of static and mobile readers on the accuracy. We then show that the first scheme constitutes an upper bound for the second one. Furthermore, we observe that the second scheme does not require a lot of mobile readers and that it considerably improves accuracy. Keywords: RFID, localization, mobility, 3 dimensions, tracking.
1 Introduction Radio Frenquency IDentification (RFID) has recently become widespread for automatic identification and tracking. A RFID system is composed of two types of entities: RFID tags (or transponders) that store identity, and RFID readers (or detectors) that remotely retrieve these data. Tags can be passive: communications are supplied by the reader generally by backscattering its carrier wave, semi-passive: the tags embed a power source for their internal processes and communicate with readers like passive tags, and active: they embed a battery that supplies communications with readers and functionalities such as cryptography or sensor. Active tags are more expensive than passive tags but their communication range is far larger and they can have more advanced utilizations [1]. RFID is a key technology in future pervasive systems and services. Indeed, it provides essential context-aware functionalities such as automatic identification, tracking, and real-time inventory. By building RFID in networks, new management concepts could be conceived so as to fully integrate real-time status of items and people. However, all the benefits of this technology could be hugely increased if identification information was linked to positions. It would add another dimension to the context-awareness: real-time location and consequently mobility. For example, it could be used in home-networking and libraries to retrieve specific objects, control A. Das et al. (Eds.): NETWORKING 2008, LNCS 4982, pp. 112–123, 2008. © IFIP International Federation for Information Processing 2008
3-D Localization Schemes of RFID Tags with Static and Mobile Readers
113
access or monitor events. Matching identities with their locations would also allow the development of new strategies in autonomic systems for mobility control, resource allocation, security, service discovery. Classic RFID systems only provide coarse-grained localization. In fact, they are generally composed of readers placed in strategic locations; their purpose is to identify all the tags that pass in their read range. As a matter of fact, the precision of the position corresponds to the size of the cell formed by their read range. In this paper, our major contribution is to design a 3-D localization algorithm for mobile and static RFID tags which, contrary to other related works, is based only on connectivity information and which takes into account mobile RFID readers. Our algorithm offers fine-grained position estimation and is conceived so as to be cheap, robust, fast, and thus scalable. Moreover mobile readers are used to refine and improve the precision. Our model is simple: we consider a room, a warehouse, or a container (modeled by a hexahedron) and we deploy readers on the floor and ceiling. No assumption is done on the equipments and their quantity is reduced to the minimum in order to have a low-cost system. In the first scheme, an estimated position is computed for each mobile or static tag by using only connectivity information (which reader can detect the tag and which cannot) with a semi-infinitely constrained multivariable nonlinear method. Then, we present a second method, derived from the first one, to increase the localization precision when there are mobile readers. They are used to refine the first method by adding more constraints. This calculation requires more time and can only be applied on static RFID tags. First, we evaluate the impact of the number of readers on the precision of the localization, and we show that the accuracy of our method is very high when they are densely deployed. Then, we study the impact of the number of mobile readers on the performance of the second method, we underline the existence of an upper bound for the precision, and we point out a quick and impressive reduction of the localization error. The rest of the paper is organized as follows. First we discuss related work in Section 2. Then we explain the basic localization method and the improved localization method with mobile readers in Section 3. Simulation methodology and results are discussed in Section 4. Finally, Section 5 concludes the paper.
2 Related Work Localization is often considered as a widely studied domain. However, few methods have been proposed for RFIDs. In fact, this area has specific constraints and requirements. Contrary to localization in Mobile Ad-hoc NETworks (MANETs) or in Wireless Sensor Networks (WSNs) for which a lot of algorithms have been conceived, a RFID system is centralized because the computation capabilities of RFID tags are very limited. Besides they are composed of tens of thousands of tags that need to be treated quasi simultaneously. Moreover, they are usually deployed in indoor environments and their signal is harshly impaired. For example, UHF tags’ radio waves do not bounce off metal and have difficulties to penetrate water. The most famous indoor localization sensing method is called LANDMARC (LocAtioN iDentification based on dynaMic Active Rfid Calibration) [2]. It only
114
M. Bouet and G. Pujolle
localizes active RFID. The system is calibrated with the help of reference tags (additional tags that are fixed and whose positions are known by the system): a map including the Received Signal Strength (RSS) of each reader is built. Then, the system has to retrieve the RSS information from each tag to the readers and checks the map to find out its estimated position. Another well-known RFID localization system is SpotON [3]. It is also based on RSS measurements and uses them to estimate the distance between readers and tags. A central server aggregates the data and performs a trilateration to obtain the position of the tags. In [4], the authors also estimate the distance between tags and readers. However, this estimation is done through the Time Difference Of Arrival (TDOA) technique: the system measures the time-of-flight and deduces the distance according to the frequency and the inter-delay. This scheme is designed for fixed passive SAW RFID tags. Finally, in [5] the authors propose a 3-D localization scheme. It is founded on the assumption that readers have numerous power levels and on the deployment of reference tags. The read range of each reader is increased or decreased until the tag is detected. Then, thanks to the reference tags, an upper and a lower bound are obtained. The localization is done by mixing the bounds of all the readers and by applying a time-costly computation on the obtained area. Distance estimation through RSS, TOA or AOA is often very complicated in indoor environments because of signal absorption, indirect path, and interferences. These techniques can lead to large errors and require specific and thus expensive equipments. Moreover, the use of reference tags considerably increases the whole cost of the system and necessitates manual installation. Our localization method is based on very simple principles in order to be cost-effective, robust in harsh environments, and fast enough to be scalable when thousands of items need to be treated simultaneously. Indeed, we consider readers with basic capabilities, we do not use any additional equipment, and we localize tags using only connectivity information, no distance estimation is performed. General indoor localization systems have also been studied for a long time. The three more famous are Cricket [6], Active Bat [7], and Active Badge [8]. In the last system, Active Badges transmit unique infra-red signals every 10 seconds. When they pass close to a reader, they are detected. The position of the badge corresponds to the one of the reader that detected it, and the precision is the size of the cell. In Active Bat, ultrasonic receivers (or sensors) are placed on the ceiling. The system measures the time-of-flight from the node to each receiver and applies a classic trilateration. Finally, Cricket is also based on TDOA measurements but the difference is that the sensors send their coordinates to the node and it is the node that performs the trilateration to estimate its position. Several location methods for geographic routing and security mechanisms have also been proposed for MANETs and WSNs. The vast majority of them measures inter-node distance through the RSS, TDOA, or Angle of Arrival (AOA) technique. The others are based on hop count or inclusive and exclusive constraints. The readers are referred to [9] for more details. As explained earlier, those approaches address different problems than the one treated in this article but they offer a good comprehension and a solid basis for our approach. This also goes for the numerous methods that use reference RFID tags to localize mobile robots.
3-D Localization Schemes of RFID Tags with Static and Mobile Readers
115
3 Our Algorithm 3.1 System Setup First of all, we place RFID readers on the floor and ceiling of a room, a warehouse, or a container. These are modelized by a hexahedron whose length, width, and height are L, W, and H respectively as shown in Fig. 1. The readers are spaced from each other according to a certain gap S. The exact position of each reader is known by the system. Furthermore, they are supposed to be as basic as possible, that is, they have no different power levels, no directional antenna, no multiple antennas, and no synchronization. They can also have different read ranges. For easier comprehension, we consider they all have the same capacities and thus the same read range R, and we assume the signal transmission between readers and tags forms a sphere. Both active and passive tags can be located with this system.
Fig. 1. Our model
3.2 Basic Position Estimation This first method can locate both static and mobile tags and is based on the architecture presented in Section 3.1. The localization of tags only requires connectivity information: which readers are able to detect a given tag and which cannot. No distance estimation is performed. A mean position is calculated for each combination of intersection of readers as shown in Fig. 2. These mean positions correspond to the barycenter (also known as the center of gravity or the center of mass) of the different volumes formed by the intersection of the readers’ detection areas. Tags’ positions are estimated as follows. First, we define an error objective function δ i (x, y, z ) for each combination of readers: nj
δ i ( x, y , z ) = ∑ j =1
(x − x ) + (y − y ) + (z − z ) 2
j
2
j
2
j
.
(1)
116
M. Bouet and G. Pujolle
Fig. 2. A 2 dimensional intersection of readers
Where n j is the number of readers that form the combination,
( x, y , z )
are the
unknown coordinates of the barycenter (that will be the estimated position), and x j , y j , z j the coordinates of the reader j .
(
)
The error objective function is defined as the sum of the distance between the tag whose position is unknown and every reader able to read it. Then, as the number of readers on the floor is equal to the one on the ceiling, we can easily deduce if the tag is close to the floor, in the middle zone, or close to the ceiling. Indeed, if the tag is near the floor, more readers on the floor than on the ceiling will be able to read it. In that case, we can add extra information to the error objective function in equation (2). The same is done if more readers on the ceiling than on the floor are activated in equation (3). Nothing is done if the quantities are equal.
δ i ( x, y , z ) = δ i ( x , y , z ) +
(z − z
floor
)
δ i ( x, y , z ) = δ i ( x, y , z ) +
(z − z
ceiling
)
2
2
,
(2)
.
(3)
Finally, we use a semi-infinitely constrained multivariable nonlinear method to find the minimum of the error objective function presented in equation (1). It takes as parameter non linear functions, linear inequalities (the difference between the maximum read range R and the distance reader-unknown estimated position), and lower and upper bounds (the dimensions of the hexahedron). This well-known algorithm uses cubic and quadratic interpolation techniques to estimate peak values in the semi-infinite constraints. The error objective function has been defined so that its minimum corresponds to the barycenter of the volume: the calculated point will minimize the sum of the distances with all the readers plus the distance with the floor or the ceiling. The problem is stated as follows:
3-D Localization Schemes of RFID Tags with Static and Mobile Readers
117
min δ i (x, y, z ) subject to
( x, y , z )
⎧0 ≤ x ≤ L ⎪0 ≤ y ≤ W ⎪ ⎪0 ≤ z ≤ H ⎪ ⎨ ( x − x )2 + ( y − y )2 + ( z − z )2 − R ≤ 0 1 1 1 ⎪ ⎪... ⎪ ⎪ x − xn 2 + y − y n 2 + z − z n 2 − R ≤ 0 j j j ⎩
(
(
) (
Where (x1 , y1 , z1 ) , …, x n j , y n j , z n j
) (
(4)
)
) are the coordinates of the readers that formed
the volume. It is obvious that if the result for a given combination has already been computed, it is not necessary to recompute it. Consequently, this localization method can require a few calculations at the beginning but will be very fast when all the cases are treated. Actually, a solution would be to calibrate the room at the start, i.e. compute the corresponding mean position of every combination of reader. The localization would then be very fast: check the built map and retrieve the tag’s position. This process can be easily applied both on static and mobile tags since only connectivity information is used. 3.3 Position Estimation Enhanced by Mobile Readers In realistic pervasive environments, RFID readers can be mobile. We propose to use this diversity to improve our localization scheme. We lean this method on the first one: the room is equipped in the same way and the positions are estimated through the same process if no mobile reader is present. The mobile readers do not need to be complex or expensive since, once again, we deduce connectivity information from their location and their maximum read range. Their positions are known by the system. The interaction between the static reader structure and the mobile readers is shown in Fig. 3.
Fig. 3. A 2 dimensional intersection of static and mobile readers
118
M. Bouet and G. Pujolle
Consequently, the equation (4) becomes:
min δ i ( x, y, z ) subject to
(x, y , z )
⎧0 ≤ x ≤ L ⎪0 ≤ y ≤ W ⎪ ⎪0 ≤ z ≤ H ⎪ ⎪ ⎪ 2 2 2 ⎨ (x − x1 ) + ( y − y1 ) + ( z − z1 ) − R ≤ 0 ⎪ ⎪... ⎪ 2 2 2 ⎪ x − xn j + y − y n j + z − z n j − R ≤ 0 ⎪ ⎪ x − x mobile 2 + y − y mobile 2 + z − z mobile k k k ⎩
(
) (
(
(
) (
) (
Where x mobilek , y mobilek , z mobilek
)
) (
)
(5)
)
2
−R≤0
are the coordinates of the mobile reader that
detected the tag. Each time a mobile reader performs the reading of a tag, an inclusive constraint is added. Obviously, if the tag is static, this scheme can be easily applied and the zone is reduced quickly or not depending on the number of mobile readers. If the tag is moving slowly, it can also be localized with this variant but it is necessary to put timestamp on the constraints defined by the mobile readers and to remove the oldest ones. If the tag is moving quickly, the first localization method has to be applied.
4 Simulation 4.1 Simulation Methodology and Settings We have run extensive simulations in order to study the accuracy of our methods. The semi-infinitely constrained multivariable nonlinear algorithm has been implemented in several mathematic programs. We chose the one in the Optimization Toolbox available in Matlab [10]. We have defined different error measurements so as to evaluate the accuracy: • The mean error in 2 dimensions:
ε 2D =
(xreal − xestimated )2 + ( y real − yestimated )2
(6)
,
And its standard deviation σ 2 D . • The mean error in 3 dimensions:
ε 3D =
(xreal − xestimated )2 + ( y real − yestimated )2 + (z real − z estimated )2
And its standard deviation σ 3 D .
,
(7)
3-D Localization Schemes of RFID Tags with Static and Mobile Readers
119
• The mean error regarding the estimated height:
εh =
(z real − z estimated )2
,
(8)
And its standard deviation σ h . We dimensioned the hexahedron as follows:
L = 100m W = 100m . H = 3m
(9)
Where L, W, and H are the length, the width, and the height respectively. These values have voluntarily been chosen bigger than the dimensions of a typical room so as to take into account all the possible shapes. We choose realistic values for the read range of the static and mobile RFID readers:
R = 5m .
(10)
Finally, we implemented the Random WayPoint Mobility Model (RWP) [11] for the mobile readers. This model is used in many works since it is relevant for simulation of people displacements. The mobile readers randomly pick a destination in the hexahedron, go to it with a constant speed, when they reach it they pause, and then start the same process. It would be better if the mobile readers were not all at the same height but for an easier analysis of the performances, we chose to place them at 1 meter from the floor and to make them move with the speed of someone who is walking (5 kilometers/hour). Since the related works presented in Section 2 do not provide enough accurate hypotheses or use different configurations and different equipments (such as reference tags) from our model, we are not able to propose any comparison. 4.2 Results Fig. 4 shows the mean error in two dimensions (on x and y coordinates) after 300 seconds for different quantities of mobile readers. The accuracy of our basic localization scheme is below 1 meter when the static readers are spaced until 6 meters. A local peak is observed at 4.5 meters. This is due to the shape of the intersections of readers’ areas. Indeed, this value is just below the one of the radius. The readers on the floor and ceiling thus form very irregular zones, hence a higher error. This data constitutes an upper bound for the second localization method. After 300 seconds, with only one mobile reader the 2-D error is reduced until 40 centimeters compared to the static results. In the same time, if 5 mobile readers are used, the estimated error falls between 18 and 57 centimeters. Furthermore, the use of 10 or 20 mobile readers almost cancels the impact of the inter-reader spacing since after 300 seconds the error is bounded between 17 and 23 centimeters.
120
M. Bouet and G. Pujolle
1.4
0 mobile reader 1 mobile reader 5 mobile readers 10 mobile readers 20 mobile readers
1.2
Accuracy (m)
1 0.8 0.6 0.4 0.2 0 2
2.5
3
3.5 4 4.5 5 Inter-Reader Spacing (m)
5.5
6
6.5
6
6.5
Fig. 4. 2-D accuracy after 300 seconds 1.6
0 mobile reader 1 mobile reader 5 mobile readers 10 mobile readers 20 mobile readers
Accuracy (m)
1.4 1.2 1 0.8 0.6 0.4 2
2.5
3
3.5 4 4.5 5 Inter-Reader Spacing (m)
5.5
Fig. 5. 3-D accuracy after 300 seconds
Fig. 6 shows the mean error on the estimated height. It is limited between 39 and 61 centimeters. When the readers are densely deployed, the shapes of the intersections formed by the readers’ areas are not as regular as the ones when the inter-spacing reader is around 3 or 3.5 meters. The same phenomenon occurs in the cases where they are far one another. Consequently, the accuracy is better around 3 – 3.5 meters. The results for the second localization scheme are roughly the same. However, we can notice an improvement of the accuracy when mobile readers are used with static readers spaced of at least 4 meters. The impact of the mobile readers could be hugely increased if they were not all placed at the same height and if their read range were not all equal. For easier comparison between the different scenarios we chose identical mobile readers. Fig. 5 shows the 3-D mean error. The curbs have almost the same shapes than the ones for the 2-D results. This can be explained by the fact that our second localization method has only a light impact on the improvement of the height accuracy. Therefore,
3-D Localization Schemes of RFID Tags with Static and Mobile Readers
0.65
0 mobile reader 1 mobile reader 5 mobile readers 10 mobile readers 20 mobile readers
0.6
Accuracy (m)
121
0.55 0.5 0.45 0.4 0.35 2
2.5
3
3.5 4 4.5 5 Inter-Reader Spacing (m)
5.5
6
6.5
Fig. 6. Accuracy on height after 300 seconds
the evolution of the 3-D accuracy tends to follow the one in 2-D. The error is bounded between 57 and 159 centimeters for the first localization method. When 20 mobile readers are used, after 300 seconds the error falls between 48 and 61 centimeters (until 62% of reduction). The evolution of the accuracy through time is illustrated in Fig. 7. The impact of the mobile readers is visible since the beginning. After 30 seconds, the precision has been greatly increased and it goes on over time. Nevertheless, we can notice that improvement of the accuracy tends to decrease since the difference between the results at 240 seconds and at 300 seconds is only a few centimeters. Finally, in Fig. 8 we compare the impact of the number of mobile readers on the accuracy. Since for the first localization scheme there is no mobile reader, the error remains unchanged through time. In addition, two interesting remarks can be done. First, it is not necessary to use a lot of mobile readers. Indeed, the difference between 1.4
0s 1s 30 s 60 s 120 s 180 s 240 s 300 s
1.2
Accuracy (m)
1 0.8 0.6 0.4 0.2 0 2
2.5
3
3.5 4 4.5 5 Inter-Reader Spacing (m)
5.5
6
6.5
Fig. 7. Evolution of the 2-D accuracy with 10 mobile readers
122
M. Bouet and G. Pujolle
0.6
Accuracy (m)
0.5 0.4 0.3 0.2 0 mobile reader 1 mobile reader 5 mobile readers 10 mobile readers 20 mobile readers
0.1 0 0
100
200
300
400 500 Time (s)
600
700
800
900
Fig. 8. Evolution of the 2-D accuracy for an inter-spacing of 5 meters
the results for 5 mobile readers and the ones for 10 and 20 is not as important as expected. Secondly, as noticed in Fig. 7, the mean error in each scenario tends to rapidly converge over time. A residual error remains because of the inter-spacing between the static readers. To sum up, the results for the first localization scheme constitute an upper bound for the mean error of the second scheme. The use of mobile readers improves the accuracy. It depends on the number of mobile readers, the space between the static readers, and the execution time. For example, when inter-space is 5.5 meters and when 10 mobile readers are involved, the 3-D error falls from 92 to 59 centimeters (a reduction of 36%) after 300 seconds. Moreover, the results show that the error reduction converges quickly over time and that it does not require a lot of mobile readers.
5 Conclusion We have proposed a 3 dimensional localization method for static and mobile RFID tags and we have shown how to use diversity of pervasive environments, that is to say mobile RFID readers, to improve the positioning accuracy. We have chosen very simple properties so as to obtain a robust, fast, cost-efficient, and thus scalable method. Static RFID readers are placed on the floor and ceiling of a room. Tags’ positions are estimated by using only connectivity information in a semi-infinitely constrained multivariable nonlinear method. We then derive this scheme: mobile readers are used to refine the inclusive constraints and thus to improve the accuracy of static tags’ estimated location. Our results show that the precision of the first scheme is very satisfactory compared to the requirements. Furthermore, the use of mobile readers hugely reduces the localization error. The analysis also shows that it is not necessary to involve a lot of mobile readers and that the error reduction rapidly converges making the second localization scheme not only very quick but also very precise.
3-D Localization Schemes of RFID Tags with Static and Mobile Readers
123
References 1. Want, R.: An introduction to RFID technology. IEEE Pervasive Computing 5(1), 25–33 (2006) 2. Ni, L.M., Liu, Y., Lau, Y.C., Patil, A.P.: LANDMARC: indoor location sensing using active RFID. In: First IEEE International Conference on Pervasive Computing and Communications, pp. 407–415 (2003) 3. Hightower, J., Borriello, G., Want, R.: SpotON: An Indoor 3D Location Sensing Technology Based on RF Signal Strength. UW CSE Technical Report (2000) 4. Bechteler, T.F., Yenigun, H.: 2-D localization and identification based on SAW ID-tags at 2.5 GHz. IEEE Transactions on Microwave Theory and Techniques 51(5), 1584–1590 (2003) 5. Wang, C., Wu, H., Tzeng, N.-F.: RFID-Based 3-D Positioning Schemes. In: 26th IEEE International Conference on Computer Communications (INFOCOM), pp. 1235–1243 (2007) 6. Priyantha, N.B., Chakraborty, A., Balakrishnan, H.: The cricket location-support system. In: 6th Annual ACM International Conference on Mobile Computing and Networking (MOBICOM), pp. 32–43 (2000) 7. Ward, A., Jones, A., Hopper, A.: A New Location Technique for the Active Office. IEEE Personal Communications 4(5), 42–47 (1997) 8. Want, R., Hopper, A., Falcao, V., Gibbons, J.: The active badge location system. ACM Transactions on Information Systems 10(1), 91–102 (1992) 9. Gustafsson, F., Gunnarsson, F.: Mobile positioning using wireless networks: possibilities and fundamental limitations based on available wireless network measurements. IEEE Signal Processing Magazine 22(4), 41–53 (2005) 10. Matlab, http://www.mathworks.com/ 11. Hyytia, E., Lassila, P., Virtamo, J.: Spatial node distribution of the random waypoint mobility model with applications. IEEE Transactions on Mobile Computing 5(6), 680–694 (2006)
Performance Evaluation and Enhancement of Surface Coverage Relay Protocol Antoine Gallais and Jean Carle IRCICA/LIFL, Univ. Lille 1, INRIA Futurs, France {antoine.gallais,jean.carle}@lifl.fr http://www.lifl.fr/POPS
Abstract. Area coverage protocols aim at turning off redundant sensor nodes while ensuring full coverage of the area by the remaining active nodes. Connectivity of the active nodes subset must also be provided so that monitoring reports can reach the sink stations. Existing solutions hardly address these two issues as a unified one and very few are robust to non ideal physical conditions. In this paper, we propose a deep analysis and some enhancements of a localized algorithm for area coverage, based on Surface Coverage Relays (SCR) and able to build connected active nodes sets that fully cover the area. We first enhanced the critical phase of our protocol (the relay selection) and show that the number of active nodes can be drastically reduced. We then raise the issue of the robustness of the protocol once a realistic physical layer is simulated. Our algorithm proved itself to be an interesting solution as it remained able to still ensure high coverage level under realistic physical layer conditions. We also added the possibility to finely tune the overall proportion of active nodes through a new parameter used during local relay selection phases. Keywords: Wireless sensor networks, area coverage, configurable localized algorithm, realistic physical layer.
1 Introduction Wireless sensor networks are made up of hundreds of devices in which a battery, a sensing module and a wireless communication device are embedded. They are deployed over hostile or remote environments, in which they become one-use-only since their batteries cannot easily be replaced or refilled. Energy consumption is therefore balanced by taking advantage of the redundancy induced by the random deployment of nodes; some nodes are active while others are in sleep mode, thus using less energy. Such a dynamic topology should not impact the monitoring activity. The ensuing issue consists in the active nodes to fully cover the area. Furthermore, as monitoring reports should at least reach the sink stations, the set of active nodes should be connected. This is also known as the connected area coverage problem. This work focuses on a localized algorithm, considering first that the availability of a deciding central entity is a strong assumption and also willing to show that such an organization can be obtained from networks without any infrastructure. We proposed in [1] a fully localized solution to the connected sensor area coverage issue. Both a neighbor A. Das et al. (Eds.): NETWORKING 2008, LNCS 4982, pp. 124–134, 2008. c IFIP International Federation for Information Processing 2008
Performance Evaluation and Enhancement of SCR Protocol
125
detection phase and a relay selection phase are required to complete the activity decision process. In this article, we deeply study the relay selection phase, made from a new method described here. This latest solution allows us to strongly reduce the proportions of active nodes while not inducing any communication overhead nor any new information in control messages. Most of existing area coverage solutions rely on an ideal communication model (each node has a transmission threshold, beyond which no message may be directly sent). The radio channel randomness is hardly considered. We studied the robustness of our SCR protocol with such a new assumption. After showing that it was slightly impacted, we introduce a new parameter during the relay selection phase in order to vary the size of the relay set thus finely tuning the proportions of active nodes.
2 Preliminaries We assume that randomly deployed sensors are time-synchronized, static and positionaware. Several solutions have been studied to achieve these goals [2]. The location of a sensor node is used as its unique identifier. We also consider that sensors are able to determine whether an area is covered by a set of sensors or not. Various coverage evaluation schemes have already been used for that purpose [3,4]. 2.1 Communication and Sensing Models A wireless network is modeled by a graph G = (V, E), V being the set of vertices and E ⊆ V 2 the set of edges that the available communications. An edge between two vertices u and v exists if u is physically able to send a message to v. The neighborhood set of u, noted as N(u), is defined as: N(u) = {v ∈ V | v = u ∧ (u, v) ∈ E}.
(1)
Each sensor has a communication range Rc and a sensing range Rs . We denote by S(u) the area covered by a node u and S(A) the area covered by a set of nodes A = {a1 , a2 , . . . , an } such that:
i=|A|
S(A) =
S(ai ).
(2)
i=1
2.2 Radio Channel Model Given a graph G = (V, E), a communication range Rc and the Euclidean distance between nodes u and v dist(u, v), the unit disk graph model defines the set of edges E as: E = {(u, v) ∈ V 2 | u = v ∧ dist(u, v) ≤ Rc },
(3)
Yet, in a practical context, transmission quality varies over the time and a node u may be able to communicate with node v at time t, but not at time t+1. Each communication
126
A. Gallais and J. Carle
link has a probability to exist which is influenced by a lot of factors such as the emitting power or the distance between the emitter and the receiver. Many models exist and some generators have already been proposed to allow model generation from parameters such as the kind of material used or the localization of the sensors themselves (see [5] for instance). To replace the unit disk graph, we opted for the lognormal shadowing model thus transforming G into a weighted graph, where the weight of each edge (u, v) ∈ E is equal to the probability of correct reception p(dist(u, v)) for the two nodes u and v. An approximated function P(x) is described by Kuruvila et al. [6]: ⎧ ⎪ 1− ⎪ ⎪ ⎪ ⎪ ⎨ P(x) =
⎪ ⎪ ⎪ ⎪ ⎪ ⎩
( Rxc )2α 2
if 0 < x ≤ Rc ,
( 2RRcc−x )2α 2
if Rc < x ≤ 2 × Rc ,
0
otherwise,
(4)
α being a factor that highly depends on the environment and x being the considered distance. This function assumes that the probability of correct reception for the range Rc is always equal to P(Rc ) = 0.5. Fig. 1 illustrates this function for α = 2, which is frequently encountered in the literature. Being aware of the approximation that is made here, we are not pretending to use a highly realistic model. Yet, we believe that considering radio channel randomness during protocol analysis and simulation constitutes a first step towards facilitating further developments on real material.
3 Related Work Many papers have already addressed the problem of connected area coverage in wireless sensor networks once sensors are allowed to self-schedule their activity. Some have assumed a given topology to start the study, such as a grid for instance [7]. In [8], authors study some deployment patterns in order to ensure both coverage and connectivity once wireless sensors are deployed over a sensing field. Meanwhile, the deployment might be random thus forcing sensor devices to make decisions based on non predictable information. Tian and Georganas [9] have proposed a node scheduling scheme in which time synchronized and randomly deployed sensor devices regularly detect their neighbors and listen for retreat messages for a given timeout. A node can get passive if remaining neighbors fully cover its area. To ensure connectivity of the set of active nodes, a strong assumption is made regarding the ratio between sensing and communication radii (Rs ≤ Rc ). Such an assumption had already been used and proved as preserving network connectivity as long as area coverage was provided [3,4]. Recently, a randomized algorithm was proposed in [10]. Based on a Markov model, this algorithm allows each node to probabilistically turn off while preserving both coverage and connectivity. Yet, the need for a new analysis when considering non homogeneous settings might be an obstacle in real deployments where neighbor information is required to ensure coherent node behavior once the neighborhood is modified for any reason (mobility, failure).
Performance Evaluation and Enhancement of SCR Protocol
127
Unit disk graph 1
Lognormal shadowing
Probability of correct reception
0.8
0.6
0.4
0.2
0
0
0.5
1 Distance
1.5
2
Fig. 1. The two considered physical models (Rc = 1, α = 2)
4 Base of the SCR-CADS Protocol While coverage might not be a strict requirement for wireless sensor networks, connectivity among the set of monitoring nodes is crucial as every collected piece of information should be able to reach one of the sink stations. This is why we propose a new look at our SCR-CADS protocol which has been proved to ensure both connectivity and coverage in an original manner [1]. We show how this algorithm could be configured and especially what its resistance to new communication models is. Our solution consists in three consecutive phases (a neighbor discovery mechanism, a relay selection phase and a decision making process), each being detailed in this section. Regular neighbor discovery. A classical neighbor discovery phase is first required. At the beginning of each round, a hello message is sent by each node. It contains information such as its geographical position and a priority, assumed to be unique among the set of nodes. Relay selection. When considering node coverage, Jacquet et al. [11] have defined the notion of multipoint relay (MPR). Each node selects a subset of its neighborhood; the set of relays. For any given node u, this set, denoted as M P R(u), enables multi-hop communications with every 2-hop neighbors: MPR : V → V u −→ M P R(u) ∀u, ∃ MPR | N (MPR(u))\N (u) = N (N (u))\N (u),
(5)
V being the whole set of nodes. We can observe that M P R(u) = N (u) satisfies the relation. Yet, trying to have a MPR set as little as possible leads to diminishing the size of the dominating set, denoted as MPR-DS. Each node must send its own relay set to its whole neighborhood so that a simple decision rule can be made. Authors have proved that some rules were providing MPR-DS that were connected.
128
A. Gallais and J. Carle
As we aim at providing area coverage by connected sets, we have extended this solution to the problem of area coverage in wireless sensor networks. The relay selection phase has been modified. Each node computes its own relay set; this set must cover as large an area as the whole set of neighbors. This set is called Surface Coverage Relay (SCR) set. We defined a SCR function for this purpose: SCR : V → V u −→ SCR(u) SCR(u) standing for the subset of N (u) for which the property holds: ∀u, ∃ SCR | S(SCR(u))\S(u) = S(N (u))\S(u).
(6)
Each node must be able to compute its SCR set. Finding the subset of minimal size is equivalent to the minimum set cover problem, which is NP-complete [12]. This is why heuristics have to be designed in order to compute SCR sets that are as optimal as possible considering the number of nodes involved. Initially, a heuristic based on centroid computation was used [1]. In this article, we propose a new heuristic to compute SCR sets. Each node starts with an empty SCR set. Then, step by step, a neighbor is added to the SCR set if and only if it covers a portion of area yet uncovered by the SCR set. To get interesting subsets, at each step, the neighbor that brings the more new coverage should be added. Ideally, the neighbors should therefore be ordered according to their coverage potential regarding previously observed nodes. The first heuristic was based on a simple idea; at each step, we try to find the node that should bring the more coverage. To avoid heavy computation, we opted for the one whose location is the furthest from the center of mass of already selected relays (every relay having the same mass). It turned out that still large sets were computed. We now propose a new heuristic for selecting the relays, based on a simple intuition; the furthest neighbor is the one that covers the largest portion of area outside the sensing zone of the selecting sensor. Neighbors are therefore ordered according to their distance to the selecting node. The furthest is added to SCR set, then the second furthest is evaluated and so on. Note that for any heuristic, considered neighbors have to be distinguished in case of equality when facing the choice criterion. Which node is considered first is determined with a simple random function. Once SCR sets have been computed, each node has to decide its own activity status. We now explain the decision rule used for this purpose. Making activity decision. In the MPR-DS protocol [11], nodes apply a simple rule to decide their status (dominant or not). This rule is based on a key, assumed to be unique among the set of nodes. Definition 1. Every node u whose key is the lowest among the neighborhood or which belongs to the relay set of the neighbor with the lowest key must be active. As already shown in [11], if relay sets are computed so that the property 5 holds, then the induced set of active nodes is connected. We have already proved that using this rule
Performance Evaluation and Enhancement of SCR Protocol
129
with SCR sets was providing a set covering as large an area as the whole set of nodes. It is also obvious that SCR sets are MPR sets once Rs = Rc since 2-hop neighbors are necessarily located within one or several sensing areas of the 1-hop neighbors. This means that the covering set is also connected once we every activity decision has been made. Now that we have presented SCR-CADS and a new heuristic to compute SCR sets, we are evaluating this protocol under several communication models. Indeed, it has already been largely spread that protocols evaluated under ideal communication assumptions (i.e. the unit disk model) were more prone to failures or to dysfunction once used in practice (see [13] for some instances among area coverage protocols). The remaining of this article is therefore focused on the analysis of SCR-CADS protocol and its performances with a realistic physical layer for communications.
5 Performance Evaluation We have simulated only homogeneous sensor networks. Experimental results were obtained from randomly generated connected networks with a discrete event simulator. Nodes are deployed over a 50 × 50 rectangle area, considering a Poisson point process of intensity λ > 0. We define the density d of the network to be the average number of nodes in a given communication area: we thus have d = λ × πRc2 . Both the communication range (Rc ) and the sensing radius (Rs ) are fixed at 10. Simulations were launched over densities varying from 20 to 90 nodes per communication zone, with a step of 10. For each density, the number of performed iterations is adjusted so that 95% of the results are in a sufficiently tight confidence interval. Each iteration consists of rounds. Each round starts with the neighbor discovery phase, followed by the SCR sets computation and the decision making process. A sensing area is modeled as a disk while the communciation model varies (unit disk model or a realistic physical layer). When nodes have to compute the area covered by a given neighbor, they use a coverage evaluation scheme based on a disks intersections theorem, already applied in [3,4]. A round ends with the sensing period which involves every node that has decided to be active. We essentially measure the percentage of active nodes and the percentage of preserved coverage of original area. 5.1 Under Ideal Communication Assumptions We give complementary results about the SCR protocol when simulated with ideal communication assumptions. By ideal, we mean that no message can ever be lost, neither due to message collisions nor to the communication environment itself. Area coverage and connectivity. As already mentioned, the algorithm has been proved as preserving both area coverage and connectivity of the set of active nodes. We therefore focus on the size of the active nodes sets in order to evaluate the impact of the heuristic used during the relay selection phase. Size of SCR sets. We have observed the average size of the SCR sets in order to compare the performances of the original heuristic with the ones the latest solution, based on distances. The size of the relay sets is a matter of prime importance first
130
A. Gallais and J. Carle
35
80 Distance−based heuristic Centroid−based heuristic
Distance−based heuristic Centroid−based heuristic 70
60 25
Active nodes (%)
Average size of SCR sets
30
20
15
50
40
30 10
20
5
10 20
30
40
50 60 Network density
70
80
(a) Diminishing the size of relay sets.
90
20
30
40
50 60 Network density
70
80
90
(b) Reducing the proportion of active nodes.
Fig. 2. Main advantages of the distance-based heuristic for relay selection
because the number of active nodes is strongly linked to these and second because they determine the communication overhead induced by the protocol. Concerning the first point,every node whose key is the lowest among its neighborhood is necessarily active. This number does not vary as long as the network density remains identical. Yet, the larger the relay sets, the higher the probability for a node to belong to the SCR set of the neighbor with the lowest key and so to become active. Concerning the second point, as relay sets must be sent to every 1-hop neighbor, the less large they are, the better for the communication overhead and thus the energy consumption. We could observed that the distance-based heuristic was actually performing better than the centroid-based one. As shown on Fig. 2(a), the average size of the SCR sets generated by the distance-based heuristic varies from roughly 8 neighbors to 11, respectively for densities 20 and 90, while the centroid-based method leads to 11 neighbors selected as relays at density 20 and nearly 24 at density 90, that is more than twice the size obtained by our distance-based heuristic. As already mentioned, the size of the relay sets straightly impacts the number of active nodes. As our new heuristic allows us to considerably reduce this size, we are now looking to what extent this improved relay selection impacts the average number of active nodes that are involved at every round. Active nodes. Figure 2(b) shows the average number of active nodes versus the network density. As expected, the percentage of active nodes decreases as the network density increases; the more nodes there are, the less the proportion of required sensors to achieve full coverage of the area. Interestingly, we can observe that the centroid-based heuristic leads to 24.7% of active nodes at density 90 while the distance-based method lowers this result to only 13% for the same density. We therefore obtained very interesting results with this new method. 5.2 Under Realistic Physical Layer Assumptions We now try to evaluate the SCR-CADS protocol with a realistic communication model. The goal for such an investigation is twofold. First, we aimed at testing the robustness
Performance Evaluation and Enhancement of SCR Protocol
131
of this algorithm and then some potential enhancements were to be implemented and also evaluated. Introducing a more realistic physical layer leads to more channel randomness, that is communication links that are probabilistic; two nodes can communicate with a given probability depending on the distance that separates them. Some area coverage protocols have already been studied under this new assumption and we aim at evaluating SCR protocol also. In our algorithm, once the relay sets have been computed, they are sent so that every node can make its activity decision from the rule previously described in 4. The so computed set of active nodes is connected and covers as large an area as the whole set of nodes once the unit disk model is used. When a realistic physical layer is used, we could observed some changes. Area coverage. Figure 3(a) shows the average percentage of covered area by the sets of active nodes computed by our SCR protocol. We can observe that while area coverage was fully preserved with an ideal communication model, this property does no longer holds under our new assumptions. Area coverage goes from a bit more than 95% at density 30 to less than 90% at density 80. Yet, this loss of coverage is not as important as we could have expected, and especially not as dramatic as the ones we could already observed with other protocols [13]. This shows an inherent robustness for our SCR protocol. Let us detail the reasons why the impact is that low. During the neighbor discovery phase, hello messages from some of the theoretical 1-hop neighbors may not be received by a given node u. Yet, this actually increases the probability for u to evaluate its own key as being the lowest among its neighbors. Then, the less neighbors are discovered, the higher the probability for u to get active, the worst case being no hello message ever received and u having an empty neighbor table, thus necessarily deciding to be active. In such a case, we would have all nodes being leaf and thus active, which is not the case here as some coverage losses have still been recorded. We may now focus on the relay selection phase. Once relays have been selected, SCR sets are sent to the neighbors. If some of these messages are never received by a given node u, then it results in some nodes being aware of only a subset of its real SCR selectors. If one of these potentially missed selectors is the neighbor with the 25 Distance−based heuristic Centroid−based heuristic 100 20
Active nodes (%)
Area coverage (%)
95
90
85
Distance−based heuristic Centroid−based heuristic
15
10
80 5 75
70
0 30
40
50
60 Network density
70
(a) Coverage loss.
80
90
30
40
50
60 Network density
70
80
90
(b) Reduction of active nodes (%).
Fig. 3. SCR-CADS algorithm and a realistic physical layer (LNS, see formula 4, with α = 2)
132
A. Gallais and J. Carle
lowest key so far, such a wrong reception leads to u not knowing it has been selected by its neighbor with the lowest key, which would have meant it had to be active. In such a case, u decides to be passive and therefore jeopardizes area coverage. This is why some coverage losses are observed on Fig. 3(a). However, note that if a relay message is received from a yet unknown node whose key is the lowest among already collected ones, then the receiving node must consider this message as a hello message. It must also check if it has been selected as a relay by this node. This demonstrates the inherent robustness of SCR protocol since only coverage losses may happen only in case the relay message of the neighbor with the lowest key (and whose previous hello message was received) was never received. This means that only this message is crucial while others can only bring some new information that could help nodes make the right activity decision. Active nodes. We also observed to what extent the average percentage of active nodes was impacted by our new physical layer assumptions. Generally, when some coverage losses occur, it is either caused by a decrease of the number of active nodes or by a spatial incoherence (as many active nodes but concentrated on a given region at the expense of another one which is left uncovered). The latter case can hardly take place thanks to the homogeneity of both our deployment and our random processes used during key computation. Indeed, fig. 3(b) shows that the percentage of active nodes is largely decreased (from less than 10% at density 30 to only 2% at density 90) when the distance-based heuristic is used. Although this tremendous drop of the percentage of active nodes could lead us to think that large coverage holes have occurred, we have already observed that the impact on area coverage was minor. The SCR-CADS protocol is inherently robust and does not much suffer from loss of active nodes since the remaining ones have self-elected with a coherent local process. 5.3 Tending to More Robustness and Customization of SCR Protocol Although the impact of a realistic physical layer is not important on area coverage, we could observe that the number of active nodes was largely decreased. As already mentioned, the percentage of active nodes is very much induced by the average size of the relay sets. We are now trying to tune the relay selection made by each node in order to be able to tune the global percentage of active nodes, and also the area coverage. We therefore introduced a coverage parameter, denoted as SCR COV , which stands for the number of relays that should cover any portion of the sensing area of a neighbor currently evaluated for potential selection. Every neighbor is now added to the set of relays if and only if its sensing area is not k-covered by already selected relays, with k being SCR COV . Several definitions of k-coverage exist in the literature. Our approach is to consider a k-covered piece of area as soon as k distinct sensor devices are able to sense it. This should help us to raise the proportions of active nodes as relay sets could be made larger. By this way, the resistance to some communication anomalies should be obtained thanks to the redundancy induced in the set of monitoring nodes. Note that this solution solely requires a modified coverage evaluation scheme.
Performance Evaluation and Enhancement of SCR Protocol
133
100
30
95
25 Active nodes (%)
Area coverage (%)
35
90
85
SCR_COV=2 SCR_COV=3 SCR_COV=4
20
15
80
10
75
5
70
SCR_COV=2 SCR_COV=3 SCR_COV=4
0 30
40
50
60 Network density
70
80
90
30
40
50
60 Network density
70
80
90
(a) Increasing robustness to radio channel ran- (b) Configurable proportions of active nodes domness. with enhanced relay selection. Fig. 4. Configurability of SCR-CADS protocol (LNS, see formula 4, with α = 2)
Area coverage. The prime goal of our SCR COV parameter is to be able to better resist to message loss. Figure 4(a) shows area coverage versus network density, with SCR COV ∈ {2, 3, 4} when the distance-based heuristic is used. As long as SCR COV > 1, area coverage is at least 95%. This shows that, even in presence of a realistic radio channel, our algorithm can provide satisfying results in terms of area coverage. Our new parameter may also help us to customize the relay selection more finely. Until now, we were only using our two selection heuristics. The problem with such a method is that dynamically modifying the way a relay selection is conducted by a node would require changing the code it actually runs. Given the hardware constraints of the target devices, it would be more convenient to interact with the algorithm by the means of a simple parameter. Active nodes. We observed to what extent the SCR COV value was able to impact the proportions of active nodes. The average percentage of active nodes is shown on Fig. 4(b), for several SCR COV values. When SCR COV = 2 (which is sufficient to ensure more than 95% of covered area), we have between 17% and 4% of active nodes. This shows that our SCR COV not only deserves to be used to improve area coverage but also to finely tune the proportions of active nodes.
6 Conclusion We have enhanced our SCR-CADS protocol in order to have a more efficient relay selection that fits in today’s requirements for wireless sensor networks algorithms. We have shown that our algorithm, originally designed under ideal communication assumptions, could work properly with a realistic physical layer, maintaining a high coverage level. We then introduced a new parameter during the relay selection, thus enabling full coverage in case this would be strongly required by the application. This allows to finely tune the proportions of active nodes as we tend to a more configurable protocol. Future work will focus on characterizing connectivity under more realistic communication assumptions. We also aim at observing the impact of both synchronization and
134
A. Gallais and J. Carle
localization errors which could be induced either due to the environment or to the used algorithm itself.
Acknowledgments This work was partially supported by a grant from CPER Nord-Pas-de-Calais/FEDER TAC COM’DOM, CNRS National platform RECAP.
References 1. Carle, J., Gallais, A., Simplot-Ryl, D.: Preserving area coverage in wireless sensor networks by using surface coverage relay dominating sets. In: Proceedings of IEEE Symposium on Computers and Communications (ISCC), Cartagena, Spain, pp. 347–352 (2005) 2. R¨omer, K.: Time Synchronization and Localization in Sensor Networks. PhD thesis, ETH Zurich, Switzerland (2005) 3. Zhang, H., Hou, J.C.: Maintaining sensing coverage and connectivity in large sensor networks. Ad Hoc and Sensor Wireless Networks journal (AHSWN) 1, 89–123 (2005) 4. Xing, G., Wang, X., Zhang, Y., Lu, C., Pless, R., Gill, C.: Integrated coverage and connectivity configuration for energy conservation in sensor networks. ACM Transactions on Sensor Networks (TOSN) 1(1), 36–72 (2005) 5. Cerpa, A., Wong, J.L., Kuang, L., Potkonjak, M., Estrin, D.: Statistical model of lossy links in wireless sensor networks. In: Proceedings of International Symposium on Information Processing in Sensor Networks (IPSN) (2005) 6. Kuruvila, J., Nayak, A., Stojmenovi´c, I.: Hop count optimal position based packet routing algorithms for ad hoc wireless networks with a realistic physical layer. In: Proceedings of IEEE Mobile Ad hoc and Sensor Systems (MASS), Fort Lauderdale, FL, USA (2004) 7. Shakkottai, S., Srikant, R., Shroff, N.: Unreliable sensor grids: Coverage, connectivity and diameter. In: Proceedings of IEEE International Conference on Computer Communications (INFOCOM), San Francisco, CA, USA (2003) 8. Liu, C., Xiao, Y.: Random coverage with guaranteed connectivity: Joint scheduling for wireless sensor networks. IEEE Transactions on Parallel and Distributed Systems (TPDS) 17(6) (2006) 9. Tian, D., Georganas, N.D.: Connectivity maintenance and coverage preservation in wireless sensor networks. AdHoc Networks Journal (Elsevier Science), 744–761 (2005) 10. Yener, B., Magdon-Ismail, M., Sivrikaya, F.: Joint problem of power optimal connectivity and coverage in wireless sensor networks. Wireless Networks 13(4), 537–550 (2007) 11. Adjih, C., Jacquet, P., Viennot, L.: Computing connected dominated sets with multipoint relays. Ad Hoc and Sensor Wireless Networks journal (AHSWN) 1(3), 27–39 (2005) 12. Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum Press, New York (1972) 13. Gallais, A., Ingelrest, F., Carle, J., Simplot-Ryl, D.: Preserving area coverage in sensor networks with a realistic physical layer. In: Proceedings of IEEE International Conference on Computer Communications (INFOCOM), Anchorage, AK, USA (short paper, 2007)
On Extending Coverage of UMTS Networks Using an Ad-Hoc Network with Weighted Fair Queueing R. El-Azouzi1 , R. El-Khoury1, A. Kobbane1,2 , and E. Sabir1,2 1
LIA/CERI, Universit´e d’Avignon, Agroparc BP 1228, Avignon, France 2 LIMIARF, Universit´e Mohammed V Rabat-Agdal, 4 Av. Ibn Battouta B.P. 1014, Maroc {rachid.elazouzi,ralph.elkhoury,abdellatif.kobbane, essaid.sabir}@univ-avignon.fr
Abstract. In this paper, we are interested in the interconnection between an ad-hoc network and UMTS system. In presence of two access technologies, new challenges arise and mobile host will have face multiple base stations or gateways with different utilizations. As a result, a user who needs to establish a voice call, prefers to be connected through UMTS and a user who needs to transmit a Best Effort traffic with high rate, prefers to be connected through ad-hoc network. The aim of that combination is to improve the coverage of cellular networks and increases the services which can be made available for mobiles. This combination also reduces transmission power for mobile hosts. Our main result is characterization of stability condition and the end-to-end throughput using the rate balance. Numerical results are given and support the results of the analysis. Finally, we perform extensive simulation and verify that the analytical results closely match the results obtained from simulations. Keywords: Interconnection, cross-layer, routing, ad-hoc, UMTS, stability.
1
Introduction
In order to meet the increasing in data and user mobility, a considered amount of effort is tunneled towards the convergence of multi-service networks of diverse technologies. Next generation wireless networks (NGWN) will be heterogeneous radio access technologies such UMTS, WiMAx, WLAN, etc, coexist. However, the NGWN will be a joint radio resource management among multiple operators of different radio resource technologies [3]. In this paper, we are interested in the planning of ad-hoc networks in providing an improved cellular coverage of UMTS cellular networks and different services can be made available for nodes. Indeed, there exist several types of traffic that require different QoS. In presence of several access technologies, new challenge arises and mobile host will
This work was partially supported by ANR WINEM No. 06TCOM05 and Maroc Telecom R&D No. 10510005458.06 PI.
A. Das et al. (Eds.): NETWORKING 2008, LNCS 4982, pp. 135–148, 2008. c IFIP International Federation for Information Processing 2008
136
R. El-Azouzi et al.
face multiple base stations or gateway with different utilization. This opens the possibility of using the most appropriate multiple access types for each type of call. For example, for a network with a low bandwidth and high reliability access as UMTS, it is preferable to be used by a voice call. As a result, a user prefers to be connected through UMTS network which can offer higher reliability for particular services, even at a high cost. A multi-hop wireless ad hoc network is a collection of nodes that communicate with each other without any established infrastructure or centralized control. Many factors interact with each other to make the communication possible like routing protocol and channel access. Recently, wireless ad-hoc networks have been envisioned of commercial applications such as providing Internet connectivity for nodes that are not in transmission range of a wireless access point. Cellular network and ad-hoc networks should be considered as complementary systems. Hence, it is possible to use ad-hoc networks as an extension of the cellular networks like UMTS. Thus it is possible for a multihomed node to use different access technologies at different time to assure a permanent connectivity. As a result, potential benefits can be envisaged for UMTS cellular as : extend the cellular coverage, reduce the power transmission which implies the reduction of intra-cell and extra-cell interference. In the ad-hoc networks, new services can be made available as VoIP and streaming video. In this work we are interested in the interconnection between a MANET and a 3G system. In order to be able to connect to more than one base station (or network), a terminal should have at least two network cards. In the ad-hoc network, we consider the random access mechanism for the wireless channel where the nodes having packets to transmit in their transmit buffers attempt transmissions by delaying the transmission by a random amount of time. This mechanism acts as a way to avoid collisions of transmissions of nearby nodes in the case where nodes can not sense the channel while transmitting (hence, are not aware of other ongoing transmissions). We assume that time is slotted into fixed length time frames. In any slot, a node having a packet to be transmitted to one of its neighboring devices decides with some fixed (possibly node dependent) probability in favor of a transmission attempt. If there is no other transmission by the other devices whose transmission can interfere with the node under consideration, the transmission is successful. As examples of this mechanism, we find Aloha-type [14] and IEEE 802.11 CSMA/CA-based mechanism. With these mechanisms, each node determines its transmission times [4,25]. In the UMTS network, the nodes communicate using Direct Sequence-Code Division Multiple Access (DD-CDMA). The node transmits the packet with fixed rate and fixed power [26]. We consider an automatic-repeat-request(ARQ) mechanism in which the node keeps retransmitting a packet until the packet is received at base station without any error. At any instant in time, a device may have two kinds of packets to be transmitted: 1. Packets generated by the device itself. This can be sensed data if we are considering a sensor network. 2. Packets from other neighboring devices that need to be forwarded.
On Extending Coverage of UMTS Networks Using an Ad-Hoc Network
137
We consider two separate queues for these two types and do a weighted fair queueing (WFQ) for these two queues. This configuration allows nodes to have flexibility for managing at each node forwarded packets and its own packets differently. Two queues allow to model the selfish behavior or on the contrary to give higher priority to connections that traverse many hops that could otherwise suffer from large loss rates. The main contribution of this paper is to provide approximation expressions of stability. Our main result is concerned with the stability of the forwarding queues at the devices. It states that whether or not the forwarding queues can be stabilized (by appropriate choice of WFQ weights) depends only on the routing and the channel access rates of the devices. The end-to-end throughput achieved by the nodes are independent of the choice of the WFQ weight. The context of the stability that we study is new as it takes into account the possibility of a limited number of transmissions of a packet at each node after which it is dropped. Related works. Multihoming has been traditionally used by stub networks for improving network availability. Previous studies [5], have shown that ”Multihoming Route Control” can improve the Internet communication performance of the networks significantly. A comparison study of overlay source routing and multihoming is presented in [6]. The goal of this work is how much benefit does overlay routing provides over BGP, when multihoming and route control are considered. In wireless network, the usefulness of attaching to the Internet using different access technologies at different time, or even simultaneously, has been described in various works [7, 8]. A work devoted to IEEE 802.11 WLANs is [9], where users can choose between several access points and even split their traffic by using several of them. The network stability has been studied extensively both for networks with centralized scheduling [15, 17], Aloha protocol [10, 21] and UMTS system [19,20]. Among the most studied stability problems are scheduling [15,16] as well as for the Aloha protocol [27, 24]. Tassiulas and Ephremides [15] obtain a scheduling policy for the nodes that maximizes the stability region. Their approach inherently avoids collisions which allows to maximize the throughput. Radunovic and Le Boudec [11] suggest that considering the total throughput as a performance objective may not be a good objective. Moreover, most of the related studied do not consider the problem of forwarding and each flow is treated similarly (except for Radunovic and Le Boudec [11] or Tassiulas and Sarkar [23]). The rest of the paper is organized as: In section II, we formulate the problem. In section III, we study the stability of any given node in the system using the rate balance equation. We analyze the uplink case in section IV, valid our model and provide some numerical examples and some concluding remarks in section V.
2
Model Formulation
Background. Consider a geographical area which is not totally covered by any 3G system. The system is composed of three geographical classes (See fig.1); Class C1 contains terminals which communicate with each other using an ad-hoc network and some of them could be covered by the UMTS. The class C3 contains
138
R. El-Azouzi et al.
all terminals which are in the direct range of the 3G Node-B. We denote by C2 the set of mobiles covered by both the 3G system and the ad-hoc network, i.e. C2 = C1 ∩ C3 . Let N1 = card(C1 \C2 ) and N2 = card(C2 ). The 3G base station is denoted by B. The idea behind this work is to find a solution that allows non covered mobiles (C1 \C2 ) to use the 3G services besides they are not in the covered area, and allow to 3G devices to connect to Internet thanks to ad-hoc network. So we consider a scheme with special kind of terminals, each one disposes of two network cards (IEEE 802.11 and DS-CDMA), hence it could be connected to either the ad-hoc or the 3G system according to the coverage criterion. Moreover this mobile is assumed to be able to forward packets arriving from ad-hoc mobiles, and therefore transmits them to the 3G node-B or to another ad-hoc node; In other terms these type of mobiles can play the role of gateways that allow to access to the node-B and therefore to benefit from its services.
Internet
Ad-hoc subsystem
UMTS subsystem
Fig. 1. A single Cell 3G system combined with ad-hoc network. Access to UMTS and Internet without coverage constraint using an IEEE 802.11/UMTS gateway solution.
As long as a 3G node is far of the base station as its transmit power is higher, which could deteriorate the other nodes QoS. To avoid this, far nodes will prefer to use their ad-hoc neighbors to transmit and therefore save their energy. Moreover, for a 3G user who needs to connect to the Internet, it is very interesting to access to it via ad-hoc for high rate and low cost comparing to Internet via UMTS. Remark. (Case of a node j ∈ C2 ). Node j has neighbors transmitting using the IEEE 802.11 band and others using the UMTS band; When j transmits over the ad-hoc subsystem, it only collides with its neighbors using ad-hoc. And it is influenced only by users communicating with the node-B when it transmits using DS-CDMA. In others terms the two subsystems are separated and do not interfere with each other. Network layer. In order to insure the forwarding of a packet to a given destination (ad-hoc node or the Node-B), we assume that each terminal i possesses two queues Qi and Fi . Fi is selected with probability fi and receives packet to be forwarded to another destination whereas Qi represents the queue which carries the own packets of node i and is selected for transmission with probability 1 − fi . In this work we consider the saturated case where node i has always
On Extending Coverage of UMTS Networks Using an Ad-Hoc Network
139
packets to transmit from Qi . These queues are assumed to have infinite capacity. The network layer handles these queues using a weighted fair queuing (W F Q) protocol. For notation, we denote by Rs,d the set of nodes between a source s and a destination d (s and d not included). MAC layer. The MAC layers of the two subsystems are different. We consider for ad-hoc subsystem a collision channel where no more than one node can transmit successfully in a slot; Denote by τ a the duration of one slot. A successful transmission is occurred when there is no collision on reception, in other terms neighbors of an intermediate node should not transmit when it receives a packet. Each mobile transmitting a packet either from Qi or Fi should access the channel by probability Pi . We can consider the aloha protocol, CSMA/CA or any other mechanism to access the channel. For instance, the attempt rate (for node i) in IEEE 802.11 DCF (see [25]) is, Pi =
2(1 − 2Pc ) (1 − 2Pc )(CWmin + 1) + Pc CWmin (1 − (2Pc )m )
(1)
Pc denotes the conditional collision probability given that a transmission atmax tempt is made and CW is the contention window. m = log2 ( CW CWmin ) is the maximum of backoff stage. We assume that a packet is retransmitted (if needed) till success or dropping, Let Ki,s,d be the maximum number of transmissions allowed by a mobile i per packet. Yet expression (1) is valid only for IEEE 802.11 systems. In our case we have an hybrid network, so it does not hold anymore and we shall calculate it. Assume xi is the total proportion of UMTS cycles for a given node i. Let τiu be the average needed number of slots to send a UMTS packets. Proposition 1. Consider a heterogenous network composed of a UMTS and an Ad-hoc subsystems, then we have the following, 1) The proportion of UMTS traffic is, xi = Pi,B (1 − πi fi ) + fi
πi,s,B
(2)
s
2) The attempt rate for any given node i is, Pi =
Li (1 − xi ) Pi Li (1 − xi ) + τiu xi Pi
(3)
Proof. Here we develop a cycle-based method to prove proposition 1. Let us a observe the system (in particular a node i) for Ci,t cycles. Ci,t is the number of th u Ad-hoc cycles until the t slot, and Ci,t is the corresponding number of cycles for the UMTS traffic. We denote by Tta the total number of transmission slots used by Ad-hoc connections till the tth slot. The proportion of UMTS cycles is xi =
u Ci,t Ci,t
=
u,Q u,F Ci,t +Ci,t Ci,t
140 u,Q Ci,t Ci,t u,Q Ci,t Ci,t u,F Ci,t Ci,t
R. El-Azouzi et al.
is the probability to choose a UMTS packet from Qi . We have = =
u,Q Ci,t Q Ci,t F Ci,t a Ti,t
·
·
Q Ci,t Ci,t
a Ti,t Ci,t
= Pi,B (1 − πi fi ) π C u,F · Ci,tF = fi πi s i,s,B = fi s πi,s,B πi i,t
a where Ti,t denotes the number of cycles having Ad-hoc packets till slot t. The proportion of UMTS cycles becomes xi = Pi,B (1 − πi fi ) + fi s πi,s,B The proof is complete for part 1. a Tta T a Ci,t Ci,t = lim ta · · t→∞ t t→∞ C C t i,t i,t
The long term attempt rate is P i = lim Tta a Ci,t a Ci,t limt→∞ Ci,t limt→∞ Cti,t
limt→∞
is the average number of slots per cycle (Ad-hoc or UMTS), i.e. Li . is exactly the proportion of Ad-hoc cycles among Ci,t , i.e. 1 − xi . is the average number of slots per cycle (Ad-hoc or UMTS), then a Ci,t ·
Li
u +Ci,t .n
Pi u i limt→∞ Cti,t = =L Ci,t Pi (1 − xi ) + τi xi The result follows by substituting each term by its established expression.
For the UMTS subsystem, we assume that the base station communicates with 3G nodes using Direct Sequence Code Division Multiple Access (DS-CDMA). Each user i transmits to the base station with a transmission rate ρi,B (Uplink transmission rate), which is the bandwidth to the processing gain ratio. It depends on the mobile classes, the solicited service and the global load. The base station uses a downlink transmission rate ρB,i when sending to i. Another important parameter is the Packet Success Rate (PSR), which we denote by ξ(γi ), it is a function of the instantaneous signal to noise plus interference ratio (SINR). ξ(.) could be any increasing continuous, differentiable and S-sharped (sigmoidal) function with ξ(0) = 0 and ξ(+∞) = 1. Some properties and examples of S-sharped functions are studied with more details in [26] and references therein. Define μi,B as the uplink service rate, i.e. at which UMTS packets are served at node i. We denote by μB,i the arrival rate to node i from the node-B. Let 1 τi,B = μi,B be the average service time in number of ad-hoc slots. Then, it can be Ma written as: τi,B = ρi,B ξ(γ a where Ma is the length of one ad-hoc packet (in i ).τ a bit) and ρi,BMξ(γ is the average service time in second of a packet while allowing i) infinity retransmissions of a failure packet, see [26].
Cross-layer architecture. Nodes with two network cards are able to communicate with other nodes or with the 3G node-B. The system performance depends on more than one layer, this motivates us to use a cross-layer architecture (fig.2). This new network insight is more powerful and flexible thanks to communication and information exchange between different layers. Remark. It is interesting to note that a mobile is able to transmit on one interface and receive on the other and vice-versa. Moreover, it could get si-
On Extending Coverage of UMTS Networks Using an Ad-Hoc Network
141
Fig. 2. Cross-layer architecture including the two subsystems
multaneously one ad-hoc and one UMTS reception. Whereas we do not allow simultaneous transmissions over the two network cards. This is due to the nature of scheduling mechanism that we consider (selection of one queue a time). If we allow parallel selections we could make two simultaneous transmissions possible.
3
Stability of Forwarding Queues
In this section we study stability properties of nodes in the system in particular. a node i ∈ C2 which we call gateways. Classically ,the forwarding queue Fi is stable if the departure rate of packets from Fi is at least equal to the arrival rate into it. This is expressed by a rate balance system. For any given nodes i, s, d ∈ C1 ∪ C3 ; i denotes an intermediate node, s is the source and d is the destination. Let ji,s,d denote the entry in the set Rs,d just after i and N (i) be the set of i’s neighbors. The probability that a transmission from node i on route from node s to node d is successful is, Pi,s,d = (1 − P j ) (4) j∈ji,s,d ∪N (ji,s,d )\i
The expected number of attempts till success or dropping from i on route Rs,d is, 1 − (1 − Pi,s,d )Ki,s,d Li,s,d = Pi,s,d Let πi,s,d be the probability that the queue Fi has a packet at the first position ready to be forwarded to the path Rs,d . It follows that the probability that the queue Fi has at least one packet to be forwarded is πi = s,d πi,s,d . If Pi,d denotes the probability that i transmits to d then the average of Li,s,d over all possible paths is, Li = πi,s,d fi Li,s,d + (1 − πi fi )Pi,d Li,i,d (5) s,d:i∈Rs,d
d
In the following we classify connections onto three categories. – ad-hoc to ad-hoc connections: This corresponds to the case studied in [1] in which an ad-hoc node transmits to another ad-hoc node, i.e. s, d ∈ C1 .
142
R. El-Azouzi et al.
– ad-hoc to UMTS connections: This is the uplink case in which nodes transmit to the base station. For s ∈ C1 and d = B, note that a UMTS packet is transmitted until success from the gateway to the base station. – UMTS to ad-hoc connections: This illustrates downlink scheme, in other terms when the base station is transmitting to a given node so s = B and d ∈ C1 ∪ C3 . We note for transmissions to the base station, that an intermediate node i Pi forwards packets to a next hop at a rate L , whereas it forwards them to the i base station (if it is in the direct range of B) at a rate μi,B . For more generality we define μi,B as the service rate for the uplink scheme as following, μi,B =
μi,B , Pi , L i
if
if i ∈ C3 i ∈ C1 \C2
(6)
The departure rate In order to compute the departure rate of a given node, we shall make differentiation between ad-hoc and UMTS connections. Also the geographical criterion is taken into consideration thanks to P i and μi,B . The long term departure rate from node i for the connection Rs,d is,
di,s,d
⎧ Pi ⎪ ⎨ πi,s,d fi Li , = πi,s,B fi μi,B , ⎪ ⎩π Pi i,B,d fi L , i
s, d ∈ C1 s ∈ C1 , d = B d ∈ C1 , s = B
(7)
The arrival rate Here, we compute the arrival rate for each node i. Let i, s, d ∈ C1 ∪ C3 . s sends a packet destined to d with probability Ps,d . When the UMTS node-B transmits to a node d, we denote by g (for gateway) the first hop on the route RB,d . i’s long term arrival rate is expressed, according to possible connections, as following:
ai,s,d
⎧
Ps ⎪ ⎪ (1 − π f ) P 1 − (1 − Pk,s,d )Kk,s,d , ⎪ s s s,d ⎪ ⎪ Ls ⎪ k∈Rs,i ∪s ⎪ ⎪ ⎨
Ps = (1 − πs fs ) Ps,B 1 − (1 − Pk,s,B )Kk,s,B , ⎪ Ls ⎪ k∈Rs,i ∪s ⎪ ⎪
⎪ ⎪μ ⎪ 1 − (1 − Pk,s,d )Kk,s,d , ⎪ ⎩ B,g
s, d ∈ C1 s ∈ C1 , d = B d ∈ C1 , s = B
k∈RB,d
(8) End to end throughput of a connection. The end to end throughput between a couple of nodes s and d is exactly the arrival rate to the destination d. Namely thps,d = ad,s,d . Recall that gateways keep transmission of a packet over the UMTS subsystem till success (correctly received by the base station).
On Extending Coverage of UMTS Networks Using an Ad-Hoc Network
3.1
143
The Rate Balance System (RBS)
A queue Fi is stable while its corresponding departure rate is greater or equal than the arrival rate into it. In this subsection we consider the extreme case where we have strict equality. We will derive the rate balance equation for every node in the system. When the steady state is achieved, if all queues are stable, then for each i, s and d such that i ∈ Rs,d we get di,s,d = ai,s,d , this is the rate balance equation on the path Rs,d . Then for all i, s and d, we get a system of equations from which we can find a solution of the πi,s,d for all i, s and d. And then, find πi , for all i, which determines the load of the forwarding queues and the main condition of their stability which is πi < 1. Each node can forward packets for the three types of connections defined previously, and therefore we can explicit the rate balance equations using three generic equations: ⎧
P s Li ⎪ ⎪ πi,s,d fi = (1 − πs fs ) Ps,d 1 − (1 − Pk,s,d )Kk,s,d , s, d ∈ C1 ⎪ ⎪ ⎪ P i Ls ⎪ k∈R ∪s ⎪ s,i ⎪ ⎪
⎨ (1 − πs fs ) P s πi,s,B fi = Ps,d 1 − (1 − Pk,s,d )Kk,s,d , s ∈ C1 , d = B μ Ls ⎪ i,B ⎪ k∈Rs,i ∪s ⎪ ⎪ ⎪
⎪ Li ⎪ ⎪ πi,B,d fi = μB,g 1 − (1 − Pk,s,d )Kk,s,d , d ∈ C1 , s = B ⎪ ⎩ P i k∈R B,d
(9) We sum over all sources s and destinations d for all connections written above and get the global rate balance equation which is useful to study some special cases. Theorem 1. In the steady state, if all the queues in the system (both ad-hoc and UMTS) are stable, then for each i, s, d ∈ C1 ∪ C3 , such that i ∈ Rs,d we have, P i fi πi,s,d fi + μi,B πi,s,B = Li s,d s d:i∈R
B,d
+
s,d:i∈Rs,d
(1 − πs fs )
P s Ps,d Ls
μB,i
1 − (1 − Pk,B,d )Kk,B,d k∈RB,i
1 − (1 − Pk,s,d )Kk,s,d
(10)
k∈Rs,i ∪s
Let zi,s,d = πi,s,d fi , for all i, s and d, be the unknown of the rate balance system which is a non linear system because P i and Li usually depend on zi,s,d . We remark as in paper [1] that the solution is independent on the forwarding probability, and consequently the end to end throughput is also not impacted by the choice of fi as it appears when computing the end-to-end throughput thps,d = ad,s,d . This result holds only when the forwarding queues are stable. As a consequence, the forwarding capabilities of gateways do not affect their energy consumption.
144
R. El-Azouzi et al.
Another important remarks concern the interaction between the ad-hoc and the UMTS. Practically, the bit rate per node in the ad-hoc network is larger than the UMTS, but the size of this former network and its characteristics (as channel access and routing) influence drastically its capacity. Yet, connecting two heterogenous networks normally needs a scaling and an adaptation of the rates on each interface, if not, stability of the gateway nodes becomes a real issue. From the rate balance system, we find zi,s,d function of the service rate of the UMTS node μi,B and of the base station rate μB,i . So, the condition on zi,s,d (zi,s,d < 1) will be translated to a condition on the parameters of the UMTS, for example, we can find a minimum packets rate for UMTS nodes or a threshold of the SINR γ that insures stability on gateway nodes. Concerning the throughput of ad-hoc nodes connected to the base station, the throughput can be written in a simple form, in case of stability, as: thps,B = zg,s,B μg,B , where g is a gateway node. For the particular uplink case, the arrival rate (second equation of (8)) is independent of μi,B since πs fs , Li and Pi do not depend on it. Then when μi,B changes the load zi,s,B changes in the opposite sense, it follows that the throughput stays unchanged.
4
The Uplink Case Analysis
In the following we discuss and study with more details a scheme when the RBS is linear such the uplink case which is very important. There is indeed many asymmetric services which do not requires any request-response pattern (e.g. downloading files). In this case all sources has the same destination and each intermediate node forwards always to the same next hop. it follows that Li is independent of the unknown πi , Ls =
πs,s ,d fs Ls,s ,d + (1 − πs fs )Ps,d Ls,s,d = πs fs Ls,s,d + (1 − πs fs )Ls,s,d = Ls,s,d
s
The RBS is reduced to the second equation when d = B, we sum over all s,
zi,s,B =
ys P s Ps,B
s
μi,B Ls
s
1 − (1 − Pk,s,d )Kk,s,d
k∈Rs,i ∪s
Let yi = 1 − πi fi , later we will refer to yi as the stability region of Fi . We have, yi +
ys ωi,s = 1
(11)
s
where ωi,s =
P s Ps,d d μi,B Ls
k∈Rs,i ∪s
1 − (1 − Pk,s,d )Kk,s,d . (11) can be written in
a matrix form and then will be resolved more easily. Y (I + W ) = 1
(12)
On Extending Coverage of UMTS Networks Using an Ad-Hoc Network
145
W is the N ×N matrix whose (s, i)th entry is ωs,i , Y is the unknown N −dimensional row vector, i.e. Y (i) = yi . In the following we will restrict to symmetric ad-hoc network. The transmit and forwarding probabilities are the same for all users, i.e. Pi = P and fi = f . Assume that every ad-hoc node i has the same number of neighbors ni = n (such a grid or a mesh), it follows that Pi,s,B = (1 − P )n . For simplification and without loss of generality we will be assuming that Ki,s,d ≡ 1. Let denote by d(i, s, B) the number of intermediate nodes on the route Rs,B . Since we only consider uplink connections we shall put μB,g = 0. Proposition 2. A necessary condition for stability of Fi , for any given node in the system, for the uplink scheme is that, f≥ where ω i,s,B =
s
ωi,s,B ωi,s,B + μi,B
s.t.
f ≤1
(13)
P (1 − P )n(d(i,s,B)+1)
Proof. For any given routing, the input ratio into the forwarding queue Fi is, ai =
(1 − f πs )P Ps,s,B 1 − (1 − Pk,s,B )Kk,s,B s
k∈Rs,i
≥ (1 − f )P (1 − P )n(d(i,s,B)+1) = amin i s
The departure rate is di = μi,B f πi ≤ μi,B f = dmax i Since Fi is stable if and only if di ≥ ai , then the result follows. The next corollary provides a condition related to UMTS subsystem. Corollary. Considering the uplink case, a necessary condition that insures stability of queue Fi for any given gateway i, is that, μi,B ≥
1−f · ωi,s,B f
(14)
A more useful form is to convert it onto a condition on instantaneous SINR as, γi ≥ ξ −1
1 − f Ma · · ωi,s,B a f ρi,B τ
(15)
where ωi,s,B = s P (1−P )n(d(i,s,B)+1) . An interesting result of proposition (13) is that UMTS parameters do not affect stability of non covered nodes.
5
Numerical Results and Simulations
Consider in fig. (3) one single UMTS cell, covered by base station B, and extended with an Ad-Hoc network which is itself related to Internet via AP 9.
146
R. El-Azouzi et al. a
Connection a: 4-3-2-1-B Connection b: 6-5-1-B Connection c: 10-1-7-8-AP
1O
a
3
2
a c 4
Internet
b
b
11
5 1
c 6
c c 9
7 8
Fig. 3. Cellular and Ad-Hoc networks 0.076
1 node node node node
0.9 0.8
1 2 3 5
0.074
0.7
Throughput
0.072
π
i
0.6 0.5 0.4
a b
0.07
0.068
0.3 0.2
0.066
0.1 0 0
0.2
0.4
μi,B
0.6
0.8
0.064 0
1
0.2
0.4
μ
0.6
0.8
1
i,B
Fig. 4. Queues load for K = 4 and f = 0.8 Fig. 5. Throughput of connections a and b 1
0.08
node node node node
0.9 0.8
1 2 3 5
0.07 0.06
Throughput
0.7
πi
0.6 0.5 0.4 0.3
0.05 0.04 0.03
0.2 0.02
a b
0.1 0 0
0.2
0.4
μi,B
0.6
0.8
1
Fig. 6. Queues load πi from simulation
0.01 0
0.2
0.4
μ
0.6
0.8
1
i,B
Fig. 7. Throughput from simulation
Both nodes in the UMTS cell and the Ad-Hoc network can access to the services of the two networks. For that, gateway nodes play an important relay role on forwarding packets for both technologies. For that we are interested to show, at first, numerical results concerning the load of these latter nodes and then the end -to-end throughput of connections that traverse these nodes. We use a discrete time simulator that reflects the behavior of nodes in our model described in section 2, to validate our formulation results. In fig. (3), nodes 4 and 6 access the UMTS system with the base station B via connections a and b. Node 10 which is in the UMTS cell also reaches the access point AP (node 9) via the Ad-Hoc network with a connection c.
On Extending Coverage of UMTS Networks Using an Ad-Hoc Network
147
We fixe P3 = P9 = 0.2, P4 = 0.4 and all other Pi to 0.3. The number of transmissions is set to Ki,s,d ≡ K = 4 and the forwarding probability to fi ≡ f = 0.8. Fig. (4) and (5) consider only the uplink case where Ad-Hoc nodes communicate with the base station. Fig. 4 shows the load variation function of the UMTS service rate μ1,B . It is clear that increasing μ1,B would ameliorate the stability of node 1. Here, we see that we need μ1,B > 0.19 to get π1 < 1. For an Ad-Hoc node rate of 2Mbps and an Ad-Hoc packet size of 1000 Bytes, the slot size becomes τ a = 4ms, then a minimum UMTS rate needed must be at least 47.5 packet/s (ad-hoc packet). Concerning the throughput, fig. (5) shows the insensitivity of the throughput with the service rate of the UMTS. Note that only for π1 < 1 the figure of the throughput make sense. Elsewhere it will be an increasing function of μ1,B as it is shown in the simulation fig. (7). A validation with simulations of the numerical results is shown in fig. (7,6). Conclusion. In this paper we propose extending the coverage of UMTS using an ad-hoc network, our main result is characterization of stability condition and the end-to-end throughput, we also validate the analytical result using a discrete simulator. An ongoing work consists on studying the impact of transmit power over the 3G subsystem on the stability of the forwarding queues. We also consider a joint power and rate control game to seek the equilibrium points under some QoS constraints.
References 1. El Khoury, R., Elazouzi, R.: Stability-throughput analysis in a multi-hop ad hoc networks with weighted fair queueing. In: The Proc. 45th Annual Allerton Conf. on Communication, Control, and Computing (Allerton 2007), Monticello, IL (September 2007) 2. Kherani, A., ElAzouzi, R., Altman, E.: Stability-Throughput tradeoff and routing in multi-hop wireless ad-hoc networks. In: The Proceeding of Networking Conference 2006, Coimbra, Portugal, MAY 19, vol. 15 (2006) (Best paper Award) 3. Bria, A.: Joint resource management of cellular and broadcasting systems-research challenges. In: RVK 2005 Conference (2005) 4. Bianchi, G.: Performance analysis of the IEEE 802.11 distribute coordination function. IEEE Journal on Selected Areas in Communications (March 2000) 5. Smith, P.: Bgp multihoming techniques. In: NANOG, vol. 23 (2001) 6. Shaikh, A., Sitaraman, R., Akella, A., Maggs, B.: A measurement-based analysis of multihoming. In: SIGCOMM (2003) 7. Stemm, R., Katz, R.: Vertical handoffs in wireless overlay networks. Journal on Mobile Networks and applications 3(4), 335–350 (1998) 8. Wakikawa, R., Paik, E.K., Ng, C.W., Ernst, T., Montavont, N., Noel, T.: Goal and benefits of multihoming. IETF Internet Draft (July 2005) 9. Altman, E., Shakkottai, S., Kumar, A.: The case for non-cooperative multihoming of users to access points in ieee 802.11 wlans. In: IEEE INFOCOM 2006, Barcelona (2006) 10. Rao, R., Ephremides, A.: On the stability of ineracting queues in a multi-access system. IEEE Tran. Inform. Theory 34, 918–930 (1988)
148
R. El-Azouzi et al.
11. Radunovic, B., Le Boudec, J.Y.: Joint Scheduling, Power Control and Routing in Symmetric, One-dimensional, Multi-hop Wireless Networks. In: WiOpt 2003: Modeling and Optimization in Mobile, Ad-Hoc and Wireless Networks, SophiaAntipolis, France (2003) 12. Clausen, T., Jacquet, P., Laouiti, A., Muhlethaler, P., Qayyum, A., Viennot, L.: Optimized Link State Routing Protocol. In: IEEE INMIC Pakistan (2001) 13. Murthy, S., Garcia-Luna-Aceves, J.J.: An Efficient Routing Protocol for Wireless Networks. ACM/Baltzer Journal on Mobile Networks and Applications, Special Issue on Routing in Mobile Communication Networks 1 (1996) 14. Roberts, L.G.: Aloha packet system with and without slots and capture, Tech. Rep. Ass Notes stanford Research Institute advance Recharch Projects Agency Network Infomation Center (1972) 15. Tassiulas, L., Ephremides, A.: Stability properties of constrained queuing systems and scheduling for maximum throughput in multihop radio network. IEEE Trans. Automat. Contr. 37(12), 1936–1949 (1992) 16. Tassiulas, L.: Linear complexity algorithm for maximum throughput in radio networks and input queued switches. In: IEEE Infocom 1998, pp. 533–539 (1998) 17. Tassiulas, L.: Scheduling and perfomance limits of networks with contantly changing topology. IEEE TRans. Inform. Theory 43(3), 1067–1073 (1997) 18. Altman, E., Borkar, V.S., Kherani, A.A., Michiardi, P., Molva, R.: Some game theoretic problems in wireless ad-hoc networks. In: Kotsis, G., Spaniol, O. (eds.) Euro-NGI 2004. LNCS, vol. 3427, pp. 82–104. Springer, Heidelberg (2005) 19. Schr¨ oder, B., Weller, A.: Prediction of the Connection Stability of UMTS Services in the downlink- an Analytical Approach. In: Vehicular Technology Conference (2002) 20. Kumar, A., Patil, D.: Stability and throughput analysis of unslotted CDMAALOHA with finite number of users and code sharing. Telecommunication Systems 8 (December (2-4), 1997) 21. Luo, W., Ephremides, A.: Stability of N interacting queues in multiqueue distributed systems: buffered random acess system. IEEE Trans. Inform. Theory 45, 1579–1587 (1999) 22. Tsybakov, B., Mikhailov, W.: Ergodicity of slotted Aloha system. Prob. Inform. Transmission 15(4), 301–312 (1979) 23. Tassiulas, L., Sarkar, S.: Max-Min fair scheduling in wireless networks. In: Proceeding of Infocom 2002 (2002) 24. Tsybakov, B.S., Bakirov, V.L.: Packet transmission in radio networks. Probl Infom. Transmission 21(1), 60–76 (1985) 25. Yang, Y., Hou, J.C., Kung, L.-C.: Modeling the effect of transmit power and physical carrier sense in multi-hop Wireless networks. In: Infocom 2007, Alaska (2007) 26. Meshkati, F., Poor, H.V., Schwartz, S.C., Mandayam, N.B.: An energy efficient approach to power control and receiver design in wireless data networks. IEEE transactions on communications 53(11), 1885–1894 (2005) 27. Anantharam, V.: The stability region of the finite-user slotted Alloha protocol. III Trans. Inform. Theory 37(3), 535–540 (1991)
A Performance Analysis of Authentication Using Covert Timing Channels Reed Newman and Raheem Beyah Communications Assurance and Performance Group, Computer Science Department, Georgia State University Atlanta, GA, USA [email protected], [email protected]
Abstract. Authentication over a network is an important and difficult problem. Accurately determining the authenticity of a node or user is critical in maintaining the security of a network. Our proposed technique covertly embeds a watermark, or identifying tag, within a data stream. By implementing this model on a LAN and WLAN we show that this method is easily adaptable to a variety of networking technologies, and easily scalable. While our technique increases the time required for data to be transferred, we show that the throughput of the link during the brief authentication window is decreased by no more than 8% in a switched LAN and 11% in a WLAN. During our empirical analysis we were able to detect the watermark with 100% accuracy in both a LAN and WLAN environment.
1 Introduction With the large amount of network applications in existence today, it is becoming increasingly difficult for network administrators to police the traffic on their networks. Additionally, these network applications are increasingly carrying sensitive information; as the sensitivity of the information traversing the network increases, so too must the level of security within the network. A key step in securing a network is the authentication of all nodes1 on that network. Authentication of nodes allow perimeter devices the ability to determine if a node's requests should be granted. Reliable node authentication helps to ensure the basic elements of network security: positively identifying a node, allowing that node specific access privileges, and holding that node accountable should it compromise the security or productivity of the network. Leading industry approaches, such as Cisco’s AAA Server and Cisco's NAC model [1], rely on user name/password, S/Key, Token Cards or system profiling to authenticate users. While all of these methods provide a reasonable level of security, each are expensive and have been shown to have flaws [2,3]. Additionally, simple access control lists have proven to be ineffective as spoofing IP and MAC addresses is a trivial task, allowing attackers to easily gain access to systems and networks. 1
Authentication relating to nodes can easily be extended to users. When referencing nodes, unless otherwise noted, the statement applies to nodes and users.
A. Das et al. (Eds.): NETWORKING 2008, LNCS 4982, pp. 149–161, 2008. © IFIP International Federation for Information Processing 2008
150
R. Newman and R. Beyah
By not requiring strict node authentication, joining a network is a trivial matter. An attacker may obtain a physical connection to a network, enter the network through a wireless access point, circumvent 802.1x via phishing or other known exploits, or access the network via a VPN connection. By requiring each node joining the network to authenticate itself, the overall security of the network is increased making systems within the network harder to breach. We propose to embed a watermark, or signature specific to a node, within a data flow using inter-packet delay. The watermark will be embedded between select packets in a covert manner, such that it is difficult to detect and does not decrease the throughput of the link significantly. Our model can be used to supplement the above methods or be used as a standalone method of authentication. Our technique does not require synchronization between the nodes' clocks, and can easily be adapted for user authentication. We acknowledge that our proposed method, a method advocating security by obscurity, is not an impervious solution but assert that the additional layer of security increases the difficulty for an attacker. We believe that providing authentication in a covert manner adds the same level of benefit one achieves when changing an internal server’s (sftp, ssh, etc.) port from a well-known port to a random port. The attacker would require not only a technique by which to break into the server (e.g., a buffer overflow attack, etc.), but must also find the server, via port scanning, over a range of 64,000 ports without being detected. Further, this work evaluates performance of using timing channels in general to transmit data. Our specific application of this method uses this channel to communicate authentication information. The remainder of this paper is organized as follows: Section 2 reviews related work, Section 3 details the covert timing channel model, Section 4 outlines the experimental setup and procedure, Section 5 provides analysis on the model, Section 6 provides experimental data, and Section 7 contains our conclusions and future work.
2 Related Work The idea of using inter-packet delay (IPD) for node identification is not necessarily new. There have been several different applications regarding the use of IPD in recent academic research. The majority of the work focuses on the detection of stepping stone connections (i.e., intermediate systems attackers use to launch attacks and insulate themselves from detection), with most solely considering interactive (SSH) traffic. The authors of [4] extend the work done in [5,6] to detect a correlation between stepping stones. In [4], the authors use a binning technique to partition the data stream allowing the encoded watermark a greater level of robustness against timing perturbations and repacketization within the stepping stone links. In [7], the authors extend the work of [8] in an effort to defeat chaff packets (e.g., structurally correct packets inserted within the data flow to obfuscate a pattern) that may be inserted by a node within the stepping stone chain. This is done by decoding watermarks from all possible subsequences of a downstream flow, and choosing the “best” watermark (defined as the watermark with the least hamming distance from the original watermark).
A Performance Analysis of Authentication Using Covert Timing Channels
151
Peng, et al. [9] investigate the secrecy of active watermarking. The authors develop an attack technique that infers important parameters of the watermarks, and also recovers and duplicates watermarks through the stepping stones. The authors of [10] attempt to detect stepping stone connection correlations of SSH traffic by creating a logical partition between ON and OFF periods of usage. By examining the IPD of connections and determining if the OFF period transitions to an ON period within a certain threshold, it can be reasonably stated that these connections are related. It is interesting to note that this is an entirely passive technique. In [11], provable upper bounds are set on the number of packets required to confidently detect encrypted stepping stone streams with proven guarantees of a low false positive rate. The methods in [11] also take into consideration the usage of chaff packets, and provide bounds on the amount of chaff needed by the attacker to evade detection. The model proposed by [12] is similar to that of [11], with the addition of wavelets. In [12], the authors attempt to differentiate between the short term behavior of the stepping stone streams, where timing perturbations and chaff packets can mask the correlation between connections, and the long term behavior of stepping stone streams. Wang and Reeves [5] propose a watermark-based scheme that can detect correlation between streams of encrypted traffic. However, the assumption is made that the attackers timing perturbations are independent and evenly distributed. Should the traffic be disturbed in another fashion, such as with the insertion of chaff packets, their method will show a decrease in accuracy. Zhang, et al. [13] provide an upper bound on the number of packets required to detect attackers in stepping stone networks when chaff packets and timing perturbations exist simultaneously. The authors of [14] show that VoIP encoding scheme can easily contain a covert channel by altering the least significant bit. They provide analysis on the bandwidth and the amount of data transferred. Wang, et al. [6] show that encrypted VoIP calls hidden through an anonymizing network can still be traced, using a technique similar to that of Paxson [10]. Only tangentially related to our work, the authors of [15] studied the loss of anonymity in a flow-based wireless mix network under flow marking attacks, in which an adversary embeds a pattern of marks into wireless traffic flows by electromagnetic interference. They asserted that traditional mix technologies are not effective in defeating flow marking attacks in wireless networks. They proposed a new countermeasure based on digital filtering technology. The authors of [16] introduce a covert timing channel model based on the presence or absence of packets arriving during a specific time period. The authors attempt to detect this covert timing channel over IP using a similarity comparison between packet inter-arrival times. The concept of covert channels was first introduced by B. Lampson in 1973 [17]. Covert channels at the network and transport layers in TCP/IP were first investigated by Rowland [18] and Fisk, et al. [19]. Currently software such as Covert_TCP [19] and Nushu [20] are available to hide data within TCP headers. Project Loki [21] has also shown that ICMP packets are capable of carrying covert information within their headers. By moving the covert channel to the application layer, detection of covert channels becomes even more difficult. It was discussed in RFC 3205 [22] that HTTP be used as a carrier for other protocols; this was obviously meant for the covert encapsulation of the protocols. Several tools are also available to tunnel protocols
152
R. Newman and R. Beyah
through HTTP, like Lars Brinkhoff's httptunnel [23], primarily for the purpose of evading firewalls. The predominate focus of these works, with the exception of [6,14-19,21-22], are on detection of stepping stones using SSH style traffic. SSH traffic can be classified as high-latency traffic, caused by user pauses in commands being issued. In [14], data in the least significant bit of the VoIP stream is altered to create a covert channel. Wang et al. [6] use a technique similar to that of Paxson [10] to correlate between VoIP flows hidden by an anonymizing network. Additionally, all of the works discussed above, with the exception of [15-19,21-22], focus on wired networks. In [17-18,21-22], the covert channel is actually embedded or encapsulated within another protocol. We propose a general model (protocol independent) for node authentication that is able to take advantage of low-latency traffic and be effective on both wired and wireless networks. We evaluate this model experimentally and address the performance and accuracy of our model. This model does not require a large amount of overhead during the brief authentication window, using no more than 8% of the available bandwidth during testing in a switched LAN and no more than 11% in a WLAN.
3 Covert Timing Channel Model Through the application of Steganography to a network flow, we achieve Covert Timing Channels, which are defined as parasitic communication channels that draw bandwidth from other channels, via the disruption of event timing relative to other events, in order to transmit information [24-25]. Traditionally Covert Timing Channels are used for the transmission of messages, and likewise, to provide authentication, we transfer a watermark or signature specific to a node, through this channel. Particularly, we disrupt the inter-packet timing within a data flow over a network (specifically using the TCP and UDP protocols). By adding minimal amounts of delay to select packets within the flow, we add a watermark to the flow in such a way that it is unique to a specific node. By delaying packets within a data stream, even minimally, we detract from the bandwidth of the network and thus increase the time required for a given task. We will show that bandwidth degrades proportional to the amount of delay needed to accurately transfer a watermark, the length of the watermark, and the rate at which the node must be re-authenticated. Disrupting the inter-packet timing within a data flow is inherently volatile, especially when considering outside influences such as the overhead incurred from the use of TCP. Given occasionally network volatility we must assume that sending one watermark may not provide adequate authentication. Additionally to provide a greater degree of robustness, in certain cases it may be necessary to increase the frequency of watermark transmissions. For instance, a university system may not require the node to re-authenticate itself often whereas a military institution, which places a higher priority on security, may. Resending the watermark increases the security provided by the model, allowing the host network to ensure that the node it authenticated originally is still that node. In Section 4 we show that the increase per
A Performance Analysis of Authentication Using Covert Timing Channels
153
additional watermark is small, resulting in a minimal decrease of network throughput. Additionally, we provide analysis on the amount of delay required to accurately detect the watermark, versus the percentage error of false negatives. The degree of natural delay varies from one network type to another. For instance, assuming that network delay is the only factor, the time required to transfer a file over the Internet or VPN connection is greater than the time required to transfer that same file over a wireless network (from one local computer to another); the time required for the transfer of that file over the wireless network is greater than the time required to transfer the file over a 100Mbps LAN connection. With the addition of network congestion, packet loss, etc., the distinction between network types becomes even clearer. As such, the addition of delay required by our model dynamically varies depending on what type of network the user is using. Our model calculates the minimal delay required to accurately embed a watermark into the data flow by using the roundtrip time (RTT) of the first ten data packets received per connection over a TCP connection. This approach will not work over a UDP flow, as there are no acknowledgment packets being returned to the sender. If UDP is being used, the client will ping the server several times and calculate the delay based on the RTT provided. An overview of our model, graphically represented in Fig. 1, is as follows. Initially a bootstrap phase is entered. During this phase, a kernel module, called the Encoder, is loaded and an initial watermark is created. The Encoder associates itself with an application at the transport layer and acts as a filter allowing for the queuing of packets, so that delay may be added. An additional kernel hook, called the Detector, registers itself to determine the RTT of the first ten data packets sent, which will determine the amount of delay added to the data flow. The initial watermark is currently generated from a password, but can be altered to be generated from another input; for example, using a serial number unique to a node (or other identifying information) in addition to a password would allow for the authentication of the user/machine pair. To generate a watermark, our password is hashed using the SHA-1 hashing algorithm, translated from hex to binary, and truncated to the desired length of the watermark. Two delay values are used within the watermark. A high value is used to represent a binary 1, and a low value used to represent a binary 0; the true high (λ) and low (ω) values are set by the Detector with λ > ω and ω being greater than the average delay between packets. When delaying a packet that is part of the watermarked sequence, the binary watermark is consulted to determine if the delay to be added is λ or ω; if the binary value of the delay is a 0, the value represented by ω is used, with the value of λ being used if the binary value of the delay is a 1. As data is sent from the application, it is registered with the Encoder. The Encoder tracks the number of packets being sent, as well as the start time of the data flow. From a predetermined level of security configured by the user, the Encoder will embed the watermark within the data stream after every β number of packets, or after γ units of time have elapsed. Additionally, the user may configure the watermark to be rehashed using the current watermark as the key to create a new watermark after δ packets have been transferred, or to create a new watermark after ζ units of time have elapsed. From this point, the data is transferred over the network to the receiver where another module, a kernel hook, decodes the signal; it is not required that a kernel hook be used in this instance, the application itself could provide this service. Abstractly,
154
R. Newman and R. Beyah
Fig. 1.
Fig. 2.
Fig. 3.
Fig. 1. A work flow depicting the Covert Timing Channel Model. Fig. 2. Depiction of the Experimental Testbed. Fig. 3 Watermarks in UDP traffic transmitted over a WLAN link. Here λ = 12 ms and ω = 8 ms, with the Watermark = {1 0 1 1 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0}.
we shall refer to this entity as the Decoder. Prior to decoding the watermark, the data flows' inter-packet timing sequence is subjected to a high-pass filter which filters out the majority of the un-encoded network traffic. Two methods of decoding the watermarks were investigated. These methods are as follows: 1. The Simple Threshold Method – A cutoff point is determined by taking the mean of the IPD not set to zero by the high-pass filter. If a packet has been delayed by an amount greater than the cutoff, it is considered to represent a 1, otherwise it is considered to represent a 0. 2. The Multi-Threshold Method – Using a moving window of two, the values are multiplied together and stored in a separate array. Doing this places the number pairs into three distinctly separate categories, 00, 01/10, and 11. It is difficult to determine the order of the pairing in the 01/10 category; as a solution, the original stream is reviewed, and the greater value is determined to be the 1 value. Due to space limitations, only the Simple Threshold Method was used during testing. Should the flow be found to not contain the watermark after a certain threshold, as determined by the level of security required, the Decoder can be configured to signal a firewall, or other external device, in an effort to alert a user or disallow continued traffic from the source. There are many additional steps that could be taken, each specific to an individual organization's needs, and beyond the scope of this work.
4 Experimental Setup and Procedure To test the Covert Timing Channel Model in a controlled environment, an experimental testbed was constructed. The testbed was comprised of a Lenovo 3000 C100 laptop running Fedora Core 4, kernel ver. 2.6.16-1.2111_FC4 with 512 MB RAM as the client sending the watermark. One server, called Server 1, used in the
A Performance Analysis of Authentication Using Covert Timing Channels
155
testbed was a custom build desktop computer running Fedora Core 6, kernel ver. 2.6.20 with a 3.0 GHz processor and 1 GB RAM connected on a local network with the client by both a wired and wireless connection. An Airlink101 wireless card was used in the Lenovo client, and a D-Link wireless USB adapter was used in Server 1 for the wireless testing. A Netgear 802.11b router was used for the local wired and wireless testing; encryption was left on during the wireless testing to more accurately simulate a real-world environment. The majority of network traffic was generated by the client to the server, with several other computers generating traffic through the router on the local network, but not to the client or server. This is an appropriate setup considering most institutions use a switched network, possibly a wireless network as well, with multiple users active at any given time. In our experiments there were two different scenarios: 1. 2.
Switched LAN – The data transfer occurs entirely over a 10/100 Ethernet network. 802.11b WLAN – The data transfer occurs entirely over an 802.11b wireless network.
Several different configurations were used with multiple trials being run for each configuration. Packets were queued using a Netfilter kernel module [26]. The packets were passed to user space if they were being sent out of a predetermined port, and placed into a separate queue with an appropriate release time set. If the packets were part of a watermark, the release time was set according to the watermark; if the packets were not part of a watermark, their release time was set to the current time. The head of the queue was continually checked to determine if the packet had reached its release time, and the packet was released if the current time was greater than the release time. All network traffic was monitored using Tcpdump [27]. Traffic was generated by transferring a 2.97 MB text file using a simple sockets program written in C, resulting in the transfer of 2035 packets over the network for Figures 4 and 5. For Figures 6-9, the same sockets program was used to transfer 88,000 packets over the network. Each set of captured data was parsed to a flat file using a pcap parser. The files were then processed in Matlab to detect the watermark embedded within the data flow. Five hundred tests per network type were run without using the watermark to provide a baseline.2 For each set of parameters used in Figures 6-9, ten trials were run per configuration, resulting in approximately 400 trials.
5 Analysis The balance of performance and security within large networks is crucial in maintaining the viability of that network. Corporate, university, government and military networks all require different levels of security and minimum tolerable levels of performance, leading to the need for scalable and adaptable solutions that do not prohibit performance. Using the Covert Channel Model, each network type receives a configurable and robust method to authenticate nodes for a minimal cost to the 2
UDP traffic was generated as a CBR data flow (35Mbps).
156
R. Newman and R. Beyah
network. The cost of using these methods varies depending on the frequency of authentication, size of the watermark, and the amount of delay added. This cost is minimal over switched LAN and WLAN connections. When adding a watermark, the majority of the data flow is uninterrupted (Unwatermarked Delay). Only the portion of the data flow containing the watermark adds delay (Watermarked Delay). Additionally, the number of times the watermark repeats increases the delay (Watermarked Repetition Delay), leading to the delay model (Total Delay). unwatermarked_transmission_time = ( packets_total – packets_watermarked ) x (RTT/2) high_delay = packets_watermarked @ λ x λ low_delay = packets_watermarked @ ω x ω watermarked_delay = high_delay + low_delay watermarked_repititions_delay = total_repititions x watermarked_delay transmission_time = unwatermarked_transmission_time + watermarked_repitions_delay
The delay added by the watermark depends on 4 variables: (1) The value of λ; (2) the value of ω; (3) the length of the watermark; and (4) the number of times the watermark is repeated. Both (1) and (2) are configurable and by minimizing these parameters the performance of the network is preserved. Both (3) and (4) are a function of the security required by the network. The Detector attempts to minimize the values in (1) and (2). By using the values of first ten data packets sent, the Detector determines which type of network is being used and sets the rates accordingly. It determines the connection type based on the RTT time of the first ten packets. The distinction between a LAN and a WLAN is made based on the variance within the first ten packets. If a LAN is in use, the Detector sets λ= (φHigh x ( RTT / 2 )) and sets ω = (φLow x (RTT/2)) with φHigh = 46.5 and φLow = 15.5. If a WLAN connection is in use the Detector sets the Encoder to “spike” the interface. When using a WLAN connection φHigh = 1.84 and φLow = 1.0; due to the comparatively high bandwidth of the LAN connection, larger normalizing parameters (φHigh, φLow) are required. During testing, it was initially observed that large delays were required on WLAN networks to ensure that the entire watermark was received. When using limited bandwidth, such as that on a WLAN, packets may be queued within the interface before being transferred to the network. By adding a large delay (“a spike”) prior to sending the watermark, the interface is allowed to clear its queue and thus transmit the watermark with greater accuracy and lower delays. Empirical testing shows that by “spiking” the interface, bandwidth over a WLAN connection is preserved far better than by simply increasing λ and ω. This will be discussed in more detail in Section 6. While testing was done using both TCP and UDP traffic, we will focus our analysis on TCP. The primary reason for this is that UDP traffic is relatively well behaved (with no outside influences unlike TCP) and easily carries the watermark. This is shown in Fig. 3 where UDP traffic is sent over a WLAN connection (which is more volatile than a LAN connection) at a rate well below the rate determined to be optimal. During this trial, watermarks were detected at 100% over the entire duration. UDP traffic over a LAN connection showed similar results. Ideally, after minimizing the delay, the watermark is transfered over the network and detected immediately. While this may be true with λ and ω set to a high value, it is not always the case. Network perturbations may cause alterations within the watermark
A Performance Analysis of Authentication Using Covert Timing Channels
157
leading to a false negative (no false positives were observed). In this case, multiple watermarks may be sent to authenticate the node. These incomplete watermarks are examined to determine their proximity to the correct watermark. Should they be within a tolerance level against false negatives (a predetermined value from the user) they will be considered the same as an ideal watermark. Additionally, care is taken such that delay values are not set too high (i.e., above the TCP timeout values), since packet retransmissions could also cause an increased number of false negatives. Optimal values for encoding differ per network. To maximize throughput the desired value for ω is slightly above the normal sending rate. Desired values for λ are slightly but distinguishably above ω. While this varies depending on what network type is in use, testing within our testbed has shown that optimal values in our LAN are λ = 6ms and ω = 2ms and in our WLAN are λ = 22ms and ω = 16ms. This was determined empirically and is illustrated in Fig. 4 and Fig. 5. These values lead to a highly detectable solution that is still covert and minimizes the number of watermarks required for accurate detection. Network performance is not greatly affected if λ and ω are set to relatively low values (but not the lowest possible values) and the number of watermarks contained within the authentication cycle is small. An authentication cycle represents the transmission of one or more watermarks. The transmission of several watermarks may be required to achieve an acceptable degree of detection accuracy. While it is certainly possible for a greater degree of performance to be achieved by setting λ and ω to lower values, doing so decreases the probability that the watermark will be accurately detected requiring a larger number of watermarks to be included within an authentication cycle. The computational power required and the speeds at which the watermarks can be detected are also important factors. The Simple Threshold Method is a powerful and easily implementable method to detect the watermark. It only requires enough memory to buffer the current watermark, and minimal computations; as such, the Simple Threshold Method is faster than the Multi-Threshold Method. The drawback to using this method is that it has minimal intelligence, and can create a higher false positive rating if network conditions change. The Multi-Threshold Method provides a greater degree of robustness with lower false positive rates. However, it does require that the original time stamps be held in memory as well as the current watermark, and a slightly greater amount of computation to be done. Comparatively, the MultiThreshold Method provides better protection against changes within network conditions. Due to space limitations our experimental data only provides analysis using the Simple Threshold method. At the monitoring node each watermark is individually detected and compared to the true watermark to determine its accuracy. Each of these accuracy ratings are stored until enough watermarks have been received (or time has elapsed) to complete one authentication cycle. The maximum value of the stored accuracy ratings is selected and compared to the configured threshold. If this maximum is greater than the threshold the user is considered to be authenticated, otherwise the maximum value of the stored accuracy ratings is averaged with all previously detected maximum rates and this value is considered to be the user’s current authentication value. The authentication value is compared to the configured threshold again to determine if the user is authenticated.
158
R. Newman and R. Beyah
Fig. 4.
Fig. 5.
Fig. 6
Fig. 7.
Fig. 8.
Fig. 9
Fig. 4. contains the results from trials used to empirically determine the optimal values for λ and ω, as well as the number of watermarks required per authentication cycle for different levels of detection accuracy in a LAN. Fig. 5 contains the results from trials used to empirically determine the optimal values for λ and ω, as well as the number of watermarks required per authentication cycle for different levels of detection accuracy in a WLAN. Figs. 6 and 8 show the percentage decrease in network throughput, compared to the baseline throughput, when the number of authentication cycles is increased in a switched LAN and WLAN respectively. Figs. 7 and 9 show the percentage decrease in network throughput, compared to the baseline throughput, when the length of a single watermark is increased in a switched LAN and WLAN respectively.
6 Performance Analysis RTT values differ per network. During testing it was observed that RTT values for a switched LAN had a median value of 0.258ms and a mean value of 0.247ms. Within a WLAN the RTT median value was 23.90ms and a mean value of 42.43ms. Using the Detector, the appropriate λ / ω delay times for a LAN and WLAN network are 6ms/2ms and 22ms/16ms respectively. As previously mentioned these values were determined empirically and are fixed in order to provide the performance analysis. While certain institutions may require the highest level of security, the needs of other institutions may not be as stringent. The Covert Timing Channel method is designed to be a general method of authentication for institutions requiring various levels of security. As such, performance testing was done for several different levels of accuracy using different watermarks lengths and various numbers of watermarks included within a single authentication cycle. By using shorter watermark lengths and/or fewer watermarks per authentication cycle, institutions (such as educational facilities that do not require high levels of security) may authenticate nodes with a
A Performance Analysis of Authentication Using Covert Timing Channels
159
lower degree of accuracy without seriously impacting the performance of the network. Conversely, institutions requiring a greater degree of security may increase the length of the watermark and/or the number of watermarks per authentication cycle. Doing so allows nodes to be authenticated at a higher degree of accuracy while increasing the complexity required for watermarks to be detected at high levels of accuracy. Testing on the switched LAN differed from that of the WLAN network in that the addition of a watermark was either fully detectable or not detectable at all up to 95% accuracy using an authentication cycle containing one watermark, after which an increase in the authentication cycle size (increased to three watermarks) was required to achieve 100% accuracy at lower rates. This is the result of extremely low latency between hosts. The “authentication watermarks” were fully detectable until 6ms/2ms, after which no watermarks were detected at all. As long as λ > 5ms and 1ms < ω ≤ λ2ms, watermarks were generally 95% detectable with 0% error within the detection. The values of 6ms/2ms were chosen for the LAN because of their consistent ability to provide a great degree of detectability with minimal performance degradation (Fig. 4). Our primary consideration during testing was the amount of overhead this model requires for accurate detection. Two configurable parameters were tested to provide a performance versus security comparison: (1) the cost to network throughput for different watermark lengths; and (2) the cost to network throughput for additional redundancy using authentication cycles. By increasing the length of the watermark and by adding additional authentication cycles, the security of the model is increased at a cost to the network throughput. Fig. 6 represents the cost of increasing the number of watermarks contained within one authentication cycle. This figure provides results for 1 watermark, 20 bits (or packets) long, per authentication cycle, with one to ten authentication cycles being sent over the authentication period of 88,000 packets for 95% detection rate. To achieve 100% detection, 3 watermarks were used per authentication cycle using the same λ and ω values. The throughput of the watermarked flows are compared to the average of several hundred baseline transmissions in the same environment. Transmission of more authentication cycles caused a decrease in the throughput of the network. In our experiments it was noted that there was an average of 0.54% decrease in throughput per additional authentication cycle transmitted, with a maximum performance penalty of 7.32% over our trials. Fig. 7 represents the cost of increasing the watermark length, tested using 6 watermarks per authentication cycle for 100% detection, and 1 watermark per authentication cycle for 95% detection. The cost of increasing the watermark from a length of 5 to 40 is a total decrease in throughput of 7.5%, with each additional bit costing, on average, a 0.036% decrease in throughput. Performance on a WLAN network had a greater degree of variance, primarily due to the nature of the network. Due to the bursty nature of a WLAN network, a higher proportional delay value was required for accurate detection. Testing was done at a detection accuracy of 90% (λ = 20ms), 95% (λ = 20ms), and 100% (λ = 22ms), with ω = 12ms (the optimal low value for our tested network) for each.
160
R. Newman and R. Beyah
Fig. 8 represents the cost of increasing the amount of authentication cycles per authentication period on a WLAN network. Each authentication cycle contains 6/3/2 watermarks for 100%/95%/90% detection respectively, consisting of 20 bits (or packets). In our experiments it was noted that there was, on average, a 0.63% decrease in network throughput per additional authentication cycle added, with a maximum decrease of 7.17%. Fig. 9 represents the cost of increasing the watermark length in a WLAN network. This figure contains a large degree of variance due to the nature of WLAN networks, but shows a general decrease in network throughput as the length of the watermarks are increased; with a larger amount of test data, we believe that this trend will smooth over time. On average adding an additional bit in a watermark on a WLAN network caused a 0.0435% decrease in throughput with, generally, an average maximum performance penalty of 8.54% when disregarding a single outlying value. All figures, while showing the general trend expected, are comprised of a limited set of trials. It is our belief that the anomalies within each figure will smooth over a larger number of trials.
7 Conclusion and Future Work While our specific application uses the Covert Timing Channel model to communicate authentication information, we investigate the use of the Covert Timing Channel model to transmit data in general. We show that the Covert Timing Channel method provides a secure, reliable, and cost effective process for which nodes may be authenticated within a network. Our model is highly scalable, easily adaptable and backwards compatible with existing technology, and provides excellent performance on switched LAN and WLAN networks. While the performance of this model is readily visible from the LAN and WLAN test results, we believe that this model could be extended for use over WAN networks as well; in our future work, we intend to show that this model will perform well over VPN connections. Additionally, we intend to investigate the effects of chaff packets on our method. Lastly, we shall apply our method to node authentication using real world traffic.
References 1. Cisco, NAC. http://www.cisco.com/en/US/netsol/ns466/ networking_solutions_package.html 2. Thumann, M., Roecher, D.: NAC@ACK: Hacking the Cisco Nac Framework. In: The Proceedings of Black Hat Europe (2007) 3. Cisco Security Response: AAA Command Authorization By-Pass. 0125-aaatcl.pdf (2006), http://www.cisco.com/warp/public/707/cisco-sr4. Pyun, Y.J., Park, Y.H., Wang, X., Reeves, D.S., Ning, P.: Tracing Traffic through Intermediate Hosts that Repacketize Flows. In: INFOCOM 2007. 26th IEEE International Conference on Computer Communications (2007) 5. Wang, X., Reeves, D.S.: Robust Correlation of Encrypted Attack Traffic through Stepping Stones by Manipulation of Interpacket Delays. In: Proc. of the 10th ACM conference on Computer and Communications Security (CCS), October 2003, pp. 20–29 (2003)
A Performance Analysis of Authentication Using Covert Timing Channels
161
6. Wang, X., Chen, S., Jajodia, S.: Tracking Anonymous Peer-to-Peer VoIP Calls on the Internet. In: Proc. of the 12th ACM conference on Computer and Communications Security (CCS), November 2005, pp. 81–91 (2005) 7. Peng, P., Ning, P., Reeve, D.S., Wang, X.: Active Timing-Based Correlation of Perturbed Traffic Flows with Chaff Packets. In: Proc. Of the 2nd International Workshop on Security in Distributed Computing Systems (SDCS), June 2005, pp. 107–113 (2005) 8. Want, X., Reeves, D.S., Ning, P., Feng, F.: Robust Network-Based Attack Attribution through Probabilistic Watermarking of Packet Flows. Technical Report TR-2005-10, Department of Computer Science, NC State Univ. (2005) 9. Peng, P., Ning, P., Reeves, D.S.: On the Secrecy of Timing-Based Active Watermarking Trace-Back Techniques. In: Proc. of the 2006 IEEE Symposium on Security and Privacy (S&P), May 2006, pp. 334–349 (2006) 10. Zhang, Y., Paxson, V.: Detecting Stepping Stones. In: Proc. of the 9th USENIX Security Symposium, August 2000, pp. 171–184 (2000) 11. Blum, A., Song, D.X., Venkataraman, S.: Detection of Interactive Stepping Stones: Algorithms and Confidence Bounds. In: Proc. of the 7th International Symposium on Recent Advances in Intrusion Detection (RAID), Octeber 2004, pp. 258–277 (2004) 12. Donoho, D.L., Flesia, A.G., Shankar, U., Paxson, V., Coit, J., Staniford, S.: Multiscale Stepping-Stone Detection: Detecting Pairs of Jittered Interactive Streams by Exploiting Maximum Tolerable Delay. In: Proc. of the 5th International Symposium on Recent Advances in Intrusion Detection (RAID), October 2002, pp. 17–35 (2002) 13. Zhang, L., Persaud, A., Johnson, A., Guan, Y.: Stepping Stone Attack Attribution in NonCooperative IP Networks. Iowa State University, Tech. Rep. TR-2005-02-1 (February 2005) 14. Takahashi, T., Lee, W.: An Assessment of VoIP Covert Channel Threats. In: Proc. of SecureComm 2007, 3rd International Conference on Security and Privacy in Communication Networks (2007) 15. Fu, X., Zhu, Y., Graham, B., Bettati, R., Zhao, W.: On Flow Marking Attacks in Wireless Anonymous Communication Networks. In: Proceedings of the 25th International Conference on Distributed Computing Systems (ICDCS) (2005) 16. Cabuk, S., Brodley, C., Shields, C.: IP Covert Timing Channels: Design and Detection. In: the Proceedings of the 11th ACM conference on Computer and Communications Security (October 2004) 17. Lampson, B.W.: A Note on the Confinement Problem. Communications of the ACM 16, 613–615 (1973) 18. Rowland, C.H.: Covert Channels in the TCP/IP Protocol Suite. First Monday 2.5 (May 1997) 19. Fisk, G., Fisk, M., Papadopoulos, C., Neil, J.: Eliminating Stenagraphy in Internet Traffic with Active Wardens. In: Information Hiding 2002, pp. 18–35. Springer, Heidelberg (2002) 20. Rutkowska, J.: The Implementation of Passive Covert Channels in the Linux Kernel. In: Chaos Communication Congress, Chaos Computer Club e.V. (2004) 21. route, alhambra. Project Loki. Phrack 7(49) (November 1996) 22. Moore, K.: On the Use of HTTP as a Substrate. Tech. Rep. In: Ternet Engineering Task Force, RFC 3205 (February 2002) 23. Brinkhoff, L.G.: httptunnel, http://www.nocrew.org/software/httptunnel.html 24. Covert Channels Definition, http://en.wikipedia.org/wiki/Covert_channel 25. Stenography Definition, http://en.wikipedia.org/wiki/Stenography 26. Netfilter / IPTables, http://www.netfilter.org/ 27. Tcpdump, http://www.tcpdump.org/
PassPattern System (PPS): A Pattern-Based User Authentication Scheme T. Rakesh Kumar and S.V. Raghavan Network Systems Laboratory, Department of Computer Science and Engineering, Indian Institute of Technology Madras Chennai-600036, India {rakeshk,svr}@cs.iitm.ernet.in
Abstract. Authenticating a user online, without compromising the user comfort is an important issue. The most popular approach to authenticate a user online is Password-based authentication. Studies show that, users (always) choose very simple passwords which are often easy to guess. On the contrary, randomly generated strings are difficult to remember, especially if the user is having many passwords. In this paper we present a dynamic password scheme based on patterns, called PassPattern System (PPS), which works using the existing infrastructure. PPS is an Adaptive Authentication System, where the strength of the system can be changed depending on the need of the application without compromising the user comfort. Keywords: User Authentication, Security.
1 Introduction "Open, Sesame!" is a classical example of using a SecretWord/Password in the famous tale Ali Baba and the Forty Thieves [1] to open the door of the magical cave. Since then SecretWord/Password has been used to authenticate the user before accessing any resource. With the advancement in computers, Internet and electronic commerce, authentication has become increasingly important. One of the main problems with the username-password scheme is ‘selection of the password’ itself. Studies show that users will always pick passwords which are short and easy to remember [2]. Often it is very easy to break the password of the user, if the personal information about him/her is known and more often than not, it is widely known. With technological advancement, alternative authentication schemes are reported in literature, which are more secure than the conventional Password-based scheme using Biometrics, RSA SecurID® [3], and Graphical passwords [4]. Each mechanism has its own advantages and disadvantages. One of the main reasons why password is still widely used is that newer technologies entail significant changes in the infrastructure of the system. Besides, the vulnerabilities of Graphical Passwords are still not fully understood and is an active area of research [4]. It appears that the need of the hour is to design an authentication scheme that is easy and intuitive to use, strong and robust against all possible attacks, and works using the existing hardware/software infrastructure. A. Das et al. (Eds.): NETWORKING 2008, LNCS 4982, pp. 162–169, 2008. © IFIP International Federation for Information Processing 2008
PassPattern System (PPS): A Pattern-Based User Authentication Scheme
163
In this paper we present the PPS, which is a dynamic password authentication system, where the user will prove to the system that he/she knows the secret instead of communicating it directly. PPS can be visualized as a challenge-response system, where in the response to a challenge is hardly reusable, there by rendering the replay attack or its variant ineffective. 1.1 Related Work There are several attempts reported in literature about authentication schemes in lieu of the traditional Password-based system. While each attempt is successful in increasing the strength of the system against some of the known attacks, they are either computationally intensive or they require additional hardware/software in the infrastructure. In this section we review the contemporary attempts, identify the gaps, and highlight the motivation for developing PPS. Password-based authentication. Password system is the oldest and the most popular authentication scheme used in the modern world. But users tend to choose simple passwords, which are easy to remember but they are very easy to break [2,5]. One way of preventing this is to provide users with a random password. While it is difficult for the user to remember, with contemporary computing power even a computer generated random password of length 8 characters is not strong enough for bruteforce attack; With Blue Gene/L1, it will take 1 hour to break password of length 10 characters. According to Microsoft “A strong password should appear to be a random string of characters to an attacker. It should be 14 characters or longer, (eight characters or longer at a minimum)” [6]. While it is recommended that user should not use same password for more than one account, it is quite common that the users have more than one online profile. Besides, users have to maintain a separate account for e-mail, social networking, e-banking, e-commerce, blogging, multimedia sharing, etc. Remembering a 14 character password for each account is difficult. The other way of increasing the strength of the password system is to make the password dynamic, i.e. the user has to enter a different password every time he/she does a login. But existing dynamic password or One-Time Password schemes either require extra hardware or complex mathematical operations. Biometrics. Biometrics comes under the category of authentication systems which use ‘What the user is’. The main disadvantage with any biometric system is the need for a change in the infrastructure of the entire system. For example if Yahoo wants to replace its authentication system from password to fingerprint based authentication, all the users have to install fingerprint readers on their computers and Yahoo should maintain a registry. This kind of change in infrastructure may not be feasible always. Moreover, biometrics are not often secret [7], as people publicly expose their voice and fingers in various ways on a regular basis, creating the possibility of biometric spoofing. For biometrics like Retina-based authentication and Vein-based authentication, spoofing is not possible but the installation cost is very high. Graphical passwords. The main idea of Graphical passwords [4] is that users find it easy to remember Graphical passwords than text-based passwords. Graphical 1
IBM Blue Gene is the current fastest super computer. [www.research.ibm.com/bluegene/]
164
T. Rakesh Kumar and S.V. Raghavan
passwords are more secure than text-based passwords from various attacks like dictionary attack, bruteforce attack and spyware. Some of the problems with the graphical passwords are that the users tend to choose the same sequence of images as their password making it easy to guess; Graphical passwords require much more storage than conventional text-based passwords. RSA SecurID®. RSA SecurID® is a two-factor authentication. It is based on something you know (a password or PIN) and something you have (an authenticator). RSA SecurID® is one of the dynamic password systems, where the user password will change for every login. Issues that cause concern are the cost and the possible of loss of physical devices. Virtual keyboard. Virtual keyboard is yet another user authentication system, where the user has to enter his/her password by clicking the characters on a virtual keyboard instead of typing the password on the conventional keyboard. While such a system is good against keyloggers and spywares, it is susceptible to other attacks like Shoulder surfing, guessing, and Social Engineering. Motivation for PPS. The discussions hitherto underline the need for an authentication system, that is simple, easy-to-use, inexpensive, incorporates the essence of challenge-response system, dynamically changing, robust against attacks such as bruteforce, dictionary, shoulder surfing, spyware, social engineering, ManIn-The-Middle attack and all above doesn’t demand any special hardware/software.
2 PassPattern System PassPattern System is a challenge-response system and is based on the premise that ‘humans are good at identifying, remembering and recollecting graphical patterns than text patterns’ [8]. The core idea of PassPattern system is that, ‘Instead of remembering a sequence of characters as the secret, users have to remember a shape (which is stored internally as a sequence of positions in hash form) as the secret’. Whenever the user wants to get authenticated, the PPS displays an NxN matrix of cells, which is known as PatternSquare. Each cell in the PatternSquare is an image, which represents a character as shown in Fig. 1(a). The character can be an alphabet, number or even special characters. The PatternSquare is the challenge that is sent by the server to the user. The PatternSquare will be generated dynamically upon each user request. Hence the characters in each cell of the PatternSquare may change or their position may change or both may change, for every authentication request. At the time of registration the user is asked to choose a sequence of positions as shown in Fig. 1(b), by typing the characters in those positions. The sequence of positions then becomes the user’s PassPattern. The cell sequence of the PassPattern so chosen will remain the secret between the user and the system. The user has to remember only the shape (cell sequence in the PatternSquare) as that is the only secret. For the user to get authenticated, he/she has to type the characters that are present in the chosen shape (PassPattern) in the PatternSquare. The cells in the PatternSquare are colored2 in such a way that, the user can see smaller 2
To enhance user convenience; no relationship to security of the PPS.
PassPattern System (PPS): A Pattern-Based User Authentication Scheme
(a)
165
(b)
Fig. 1. (a) A sample PatternSquare. This is the sample of the image that the user will see, whenever he/she wants to login to the system. (b) A sample user choice of a PassPattern. A user can choose any sequence of positions as the PassPattern.
subsections of the PatternSquare (3 x 3 in our example), which makes it easy for him to remember his PassPattern. Whenever the user wants to login to the system, the user has to type the sequence of characters which appear in the user’s PassPattern presented by the system as a challenge (This sequence of characters is referred to as SecretWord). During every presentation of the PatternSquare, the contents change and hence the user has to type a different SecretWord as shown in Fig. 2, during every authentication process such as login.
Fig. 2. The above figure shows PatternSquares that are displayed to the users at different login attempts. SecretWords corresponding to the PassPattern in Fig. 1(b) will be “t?X4”, “@?7-” and “b-97”.
2.1 Design Issues PPS allows users to choose any set of characters as their PassPattern. The user can select the PassPattern based on some sequences familiar to him/her, for example knight’s moves on a chess board or some symmetric positions. Because of the coloring2 of the cells, remembering the PassPattern will be easy. The PPS comprises of 4 parts - PPS software, Pseudo-Random number generator, Image generator, and PassPattern database. PPS software controls all activities in the system, Pseudo-Random number generator and Image generator are used to create dynamic challenges and PassPattern database stores all the PassPatterns of the users. Internally the cells of the PatternSquare are indexed in row-major order (and left to
166
T. Rakesh Kumar and S.V. Raghavan
right), starting from 0 to N2-1 (where N is the size of the matrix). Hence the PassPattern of a user will be stored as a string of numbers. Both PassPattern and usernames will be stored in the database as Hash, using MD5 hash function. Registration phase. Whenever a user sends a request for new registration, the server will create two S-seeds based on the “current clock time” (This seeds are valid only for that session at the server). Using S-seeds as the seed values, the Pseudo-Random generator will (randomly) pick two sets of 49 characters (for a 7x7 matrix) out of 94 printable characters in ASCII. The Image generator takes these characters and creates two sets of 49 images and sends the images to PPS Software. PPS Software creates two PatternSquares using the images and sends them to user as challenges. These two challenges are similar to the process of retyping the password in traditional password systems at the time of registration. The S-seed values are preserved as the session variable (in physical memory) for the verification phase.
(a)
(b)
Fig. 3. (a) Registration phase in the PPS. (b) Validation and Creation of the user account.
Once the user gets these two challenges, the user has to type the username and SecretWords. The SecretWords will be based on the user selection of the PassPattern. The PPS checks both the PassPatterns and if they are same, then the PPS calculates the MD5 Hash of the username and PassPattern and stores them in the PassPattern database and acknowledges the successful registration to the user. The Authentication phase. Whenever a user makes a login or authentication request, the PPS Software creates the PatternSquare (similar to the registration phase) and sends it to the user as a challenge. Once the user gets the challenge, the user has to type the username and the SecretWord which is based on his/her PassPattern and the PatternSquare (Secret and Challenge). The PPS software calculates the MD5 Hash of the username and PassPattern and compares the result with the value stored in the PassPattern database. Based on the comparison results, the user will be either allowed or rejected.
PassPattern System (PPS): A Pattern-Based User Authentication Scheme
(a)
167
(b)
Fig. 4. (a) Challenge creation phase in the PPS. (b) Response validation phase in the PPS.
Other Design Issues. PPS is an adaptive user-authentication system. The strength of PPS can be adapted for various situations. The strength of the PPS can be varied by changing two parameters – the size of the PatternSquare and the type of image. The first method is to change the size of the PatternSquare, i.e. the more the size, more is the security. Number of possible patterns of length n in an NxN matrix will be (N2)n. Thus, as the size of PatternSquare (N) increases, the total possible number of PassPatterns will increase, which in turn increases the strength of the system. The second method of increasing the security is by changing the type of the image in the PatternSquare. The strength of the system can be drastically improved by changing the type of the image. Each character in the PatternSquare can be represented with different coding, compression, noise, distortion, and even as a CAPTCHA3 image.
3 Security Strength of PPS In general, several attacks are possible on an authentication system. For any authentication system, the hacker can attack at least at three places; they are server, client, and the communication link. The different attacks on sever includes Bruteforce attack, Dictionary attack, attack on PassPattern database, and compromising the server as a whole. At the client, the possible attacks are keylogging and shoulder surfing. Finally on the communication link, the possible attack is Man-In-The-Middle attack, which can be done using packet sniffers. In terms of the data being passed from the user to the server and the data which is being stored in the server PPS is comparable with the classical Password-based authentication system. In both cases, user sends the username and a SecretWord and this will be compared with the registry in the database. But because of the dynamic nature of the challenge-response system, PPS is more secure than Password-based scheme to attacks such as Bruteforce, Dictionary attack, Keylogger, and Shoulder surfing. For the rest of the attacks, PPS is as vulnerable as Password-based schemes 3
CAPTCHA (Completely Automated Public Turing test to tell Computers and Humans Apart) is a test used in computing to determine whether the user is human. For more information on the CAPTCHA refer [http://www.captcha.net].
168
T. Rakesh Kumar and S.V. Raghavan
(e.g. Server database compromise attack). The best known solution for such attacks is to use cryptography protocols at the server or on the communication link. In this section we analyze the impact of the four attacks mentioned here on PPS. Bruteforce attack. The hacker can try two kinds of Bruteforce attacks on this system. The first way of attacking the system is to ignore the PatternSquare and try with some random string. For a user PassPattern of length 4, there will be a unique SecretWord for the given session. If the hacker wants to guess that SecretWord, the probability of success will be 1/(944) = 1.28x10-8 (Since there are 94 printable characters). If the guess is wrong the probability of success will remain same for the next guess, it is because the SecretWord will change with every attempt. Hence, The probability of success for every attempt =
1 94n
(1)
The other way of doing Bruteforce search is to try all combinations of positions. For example, if we consider a 7x7 PatternSquare there will be 49n (if selection of PassPattern includes reuse of positions) or 49Pn (without reuse of positions) different patterns of length n. ⎧( N 2 ) n ⎪ Number of possible PassPatterns = ⎨ N 2! ⎪ ( N 2 − n)! ⎩
(2)
To break the system, the hacker on an average has to break (nx49n)/2 images (with reuse) or (nx49Pn)/2 (without reuse). ⎧ n × ( N 2 )n ⎪ 2 ⎪ Number of images that are to be broken = ⎨ (3) n × N 2! ⎪ ⎪⎩ 2 × ( N − n)! N represents the size of the PatternSquare and n represents the length of the PassPattern. Dictionary attack. Dictionary attack is one of the most commonly used techniques to break a Password-based system. In the case of PPS commonly used shapes, sequences can be possible candidates in a dictionary. However, as the PatternSquare changes randomly on every presentation, it approaches the behavior of one-time pad. Keyloggers. Keylogger is a program, which captures the user’s keystrokes and sends this information to the hacker. The natural protection for an authentication system from the keylogger is to have a one-time password (or Dynamic password). PPS being a dynamic password system, is not vulnerable to keyloggers. Even if the hacker gets the SecretWord of the user of a PPS system, this SecretWord cannot be reused by the hacker to login to the system, because of the dynamic nature of the PatternSquare. Shoulder surfing. Shoulder surfing is looking over someone’s shoulder when they enter a password or a PIN code. It is an effective way to get information in crowded places because it is relatively easy to stand next to someone and watch as they fill out a form, enter a PIN number at an ATM machine, or use a calling card at a public pay
PassPattern System (PPS): A Pattern-Based User Authentication Scheme
169
phone. Shoulder surfing can also be done at a distance with the aid of binoculars or other vision-enhancing devices to know the password. Shoulder surfing can be done easily on the password system, just by seeing the keys that the user is typing. But to decode the PassPattern in the PPS, the hacker has to see both the key sequence and the PatternSquare and do a mapping before the user submits the page. So shoulder surfing is of little or no use in PPS as compared to a Password-based system.
4 Conclusion In this paper we presented PPS, a user authentication system which can be a potential replacement to classical Password-based authentication system. The strength of the system can be changed by varying the size of the PatternSquare and the type of image associated witch each cell of the PatternSquare without increasing the length of the PassPattern. PPS is very easy for the user to use and at the same time it is more secure than conventional Password-based system. An existing Password-based system can be migrated to PPS, without any change in the infrastructure. Some of the open problems in this area are: What is the ideal length of the PassPattern? What is the ideal size of the PatternSquare? What is the general user behavior while choosing a PassPattern? Prototype of the PPS is available at http://netlab.cs.iitm.ernet.in/pps
References 1. McCaughrean, G.: One Thousand and One Arabian Nights, USA. Oxford University Press, Oxford (1999) 2. Adams, M.A., Sasse, M.S.: Users are not the enemy: why users compromise computing security mechanisms and how to take remedial measure. Communications of the ACM 42(12), 40–46 (1999) 3. RSA Security Inc. RSA SecurID® authenticators, http://www.rsasecurity.com 4. Suo, X., Owen, Y.Z.: Graphical Passwords: A Survey. In: 21st Annual Computer Security Applications Conference (ACSAC 2005), pp. 463–472 (2005) 5. Gilhooly, K.: Biometrics: Getting Back to Business. Computerworld (May 09, 2005) 6. Strong passwords: How to create and use them, http://www.microsoft.com/ protect/yourself/password/create.mspx 7. Brainard, J., Juels, A., Rivest, R.L., Szydlo, M., Yung, M.: Fourth-Factor Authentication: Somebody You Know. In: Proceedings of the 13th ACM conference on Computer and communications security, pp. 168–178 (2006) 8. Shepard, R.N.: Recognition memory for words, sentences and pictures. Journal of verbal Learning and verbal Behavior 6, 153–163 (1967)
A Secure and Efficient Three-Pass Authenticated Key Agreement Protocol Based on Elliptic Curves Meng-Hui Lim1 , Chee-Min Yeoh1 , Sanggon Lee2 , Hyotaek Lim2 , and Hoonjae Lee2 1
Department of Ubiquitous IT, Graduate School of Design & IT, Dongseo University, Busan 617-716, Korea {menghui.lim,yeohcm}@gmail.com 2 Division of Computer and Information Engineering, Dongseo University, Busan 617-716, Korea {nok60,htlim,hjlee}@dongseo.ac.kr
Abstract. Key agreement protocol is of fundamental importance in providing data confidentiality and integrity between two or more parties over an insecure network. In 2004, Popescu [14] proposed an authenticated key agreement protocol in which its security is claimed. However, Yoon and Yoo [19] discovered its vulnerabilities two years later and proposed an improved variant of it. In this paper, we highlight the vulnerability of this improved variant under the LaMacchia et al.’s extended Canetti-Krawczyk security model [12]. With this, we propose another enhanced version of Popescu’s protocol which offers stronger security features and appears to be significantly more efficient than Yoon-Yoo’s scheme. In order to justify our claims, we present a thorough heuristic security analysis on our scheme and compare the computational cost and security attributes with the surveyed schemes.
1
Introduction
Authenticated key agreement protocol is essential for two or more specific entities to communicate securely over an open network (e.g. the Internet), in which the communication can be fully controlled by adversaries. The protocol must be properly designed in such a way that at the end of the protocol execution, both communicating parties can be assured of each other’s identity and agreed on an unique shared secret key (also known as session key) based on the information contributed equally by each party. Once the key agreement is successfully carried out, the derived session key can be used subsequently to create a confidential channel particularly for preserving data confidentiality and integrity. Therefore, an authenticated key agreement protocol should strictly prohibit other unauthenticated parties aside from the intended protocol participants from gaining access to the shared secret under any circumstances.
This work was supported by MIC of Korea, under ITRC support program supervised by IITA (IITA-2007-C1090- 0701-0026).
A. Das et al. (Eds.): NETWORKING 2008, LNCS 4982, pp. 170–182, 2008. c IFIP International Federation for Information Processing 2008
A Secure and Efficient Three-Pass Authenticated Key Agreement Protocol
171
Key agreement protocols can employ symmetric or/and asymmetric cryptography in its construction. Generally, symmetric protocols require a common secret key to be shared in prior between the communicating parties whereas asymmetric or public key-based protocols require the communicating entities to learn only specific authenticated public information of their peer (such as identity, public key, etc.), which is usually exchanged via certificates. This paper is concerned with two-party authenticated key agreement protocols in the asymmetric settings. Over the years, there has been overwhelming interest in the use of public keybased cryptography, mainly due to the employment of elliptic curve operations in constructing cryptographic key agreement protocols. However, as designing a secure and efficient protocol is far from being a simple task, many protocols have been proven to be fallible. Strangio [16], in 2005, has proposed an efficient two-party elliptic curve based key agreement protocol, namely ECKE1, which is believed to be secure at the first glance since the security attributes are well discussed in his work. Unfortunately, Wang et al. [18] have revealed a weakness in Strangio’s protocol recently. Specifically, they have presented a valid key compromise impersonation attack on it. Besides, Duraisamy et al. [8] have also pointed out a similar attack independently. To defeat the vulnerability of ECKE1, Wang et al. [18] and Strangio [17] have proposed their revised version of ECKE1, namely ECKE1N and ECKE1R respectively at the expense of a higher computational workload. In 2004, Popescu [14] has proposed another notable key agreement scheme, in which the author claimed such protocol to be secure and more efficient than the exisitng ones due to its low computational cost required at both communicating entities. However, in 2006, Yoon-Yoo [19] have subverted Popescu’s claim by exploring a series of cryptographic attacks which encompass a key-compromise impersonation attack, a reflection attack and a replay attack. Subsequently, Yoon-Yoo have proposed another improved scheme [19] in order to defeat these vulnerabilities. To justify their claims on the security of their protocol, they have demonstrated a detailed heuristic security analysis on it. In this paper, we point out that Yoon-Yoo’s improved scheme [19] does not seem secure when both ephemeral keys of a specific completed session are exposed to a passive adversary who only eavesdropped on the session. This compromise of session-specific secret information is regarded as one of the essential attacks captured by the extended Canetti-Krawczyk security model [12]. Based on the shortcoming, we propose another improved variant of Popescu’s protocol [14] and we claim that our protocol is able to achieve a stronger and higher sense of security and efficiency as compared to Yoon-Yoo’s scheme. The structure of this paper is organized as follows. In Section 2, we illustrate the basic concepts needed to evaluate the security properties of a key agreement protocol and define the elliptic curve as well as several hard cryptographic problems. In section 3, we revisit Yoon-Yoo’s improved scheme and illustrate its insecurity. We propose an efficient three-pass authenticated key agreement protocol and evaluate its security in sections 4 and 5 successively. In Section 6, we compare our scheme with
172
M.-H. Lim et al.
the other existing key agreement schemes in terms of computational efficiency and security. Lastly, we conclude this paper in Section 7.
2 2.1
Preliminaries Security Properties of Key Agreement Protocol
There are numerous security attributes that have been defined and discussed, specifically for the analysis of the key agreement protocols. The most fundamental property of a key agreement protocol is the passive attack resilience, that is, the protocol should be able to prevent the adversary from obtaining the session key or any other useful information (such as ephemeral keys) by merely eavesdropping on the protocol. On top of that, we also assume that the adversary has full control of the communications on the open network, such that the adversary is capable of intercepting, deleting, injecting, altering and replaying messages in any online instance of the key agreement protocol. These potential attacks has in fact led to the additional security properties: known session key security, perfect forward secrecy, key compromise impersonation resilience, unknown key-share resilience and key control resilience. Please refer to Blake-Wilson and Menezes’s definition of these security attributes [4,3] for an excellent overview. 2.2
Elliptic Curve Cryptography
The notion of elliptic curve cryptography was first introduced independently by Miller [13] and Koblitz [10]. Since then, numerous elliptic curve cryptosystems have been proposed and employed. The main attraction of it is that it allows much smaller parameters (e.g. key size) to be employed in order to achieve an equivalent level of security as compared to the traditional public-key cryptosystems such as RSA and DSA. Since an elliptic curve cryptosystem, that is mainly based on the intractability of Elliptic Curve Discrete Logarithm Problem (ECDLP), takes full exponential time, its resistance against the sub-exponential attack offers potential reductions in processing power and memory size which is essential in applications on constrained devices [15]. Let E(Fq ) be an elliptic curve of defined over a finite field Fq of characteristic p. The public elliptic curve domain parameters over Fq is defined as a 8-tuple (q, F R, S, a, b, P, n, h), where q is the prime order of the field, F R (field representation) indicates the representation used for the elements of Fq , S is the random seed for elliptic curve generation, the coefficients a, b ∈R Fq define the equation of elliptic curve E over Fq (y 2 = x3 + ax + b for p = q > 3, where 4a3 + 27b2 = 0), the base point P = (xp , yp ) in E(FQ ), the prime n is the order of P (n > 2160 ) and the cofactor h = E(FQ )/n, where E(FQ ) denotes the number of FQ -rational points on E. These parameters should be chosen appropriately to prevent the employment of any efficient algorithm from solving the Discrete Logarithm Problem (DLP) or the computational Diffie-Hellman Problem (CDHP) in the cyclic subgroup P [16].
A Secure and Efficient Three-Pass Authenticated Key Agreement Protocol
173
Since many cryptographic primitives base their security on the underlying assumptions in which the DLP and CDHP on some cyclic groups are intractable, our proposed key agreement protocol would not be exceptional. Our protocol also rests upon a few related conjectures before its security can be claimed. Now, we define several cryptographic problems which we will assume their hardness throughout this paper. Conjecture 1 (ECDLP). Let E(Fq ) and P be defined as above. The Elliptic Curve Discrete Logarithm Problem is said to be intractable if for any probablilistic polynomial time Turing Machine A with the knowledge of Y = xP , where Y ∈ P , the probability of success in computing logP Y = x ∈R ecdlp [1, n − 1], denoted as SuccP,E(Fq ) (A) is negligible: ⎡
⎤ x ∈R [1, n − 1]; ecdlp ⎦ ε, Y = xP ; SuccP,E(Fq ) (A) = P r ⎣ A(n, P, Y ) = logP Y where the probability is taken over the coin tosses of A for any random choice of x. Conjecture 2. (ECCDHP). Let E(Fq ) and P be defined as above. The Elliptic Curve Computational Diffie-Hellman Problem is said to