ISSN 2319 - 6629 Volume 3, No.5, August – September 2014 Manpreet Singh et al., International Journal of Wireless Communications and Network Technologies, 3(5), August – September 2014, 78-81
International Journal of Wireless Communications and Networking Technologies Available Online at http://warse.org/pdfs/2014/ijwcnt01352014.pdf
A Novel Approach to Minimize End-to-End Delay in Wireless Sensor Network 1
2
Manpreet Singh1, Priyanka Dayal2
PG Student, ECE, Punjab Institute of Technology, Kapurthala, India, E-mail: reet_0987@hotmail.com. Assistant Professor, ECE, Punjab Institute of Technology, Kapurthala, India, E-mail: priyanka23dayal@gmail.com.
ABSTRACT In wireless sensor network, end-to-end delay is considered to be an important QoS metric, also for any application that involves small-sized files transmission. In this paper, we focus on how to minimize the end-to-end delay in WSN. The term end-to-end delay is defined as the total time taken by a single packet to reach the destination. It is a resultant of many factors including the interference level along the path, the length of the routing path and number of hops in the routing path. In this paper, we present SPR and a transmission scheduling scheme that minimize the end-to-end delay along a provided route. Our proposed scheme is based on integer linear programming and it also involves interference modelling. Using this scheme, there is no conflict in the transmission at any time. Simulation is done in MATLAB and through simulation, our proposed SPR and link scheduling scheme has shown significant reduction in end-to-end delay regardless of other routing algorithm used.
(a)
Keywords: FCFS, SPR, SCH, SPR+SCH, WSN 1.
INTRODUCTION (b)
In a wireless sensor network, sensor nodes are powered by small batteries that cannot be charged or replaced. Hence, sensors can only send a finite number of bits from source to sink until they run out of energy. End-to-end delay is considered to be the major metrics for quality of service. Both data rate and end-to-end latency is a combined effect for userperceived data transfer speed. For the transmission of smallsized file, end-to-end delay is the dominating factor and for transferring a large-sized file, the dominating factor is the data rate. In wireless sensor network, where sensor nodes need to be periodically reported to the sink, end-to-end delay plays an important role.
Figure 1: (a) With maximum throughput routing, latency is 7 slottime; (b) With minimum delay routing, latency is 5 slot-time.
For the given network in Figure 1, a maximum throughput routing algorithm would prefer (a). Since the total throughput is more than that of the single path. Whereas a minimum delay routing algorithm would prefer (b) since it is the shortest route and also there is no interference from any other data flows. Basically the two routing algorithms with different objectives result in different paths. In the example shown in Figure 1, minimum delay happens to have the shortest path. In this paper we will show that shortest path always leads to the minimum delay is a misbelieve. In fact, end-to-end delay is a combined result of both the interference level along the path and the number of hops on the path. The shortest path leads to the minimum delay only if it is the least interfered path.
In past years, we have seen many papers regarding how to maximize throughput in WSN [1]-[8]. Moreover, the solution that enhances network throughput often neglects the aspect of delay and leads to poor results in end-to-end latency. The more preference is provided to the path with less number of hops without considering the factor that it has certain demerits also that leads to end-to-end delay. 78
Manpreet Singh et al., International Journal of Wireless Communications and Network Technologies, 3(5), August – September 2014, 78-81 interference modelling, the related work includes [1]-[6]. [1] uses the conflict graph that model the effect of wireless interference under a simplified protocol model; [3] continued to use conflict graphs to model interference under the IEEE 802.11 interference model; [6] focused on estimation of interference and studied the effect of interference on aggregated network throughput based on the IEEE 802.11 model; [4] proposed a physical interference model based on the measured interference rather than the distance between the nodes. Our previous work [9] did joint routing and link rate control using a different interference model for directed graphs.
(a)
Delay optimization is very important in wireless sensor networks, has been approached from routing, MAC layer scheduling or both. [10] presented in sensor networks when the routing tree is given, how to determine the time slot of each node such that the maximum latency to send the packet from a node to the sink is minimized. [11] presented an algorithm to find the optimal routing paths between the sensor and the sink with the objective of minimizing the total end-to-end delay. [12] presented approximation algorithms for minimum latency aggregation in sensor networks, which computes on aggregation tree as well as time slot assignment for links so that the timespan of the schedule is minimized.
(b) Figure 2: (a) With a single data flow S1 _ D1; (b) With two data flows S1 _ D1 and S2 _ D2. Numbers on links are slot numbers. There are 5 distinct slot numbers.
As interference works adversely for throughput in the same way it does for delay. Suppose to transmit one packet each slot is used and a packet is scheduled so that it can use the very next available slot as soon as it arrives. In Figure 2(a), as there is only one data flow (from S1 to D1), so the end-to-end delay is 6 slots. In Figure 2(b), there are two flows interfering with one another, so the end-to-end delay from S1 to D1 is increased to 10 slots.
3.
When there is multiple numbers of data flows in the network, it is not straight forward to find out the optimal transmission schedule that would leads to the minimum delay. In this paper, we propose a linear programming-based data aggregation scheduling scheme with SPR that compute time slot assignment in order to minimise end-to-end delay without having any conflict in transmission. The main contribution of our paper is that we have introduced a linear model to closely study the impact of interference on network delay in multi hop wireless network. Comparison with previous linear models, our linear model is more accurate; and also compared to exact solution, which is NP-hard for computation, our solution is more efficient one.
We assumed that the channel time has been divided into superframes. Each super-frames contains F number of distinct time slots, and the slot duration is enough large for transmission of single packet. In this paper we focused on the centralized scheduling scheme; the distributed implementation of this will be addressed for researches in future work. When an intermediate node forwards a packet, there is a mandatory store and forward delay and a scheduling delay. While the total of store-and-forward delay is decided by the total number of hops in the route, the scheduling delay has to be decided by the particular transmission schedule, which is influenced by the interference from other sensor nodes. Providing routing information, we can further minimize end-toend delay by optimizing link scheduling. End-to-end delay is related to both the scheduling delay at each relay node and the total number of hops. When the routing information is given, the delay factor can be optimized.
The rest of the paper is organised as follows. In section 2, we briefly survey the related work on delay optimization and interference modelling in recent years; in section 3, we present a linear programming based scheduling scheme with SPR; in section 4, we validate our model by simulation results. And at last, section 5 concludes the paper. 2.
MINIMUM DELAY SCHEDULING WITH SPR
To achieve minimum scheduling delay with SPR, we first formulate it as an optimization problem. As the routing information is provided, so we use 1 to indicate link l is having flow on the path, otherwise 0. To transmit packet from source to destination we follow SPR with the scheduling scheme i.e. data is aggregated from sources to a single aggregation node
RELATED WORK
We firstly surveyed the interference modelling, and then we review recent work in the optimization of delay. For 79
Manpreet Singh et al., International Journal of Wireless Communications and Network Technologies, 3(5), August – September 2014, 78-81 using SPR and then transmitted to the sink. So that there will be less interference in the network and hence end-to-end delay will be minimized. 4.
Figure 3 shows the end-to-end delay for SPR+SCH with respect to number of nodes. Delay is the difference of time period of time period between the data sending at the sender’s end and the data receiving at the receiving end. It shows the delay time of all successfully transmitted data from source end to the receiving end. For the scenario with 40 nodes the delay obtained is 21.0151, for 60 nodes the delay obtained is 39.7396 and for that of 80 nodes the delay obtained is 55.0595. It is shown in the graph that maximum delay is for 80 nodes and minimum is for 40 nodes when delay plotted in a common graph for all three scenarios with respect to number of nodes.
SIMULATION
In this section, results of SPR+SCH and simulation parameters are shown. A routing scheme Shortest Path Routing (SPR), and a link level scheduling algorithm SCH is used. SCH uses the routing information from the network layer for link level transmission scheduling and can be used with any routing algorithm. In SCH, an aggregation node is selected which collected the data from the near source nodes in its range by SPR. In SPR, a router choose the shortest path (in hops) to reach the destination regardless of other transmissions.The tool used for simulation is MATLAB. It is a high performance language used for technical computing, and makes programming in an easy to use environment where it is easy to implement mathematical formulae of particular problem and its solution. Table 1, shows the parameters used for the simulation, we create three scenarios, where we use 40, 60 and 80 nodes deployed in a 150m*150m square region, with node transmission range 30m. 20% nodes are selected randomly as source nodes. Each source node sends data and through multihop forwarding the data is delivered to the destination. For each scenario, we repeat the simulation by varying number of nodes and obtained the delay. Table 1 Simulation Parameters for SPR+SCH
Parameter Name
Parameters
Channel type
Channel/ wireless
Radio Propagation
Two Ray Ground
Antenna Type
Antenna/ Omni Antenna
Link Layer type
LL
Area of network Number of nodes
150m * 150m 40, 60 and 80
Network Interface Type
Phy/Wireless Phy
Position of sink Range
150,150 30
Routing protocol
SPR
Source nodes
20%
Figure 3: Delay graph of SPR+SCH
Figure 4: Comparison graph between proposed technique and existing techniques
80
Manpreet Singh et al., International Journal of Wireless Communications and Network Technologies, 3(5), August – September 2014, 78-81 In the Figure 4, the comparison graph is obtained between the proposed technique and existing techniques on the basis of delay with respect to number of nodes. By our results we concluded that our proposed technique has minimum delay when compared with that of existing techniques or we can say that our proposed technique transmit more data than that of existing techniques.
[2] S. Rangwala, R. Gummadi, R. Govindan, and K. Psounis, “Interference-aware fair rate control in wireless sensor networks,” in SIGCOMM ’06: Proceedings of the 2006 conferenceon Applications, technologies, architectures, and protocols forcomputer communications. New York, NY, USA: ACM, 2006,pp. 63–74. [3] Y. Li, L. Qiu, Y. Zhang, R. Mahajan, Z. Zhong, G. Deshpande, and E. Rozner, “Effects of interference on wireless mesh networks: Pathologies and a preliminary solution,” in HotNets2007, Nov. 2007. [4] L. Qiu, Y. Zhang, F. Wang, M. K. Han, and R. Mahajan, “A general model of wireless interference,” in MobiCom ’07:Proceedings of the 13th annual ACM international conferenceon Mobile computing and networking. New York, NY, USA: ACM, 2007, pp. 171–182. [5] Y. Li, L. Qiu, Y. Zhang, R. Mahajan, and E. Rozner, “Predictable performance optimization for wireless networks,” in SIGCOMM ’08: Proceedings of the ACM SIGCOMM 2008conference on Data communication. New York, NY, USA: ACM, 2008, pp. 413–426. [6] J. Padhye, S. Agarwal, V. N. Padmanabhan, L. Qiu, A. Rao, and B. Zill, “Estimation of link interference in static multihop wireless networks,” in IMC ’05: Proceedings of the 5th ACMSIGCOMM conference on Internet Measurement. Berkeley, CA, USA: USENIX Association, 2005, pp. 28–28. [7] M. Kodialam and T. Nandagopal, “Characterizing achievable rates in multi-hop wireless networks: the joint routing and scheduling problem,” in MobiCom ’03: Proceedings of the9th annual international conference on Mobile computing andnetworking. New York, NY, USA: ACM, 2003, pp. 42–54. [8] M. Alicherry, R. Bhatia, and L. Li, “Joint channel assignment and routing for throughput optimization in multiradio wireless mesh networks,” in ACM MobiCom, 2005. [9] M. Cheng, X. Gong, and L. Cai, “Link rate allocation under bandwidth and energy constraints in sensor networks,” in IEEEGLOBECOM, Dec. 2008, pp. 1–5. [10] P. Chatterjee and N. Das, “A cross-layer distributed tdma scheduling for data gathering with minimum latency in wireless sensor networks,” in Wireless VITAE 2009, May 2009, pp. 813 – 817. [11] F. Sivrikaya and B. Yener, “Minimum delay routing for wireless networks with stdma,” Wireless Networks, vol. 15, no. 6, pp. 755–772, October 2007. [12] P.-J. Wan, S. C.-H.Huang, L. Wang, Z. Wan, and X. Jia, “Minimum-latency aggregation scheduling in multihop wireless networks,” in MobiHoc 09, 2009, pp. 185–194.
The existing techniques used for the comparison are SPR+MinDelay and SPR+FCFS. Also we observed that no matter which MAC layer scheduling scheme is used, SPR always performs better. And in table 2, the tabular representation of proposed technique and other existing techniques is represented for three scenarios by varying the number of nodes that is for 40, 60 and 80 nodes. Table 2 Comparison table of delay for Proposed Technique with Existing techniques
5.
NUMBER OF NODES
SPR + MinDelay
SPR + FCFS
Proposed Technique
40
23
39
21.0151
60
40
70
39.7396
80
65
129
55.0595
CONCLUSION
In this paper, we worked on important problem in practice: given a multi hop wireless sensor network having multiple data flows, the way to achieve the minimum end-to-end delay. This paper presented a proposed technique SPR+SCH, in which the impact of interference is considered. Our proposed technique guarantees collision-free transmission and also does not need to solve the NP-hard clique problem.The model for optimization is very useful for feasibility analysis for a given set of Quality of Service constraints, and also for improving delay when routing information is provided. REFERENCES [1] K. Jain, J. Padhye, V. N. Padmanabhan, and L. Qiu, “Impact of interference on multi-hop wireless network performance,” in MobiCom ’03: Proceedings of the 9th annual internationalconference on Mobile computing and networking. NewYork, NY, USA: ACM, 2003, pp. 66–80.
81