Time Petri Net model for CL-MAC with Packet Loss Protocol in Wireless Sensor Networks Ahmed Louazani Larbi Sekhri Computer Science Department, Computer Science Department, University of Oran1, Ahmed Benbella, Algeria University of Oran1, Ahmed Benbella, Algeria Industrial Computing and Networking Laboratory, Industrial Computing and Networking Laboratory, ahmedlouazani@yahoo.fr larbi.sekhri@univ-oran.dz Abstract the sink. As mentioned in [Kec 08], [Kec 10], we have Wireless Sensor Networks (WSN) are described CL-MAC protocol and compared it with expected to operate as long time as possible in concurrent solutions. The two adjacent layers MAC and all applications and environments. Facing network exchange control information to find the energy challenge, software developers’ have shortest path to the sink so that all nodes belonging to to design save-energy programs. In this paper, the same path relying initiator node to the sink must be an extended version of CL-MAC (Cross- ready to route packets at the right moment. Any other Layer-MAC) is slightly presented dealing with node which is a neighbor to one path-node not packet loss problem modeled using Time Petri belonging to the path has to turn off its transceiver from net (TPN). TiNA (Time Net Analyzer) tool is the beginning to the end of the routing process. CL- used to validate the proposed model. The MAC considerably reduces energy consumption using obtained properties such liveness, only three communication packets (CTS, DATA, ACK) boundedness and reversibility prove the instead of four ones (RTS, CTS, DATA, ACK) unlike correct behavior of the new version of CL- other MAC protocols. Referring to energy consumption MAC where lost packets problem is solved. model [Est 99], [Kyu 14], and according to the node Basically, CL-MAC protocol was designed to radio characteristics, for each hop, CL-MAC saves the reduce both energy and latency. Its main amount of needed energy to communicate RTS packet engine is to wake-up only nodes within the (in [24], RTS packet size is equal to 118 bits). Hence, routing path. for only one hop communication, the amount of saved energy is calculated as follow (we assume that nodes are 10 meters distant): Keywords - Wireless Sensor Networks, Cross- ( ) layer Optimization, CL-MAC Protocol, Energy ( ) (1) consumption, Delay sensitive, Time Petri net. ( ) (2) 1. Introduction CL-MAC protocol has good performances under the In literature, many WSN protocols have been proposed following hypotheses: A safe network, pleasant to decrease energy wastage resources such as idle environment, flat topology and using control listening, over emitting, and collision. CL-MAC information of two adjacent networks’ layers (network [Kec 13], [Kec 10] is one of them and it was designed and MAC). These hypotheses bring us to spell out its for delay sensitive application such as forest fire vulnerability face to security issue [Yas 12]. In [Lou 14] detection and chemical industry monitoring. It’s an a defense mechanism for the CL-MAC protocol against energy efficient cross layer protocol, where MAC and wormhole attacks is presented. Another communication network layers share control information variables to issue remains hidden by the second hypothesis that our build routing table, neighbor list, and reserve a low paper deals with. In real environment field deployment, latency path from the source to many other communication handicaps occurs leading to Copyright © by the paper’s authors. Copying permitted only for private and academic purposes. In: Proceedings of the 3rd Edition of the International Conference on Advanced Aspects of Software Engineering (ICAASE18), Constantine, Algeria, 1,2-December-2018, published at http://ceur-ws.org Page 92 Time Petri Net model for CL-MAC with Packet Loss Protocol in Wireless Sensor Networks ICAASE'2018 packet loss like: interference, obstacle, impediment, and process or checks for an alternative one. Then, the nodes’ moving. So, to promise packet delivery, the interrupted communication will restart from the source node will retransmit to destination the no- beginning on the new calculated path (see figure 2). acknowledged packet. The next section deals with packet loss problem in CL-MAC. The remainder of this paper is structured as follows. Section 2 covers the new CL-MAC version reviews D A B C with packet loss problem. Section 3 uses TPN model for DIFS the proposed solution and experimental results are RTS given. Section 4 is reserved for the conclusion to RTS SIFS summarize the paper and propose futures works. CTS CTS SIFS 2. Proposed Solution Nav(RTS) Delay Delay DATA DATA Nav(CTS) To overcome the lost packet problem, two variables are SIFS added to CL-MAC algorithm: (i) Nb_transmission ACK variable to count the lost packet retransmission tentative ACK number, (ii) Waiting_delay a countdown variable to DIFS DIFS measure the estimated needed packet propagation time. When a source node wants to communicate with Figure 1: Exchanged packets between node A and another one (destination), four packets are exchanged node B between both nodes as shown in figure 1. Before sending its first packet “RTS”, node “A” sets waiting_delay variable to the estimated RTS packet propagation time value. This duration is the elapsed time from the injection of the first RTS bit in the network by node “A” till the reception of the last CTS D F J H bit by the same node as a replay. Hence, we formalize M the packet propagation time by equation (3). A B C G ( ) L E ( ) (3) I K Where  is the time for equation adjustment. Nb_transmission variable is set to one indicating that’s Old Path the first packet transmission. Then node “A” waits until New path waiting_delay variable expire. When it elapsed (waitin_delay = 0), node “A” concludes that his packet was lost (didn’t reach node “B”), then will fetch Figure 2: Path linking node G to node H is broken whether Nb_transmission didn’t exceed a given threshold retransmission number. In our proposed solution, we fix the threshold to 3 retransmissions of the same lost packet (here it’s fixed to 3 just to test the 3. Modeling CL-MAC Protocol With proposed solution behavior). If Nb_transmission is Packets Loss equal or less than 3, then node “A” re-sets waiting_delay, increments Nb_transmission and In order to formally prove and verify the correct retransmits the packet. If Nb_transmission exceeds 3 behavior of our proposed solution, we have chosen a transmissions temptations, the source node halts the suitable mathematical model according to current communication and start finding new path communication protocol specifications. The protocol International Conference on Advanced Aspects of Software Engineering Page 93 ICAASE, December, 01-02, 2018 Time Petri Net model for CL-MAC with Packet Loss Protocol in Wireless Sensor Networks ICAASE'2018 operating mechanism is a time discret events so Time Initially, only the places p1, p8, p14 and p17 are marked Petri nets (TPN) seem more attractable and suitable for by one token each one. both their ability to easily model temporal constraints of communication scenarios, and the existence of TiNA tool [Ber 04]. TiNA is a software tool for TPN and ( ) ( ) (4) automatons properties’ verification like boundedness, liveness, deadlock-freeness, reversibility, etc. [Ber 83]. Figure 3 depicts the TPN model of CL-MAC protocol with packet loss. This model is a revised one (see [Kec 3.2 Model explanation 10]). Intervals values associated to transitions refers to relative time of transmitting packets (RTS, CTS, In this section we give a TPN model for the proposed DATA, ACK) according to IEEE 802.11 standard and solution. The lost packet event may occur when node respected by our proposed solution. sends RTS, CTS, DATA, or ACK packet that didn’t reach its destination (one hop neighbor). After waiting 3.1 Model Hypothesis the replay a sufficient time needed for packet and packet replay propagation, the sender node retransmits CL-MAC with packet loss TPN model works under the the packet again (the lost one). Whatever is the packet, following hypothesis: DIFS duration = SIFS duration = the process is the same. A packet is retransmitted at 1 time unit, control packets RTS, CTS and ACK most four times. After the fourth packet transmission consume 3 time units each one, DATA packet requires fail, then chronologically node will interrupt this 10 time units for its transmission. One unit time is communication, looks for a new path and restarts the added (reserved) for packet processing (a new packet communication on the new path. So, to model this idea, generation, received packet reading) and also for some we first describe TPN model transitions (see table 1). environment’s handicap. M is the initial marking. Table 1: CL-MAC with packet loss model transitions Transition Description t1 RTS packet sending in network by the sender node t2 DATA packet unicasted by the sender t3 Sender switches to sleep mode t4 Sender switches to weak-up mode to start a new communication (frame) t5 Receiver sends a CTS packet as a replay to the RTS one generated by t1 t6 Receiver sends an ACK packet after receiving the DATA packet t7 Receiver node switches to sleep mode after communication completion t8 Neighbor node, not belonging to the routing path, switches to sleep mode Neighbor node, not belonging to the routing path, switches to weak-up mode after communication t9 completion. t10 CTS packet sent by next hope node t11 Receiver sends DATA packet to the next hope node. t12 Next hope node switches to sleep mode t13 DATA packet losing. t14 DATA packet retransmission after ( ( ) ) t16 et t18 Empty retransmission counter after a successful transmission t17 Sender initialization for a new communication after failures (after 4 retransmission fails). International Conference on Advanced Aspects of Software Engineering Page 94 ICAASE, December, 01-02, 2018 Time Petri Net model for CL-MAC with Packet Loss Protocol in Wireless Sensor Networks ICAASE'2018 t19, t20 Receiver initialization after a long waiting time for DATA packet t21 Next hop node initialization after a long waiting time for DATA packet. t21 Sender Network Receiver Network Next-Hope Figure 3: Time Petri Net Model for CL-MAC with Packet Loss. The communication nature in such networks is a After sending a packet, the sender node will wait for a multi-hop scenario. An end-to-end packet replay from his path member neighbor as shown in communication is a replication of the same atomic figure 1 (from the receiver). Whenever the sender communication between two neighbors node. So that didn’t receive a replay to its initial sent packet, the destination node in the ith communication will be retransmit it again and increments the counter the source of the (i+1)th one. For this reason, our retransmission number. This action is modeled by model is restricted to only one hop communication. transition t14. Place p22 models the counter variable, will then get one more token after t14 was getting As illustrated in Figure 3, each node in the network is fired. If four token will be gathered in place p22, modeled as follow: transition t17 will then be fired (arc linking p22 to t17 Sender: Transitions t1, t2, t3, t4, t14, t15, t16, t17 and is 4 weights). This situation means that DATA packet t18.The first transitions t1 stands for RTS packet is retransmitted four times. So the node has to halt this sending process at precise moments modeled by communication and checks for another alternative temporal intervals associated to the transitions (RTS path taken into consideration that the actual packet is sent after a DIFS and DATA packet is sent destination node is broken. Transition t3 depicts node after reception of a CTS within 3 to 4 time units). switching from waiting state to sleep state (p19). Place p3 models node waiting state for CTS packet. Transition t15 is fired when ACK packet is received International Conference on Advanced Aspects of Software Engineering Page 95 ICAASE, December, 01-02, 2018 Time Petri Net model for CL-MAC with Packet Loss Protocol in Wireless Sensor Networks ICAASE'2018 (as a replay to DATA packet reception) and t16 then destination (here t6 is fired) or lost (t13 is fired)). empties the place p22 (resets the retransmission Place p7 stands for ACK packet propagation. counter variable) if there are still tokens in. Transition t4 allows node to switch to weak-up mode after a half 3.3 CL-MAC with packet loss TPN Model Results communication frame. In CL-MAC, a frame is modeled by 44 time’s unit. Figure 4 illustrates the reachability analysis results of the time Petri net using TiNA tool. The results reveal Receiver is represented by four transitions, t5, t6, t7, that the TPN model, of the new version of CL-MAC and t19. Transition t5 represents RTS packet with packet loss protocol, has effectively good reception. Here, the receiver is ready to start a new properties: communication according to the exchanged schedule in neighbor discovery phase (place p8 is marked by i. Boundedness: the number of tokens in every place one token). After receiving RTS packet, the receiver is limited to one token except the place p22 witch node will then generates and transmits a CTS packet can get four token inside (that is 4-bounded).The as a replay to the sender node. Place p9 will be then K-bounded property describes the well operating marked by one token as indication of the waiting state of the CL-MAC protocol with packet loss. In our to DATA packet. Whenever t6 is fired indicates solution, we have proposed that a lost packet will reception of DATA packet from the sender node. be retransmitted again and again at most four ACK packet will be sent by the same transition t6 times (line 22 in the algorithm above reflects this represented by the token injected in place p7. situation). Transition t19 forces the receiver node to switch to ii. Liveness: the net is deadlock freeness and each sleep mode after staying a long time waiting for transition is always able to be fire infinitely. This DATA packet. Also t7 allows the receiver to switch to property tells us that our solution ensures packet sleep mode but is fired when place p12 gets one token delivery even if some communication handicap or representing a communication completion (ACK is obstacles are present in the deployment received from the next hope node). This allows the environment. communication process re-initialization on the side of iii. Reversibility: the return of the TPN to its initial the destination receiver; the second one is the part of the network between the receiver and the next-hope state shows that the CL-MAC TPN model is node. reversible. This last property confirms that the new CL-MAC version didn’t halt whenever is lost Network is modeled by two parts. The first one elsewhere, and the protocol tries to find other describes the neighborhood of both sender and alternative path after a communication fails. receiver. Places p18, p17 and, transitions t8 and t9 represent a neighbor node not belonging to the routing path. Place p17 is marked by one token telling that the node is ready to take part of the communication. When it receives a packet not addressed to it (p17 will get the second token), immediately it turns its transceiver and switches to sleep mode. Transition t8 is fired and p18 gets one token as indicator of node sleep state. Place p2 models the RTS packet propagation in the network while p5 stands for the propagation of the RTS packet replay (CTS) sent from the receiver. As mentioned, a packet may be lost due to the environment nature where the network is deployed. Transition t13 here models all the obstacles causing the loss of the packet. In our TPN model, both transitions t6 and t13 have the same firing time’s intervals drawing the competitively of these two transitions. Only one will be fired (a packet will be either received by the receiver as its intermediate Figure 4 (A) International Conference on Advanced Aspects of Software Engineering Page 96 ICAASE, December, 01-02, 2018 Time Petri Net model for CL-MAC with Packet Loss Protocol in Wireless Sensor Networks ICAASE'2018 [Est 99] D. Estrin, R. Govindan, J. Heidemann, and S. Kumar. Next century challenges: Scalable coordination in sensor networks, in Proceedings of the 5th IEEE/ACM Annual Conference on Mobile Computing and Networks(MobiCOM'99), Seattle, pp. 263-270. August 1999. [Kyu 14] Shi-Kyu Bae. Power Consumption Analysis of Prominent Time Synchronization Protocols for Wireless Sensor Networks. In (JIPS) Journal of Information Processing Systems, vol. 10, no. 2, pp. 300-313, 2014. [Kec 13] B. Kechar and L. Sekhri. CL-MAC: Cross-layer MAC Protocol for Delay Sensitive Wireless Sensor Network Applications. in Petri Nets- Figure 4 (B): Reachability analysis using TiNA Applications, Book chapter, pp. 181-208, May 14, 2013. [Kec 08]B. Kechar and A. Louazani. CL-MAC: An Energy After running several times, TiNA generates 1137 Efficient Cross-Layer MAC Protocol with classes and 21 transitions. This great number of Latency Improvement in Wireless Sensor classes makes impossible to represent the class graph Network, in 17th International Conference on in this paper. Computer Communication and etworks (ICCCN). Virginia Institute, USA, 3-7 Aug. 2008. [Kec 10 ]B. Kechar. L. Sekhri and M.K. Rahmouni. CL- 4. Conclusion And Future Work MAC: Energy Efficient and Low Latency Cross- In this paper, a new version of CL-MAC protocol Layer MAC Protocol for Delay Sensitive Wireless Sensor Network Applications. In The recovering the packet loss problem is presented. The Mediterranean Journal of Computers and proposed solution is based on retransmitting the lost Networks, Vol.6, No.1. pp. 1-14, 2010. packet until it will be received by destination or the [Ber 04] B. Berthomieu, P.O. Ribet and F. Vernadat. The retransmission fails four successive times. We have tool TINA - Construction of abstract state spaces proposed a time Petri net based approach to model the for Petri Nets and Time Petri Nets . In solution depicted by the given algorithm. Formal International Journal of Production Research, analysis using TiNA tool allows proving some Vol.42, No.14, pp. 2741-2756, 2004. properties of the TPN model. The obtained results [Ber 83] B. Berthomieu and M. Menasche. An Enumerative illustrate clearly the well operating of the new Approach for Analyzing Time Petri Nets. In FIP extended version of CL-MAC protocol. Congress Series, Elsevier Science Publishers, Vol. 9, Amsterdam, Netherland, pp. 41-46. 1983, In order to strengthen theoretical results, this work is [Lou 14] A.Louazani, L. Sekhri and B. Kechar. A Security now under² implementation using OMNET++/Castalia Scheme Against Wormhole Attack in MAC Layer simulator to obtain empirical preliminary results in for Delay Sensitive Wireless Sensor Networks. In order to enhance TPN model properties. As future International Journal of Information Technology work, we try to secure this version of CL-MAC with and Computer Science (IJITCS), Vol.6, No.12, packet loss protocol against wormhole attacks. pp.1-10, November 2014. References [Yas 12] M. Yasir. An Outline of Security in Wireless Sensor Networks Threats, Countermeasures and Implementations. Wireless Sensor Networks and Energy Efficiency. Protocols, Routing and Management Book, pp. 507-527, 2012. International Conference on Advanced Aspects of Software Engineering Page 97 ICAASE, December, 01-02, 2018