=Paper=
{{Paper
|id=Vol-2326/paper12
|storemode=property
|title=Time Petri Net Model for CL-MAC with Packet Loss Protocol in Wireless Sensor
Networks
|pdfUrl=https://ceur-ws.org/Vol-2326/paper12.pdf
|volume=Vol-2326
|authors=Ahmed Louazani,Larbi Sekhri
|dblpUrl=https://dblp.org/rec/conf/icaase/LouazaniS18
}}
==Time Petri Net Model for CL-MAC with Packet Loss Protocol in Wireless Sensor
Networks==
https://ceur-ws.org/Vol-2326/paper12.pdf
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