Ubicc 263 Final 263

TEMPORAL INFORMATION SYSTEMS AND THEIR APPLICATIONS TO MOBILE AD HOC ROUTING V. Mary Anita Rajam, V.Uma Maheswari and Arul Siromoney Department of Computer Science and Engineering, Anna University, Chennai -- 600 025, India Contact email: [email protected]

ABSTRACT A Temporal Information System, that incorporates temporal information into the traditional Information System of Rough Set Theory (RST) and Variable Precision Rough Sets (VPRS), is presented. Mobile Ad hoc Networks (MANETs) dynamically form a network without an existing infrastructure. The Dynamic Source Routing (DSR) protocol of MANETs is modified in this paper to use recent routes. Weighted elementary sets are introduced in temporal information systems and used to route packets in mobile ad hoc networks. Notions from VPRS are also brought into weighted temporal information systems and used in routing. The performance of these proposed routing protocols is studied. Keywords: Rough Set Theory, Mobile ad hoc networks, Temporal Information System, Routing.

1

INTRODUCTION

Rough Set Theory is a mathematical tool that deals with vagueness and uncertainty. Mobile ad hoc networks are a collection of wireless mobile nodes that can dynamically form a network. The state of each link in a mobile ad hoc network changes with time. This paper introduces temporal information systems that are then applied to mobile ad hoc routing. Each mobile node maintains a route cache of known routes. It is shown in this paper that giving more importance to the recent routes in the route cache is useful. This has led to the notion of weighted elementary sets in temporal information systems, where more recent elementary sets are given more importance. 1.1 Rough Set Theory In Rough Set Theory (RST) [21], introduced by Zdzislaw Pawlak, a data set is represented as a table, where each row represents an event or an object or an example or an entity or an element. Each column represents an attribute that can be measured for an element. This table is called an information system. The set of all elements is known as the universe. For example, if the information system describes a hospital, the elements may be patients; the attributes (condition attributes) may be

symptoms and tests; and the decisions (or decision attribute) may be diseases. In an information system, elements that have the same value for each attribute are indiscernible and are called elementary sets. Subsets of the universe with the same value of the decision attribute are called concepts. A positive element is an element of the universe that belongs to the concept. For each concept, the greatest union of elementary sets contained in the concept is called the lower approximation of the concept and the least union of elementary sets containing the concept is called the upper approximation of the concept. The set containing the elements from the upper approximation of the concept that are not members of the lower approximation is called the boundary region. The lower approximation of the concept is also known as the positive region. A set is said to be rough if the boundary region is non-empty. A set is said to be crisp if the boundary region is empty. Variable Precision Rough Sets (VPRS) [31], proposed by Ziarko, is a generalization of the rough set model, aimed at modelling classification problems involving uncertain or imprecise information. Classification with a controlled degree of uncertainty is possible with this model. It is possible to generalize conclusions obtained from a smaller set of observations to a larger population.

Ubiquitous Computing and Communication Journal

1

In RST, the lower approximation of a concept is defined using an inclusion relation. Here in VPRS, the lower approximation is defined using a majority inclusion relation. The β-positive region is the union of elementary sets which are either completely contained in the concept or are almost contained in the concept, with a maximum error of 1 – β. The conditional probability of an element being positive in an elementary set is the probability that the element is positive, given that the element belongs to that elementary set. It is the ratio of the number of positive elements in that elementary set to the number of elements in that elementary set. When this conditional probability is greater than a threshold β (0.5 < β ≤ 1) the elementary set is said to fall in the β-positive region. 1.2 Rough Sets in Temporal Contexts A temporal system is a time based system which shows the temporal variation of some specific data or attribute. Time-series data are a kind of temporal data and are results of some observations usually ordered in time. Time-series data often possess content that is conflicting and redundant. The data may be imprecise; therefore a precise understanding of information cannot be derived from the data. Rough set theory offers a powerful toolset for confronting this situation. Analysis of time-series data and constructing suitable data from the time-series that can be used by rough sets are investigated in [15], [18], [11]. Reducts can be found from the original data and rules can be generated from the acquired reducts using rough sets [15]. For constructing suitable data from the time-series, different methods are tried. In the mobile window method [4], a window is moved along the time-series; the data points falling into the window are transferred into a rough sets object. The window method poses restrictions on how far back in time dependencies can be traced. In the columnizing method [18], the time series are organized in columns, such that each row represents an object where each column is an economic indicator, and each row represents a different point in time. In [11], time-series is represented using a series of events or states. An event is something that occurs, and is associated with a time. The values of attributes are trends, rather than values measured at points in time, so that dependencies can be traced back as long as required. A decision table for time-series called a time series decision table, is proposed in [16]. A time

stamp is introduced as an attribute, in addition to the condition attributes and the decision attribute of the traditional information system. A temporal information system is introduced by Bjorvand [29]. The temporal information system has a sequence attribute in addition to the condition attributes and the decision attribute present in the traditional information system. The value of the sequence attribute is an integer, based on the time of occurrence of the objects in the information system. Methods are proposed in [29] and [28] to convert this temporal information system into the traditional information system, so that rough set techniques can be applied. The method proposed in [29] depends on time intervals that must be fixed and defined in advance. Trend expressions [28] are added to transform the traditional method of translating a temporal information system into an information system. So, a new attribute is added to the information system, for which values are set based on the trend. A real time temporal information system is proposed in [29], in which the difference between the time of occurrence of the current row and the previous row (if rows are sorted according to time) is also stored in the information table. Having a linearly ordered universe, based on time, is also used in bringing in the notion of time into a rough set information system. This temporal information system with a linearly ordered universe [19], [8], [1], [3], [20], [2] provides information about the behaviour of objects in time and state of an object is described by some attributes. The elements can be the behaviour over time of the same object, multiple objects, or objects independent of each other. Temporal templates [19], which are homogeneous patterns occurring in some periods, are extracted from temporal information systems. The temporal templates are then used to discover behaviour of temporal features of objects. Using temporal templates [20], a temporal multiple information system [19] is introduced that describes many objects along the time axis e.g. several users visiting a website. For each object, a sequence of temporal templates is found. Collections of patterns, called episodes, appearing in sequences frequently are found. New attributes are generated from the found frequent episodes. Temporal patterns that can be potentially specific for one musical instrument or a group of instruments are searched [8]. Such patterns are used as new descriptors. A time window based technique is used to measure the values of the descriptors in

Ubiquitous Computing and Communication Journal

2

time. Optimal temporal templates that respond to temporal patterns are then determined. From the temporal templates, episodes (collections of templates that occur together) are found. Information maps can be constructed from data represented by temporal information systems [1]. The temporal information system at the current time t is also viewed as a family of decision systems [1], where the universe of the decision system at time t1, is a subset of the decision system at time t2, for t1 < t2. Some work is based on how the data varied over a particular duration of time (say, two years, two months etc.). Different attributes are assigned for each time period in [30]. A dynamic information system model based on time sequence is proposed in [13]. The attributes in the information system can have different values at different time points. 1.3 Routing in Mobile Ad Hoc Networks Sending data from a source mobile node to a destination mobile node through a route (or sequence of intermediate mobile nodes) is routing. Routing is one of the most difficult issues in mobile ad hoc networks. Each node in an ad hoc network is responsible for routing. Hence each node should maintain the information necessary for routing, that is, the next hop or the path through which the data has to be routed to the destination. This information is either available even before it is needed (proactive) or is got only when necessary (reactive).

1.3 Application of Rough Sets to Computer Networks Very little work has been done in the application of rough set theory to Mobile Ad Hoc Networks and Mobile Ad Hoc Routing. A few papers have applied rough set theory to networks. Rough set theory is used in intrusion detection in computer networks [6], [14] and [32]. Rough set approach is also applied to the flow control of a UDP-based file transfer protocol [33] to accomplish a real time datatransferring rate adjustment task; to network fault diagnosis [24]; and to achieve the rules for object recognition and classification for mobile robots [12]. Rough set logics is combined with artificial neural networks for failure domain exploration of telecommunication network [7]. The basic concepts of rough set theory are illustrated using an example concerning churn modeling in telecommunications [23]. 1.4 Overview of the Paper This paper presents a Temporal Information System that brings temporal information into the traditional Information System of Rough Set Theory and Variable Precision Rough Sets. The DSR protocol is modified to study the use of recent routes. The paper then introduces the notion of weighted elementary sets in temporal information systems and uses this to route packets in mobile ad hoc networks. This paper then uses VPRS in weighted temporal information systems and uses this in routing. The performance of these proposed routing protocols are studied. 2

Proactive routing is usually done using table driven protocols where tables are formed initially, and are updated either periodically or when some change is known. Reactive routing protocols are also known as on-demand routing protocols. In this kind of protocols, a route is found for a destination only when there is a need to send information to the destination. Each node does not have knowledge of the location of all other nodes in the network. All nodes when they learn or use routes, store the routes to the destinations in a routing table or a cache. Most of the on-demand routing protocols [5], [25], [9], discover routes when needed by flooding route request packets in the network. A route reply is sent back to the source node by either an intermediate node that has a route to the destination or by the destination.

TEMPORAL INFORMATION SYSTEMS

2.1 Information Systems and Decision Systems Consider a universe U of elements. An information system I is defined as I = (U, A, V, ρ), where A is a non-empty, finite set of attributes; is the set of attribute values of all attributes, where is the set of possible values of attribute ; is an information function, such that for every element , is the value of attribute for element . The information system can also be viewed as an information table, where each element corresponds to a row, and each attribute corresponds to a column. I = (U, A, V, ρ), is known as a decision system, when an attribute is specified as the

Ubiquitous Computing and Communication Journal

3

decision attribute. A decision system is used for predicting the value of the decision attribute. is known as the set of condition attributes. The concept is the set of elements of that have a particular value (say, ) of the decision attribute . That is, Normally, is a boolean attribute that takes one of two possible values. When is known as a multi-valued decision attribute. These definitions are based on the definition of Rough Set Information System in [21, 22, 17]. 2.2 Regions of the Universe An equivalence relation , called indiscernibility relation, is defined on the universe as

elementary sets whose conditional probability is greater than or equal to where 0.5. The negative region is the union of the elementary sets whose conditional probability is less than where 0.5. These are based on the definitions in [34]. When , we denote it as , and note that . The range of is (0.5,1] in the original VPRS definition. This indicates probabilistically that the elementary set is positive, when the decision attribute is boolean. It appears that when the decision attribute is multi-valued with as the number of possible values, the range of is (1/k,1]. 2.3 Temporal Extensions A Generic Temporal Information System is defined as a set of information tables, with each information table located at a time on the time axis. A time interval can also be considered instead of a time instance. (GTIS)

In the information system , the elementary set containing the element with respect to the indiscernibility relation , is

The lower approximation of the concept , with respect to and equivalence relation on , is the union of the elementary sets of with respect to that are contained in , and is denoted as The upper approximation of is the union of the elementary sets of with respect to that have a non-zero intersection with , and is denoted as The lower approximation of is also known as the Positive region of . The set is called the Boundary region of . The set is called the Negative region of . The conditional probability that an element in an elementary set is positive is

The conditional probability that the element in the elementary set is negative is

When the context is clear, the conditional probability of an elementary set is taken to be . The

A special case is when , that is, the same universe of elements that appears in each information table. A particular element , for each attribute , would have a value at each time . For example, patient $x$ has fever at , and does not have fever at . This special case is when each . In this paper, this is treated as a single Temporal Information System defined as , where is the time attribute with as a set of pairs with as a sequence of time instances,

For each elementary set that is formed from the set of attributes (ie the set of attributes without the time information), there are now elementary sets, where the first elementary set consists of elements that occurred between time instance and , the second elementary set of elements between and , and the last elementary set of elements between and . This can be pictured as vertical blocks of elementary sets along a time axis. 2.4 Information System in a Mobile Node The use of an information system in mobile ad hoc routing was introduced in [26]. The information system was modified in [27] to represent the route better, by using the link information rather than the node information. A threshold was used in the identification of a good next hop.

-positive region is the union of the

Ubiquitous Computing and Communication Journal

4

Let be a set of mobile nodes. A route is a path through mobile nodes in and is denoted as a sequence of mobile nodes Each mobile node maintains a route cache that stores all the routes that knows. Any route in the route cache is a path starting from that mobile node , and so , the first node in the route, is itself. Any route in the route cache is a simple path, where no node repeats, that is, for in the path, . So, . Each mobile node has an information table associated with it. Each row in the information table corresponds to a route in the route cache maintained by that mobile node . Let be the set of all possible links between the nodes. Each condition attribute corresponds to a particular link in the set of all possible links between the nodes. So, is the same for any and is denoted as . Each condition attribute is a boolean attribute, with , and is set to 1 or 0 depending on whether or not that link is present in the route corresponding to that element. So, since for every , and is denoted as since it is the same in each mobile node . A mobile node knows a route either because the route is in a packet that passes through this mobile node, or because this mobile node is in promiscuous mode, and this route is in a packet that passes between two nodes that are within range of this mobile node. When a mobile node knows a route it is added to the route cache only if it is not identical to a path or a sub-path of any other route already present in the route cache. However, every time a mobile node knows a route, a row corresponding to this route is always added to its information table. Consider an element x corresponding to a route . When a row is added to the information table, the values of the condition attributes corresponding to the links are set as 1. 2.5 Decision System in a Mobile Node In traditional Rough Set Theory and VPRS, the value of the decision attribute of a new element (or unknown element or test case) is predicted, based on which elementary set it falls into. The elementary set into which it falls is determined by the values of the attributes of that element. The decision system in a mobile node is used to predict the next hop for a particular destination. This next hop is called the predicted next

hop. The decision attribute is taken as the next hop, and the predicted next hop is also known as the predicted value of the decision attribute. The destination can possibly be reached through several different sequences of intermediary nodes. In other words, several different combinations of attribute values make it possible for the destination to be reached. That is, elements in several different elementary sets correspond to routes that lead to this particular destination. Thus several elementary sets play a role in identifying the best next hop for a particular destination. So, it is not possible to use a single elementary set to predict the value of the decision attribute. The union of these elementary sets is used. In other words, for a particular destination, the union is taken of all the elementary sets that correspond to valid routes from the current mobile node to the destination. A stringent method of predicting the next hop is when all the elements in this union of elementary sets have the same value of the decision attribute, then this value is taken as the predicted next hop. In other words, all known routes to this destination should have this particular node as the next hop. This can also be considered as that value of the decision attribute for which all these elementary sets are in its lower approximation. It is to be remembered that the decision attribute is a multivalued attribute, and so the lower approximation is with respect to a value of the decision attribute. Another method is to have the predicted next hop as that value of the decision attribute where the union of these elementary sets is in the -positive region. The conditional probability is determined using the union of elementary sets, and not a single elementary set. The probability that a particular next hop occurs given that the route leads to a particular destination is taken as the conditional probability. This conditional probability should be greater than a threshold . In other words, a large number of known routes to this destination have this particular node as the next hop. 2.6 Temporal Decision System in a Mobile Node In a Temporal Information System (TIS) for a mobile node, each element (corresponding to a route) has a particular value of the time attribute, that is, each element falls in a particular time interval. This is determined by the time stamp of the next hop of the route that corresponds to this element. The Temporal Decision System (TDS) in a mobile node is used to predict the next hop. An appropriate method (as described in the previous section) is used to determine the predicted

Ubiquitous Computing and Communication Journal

5

next hop in each time interval. The predicted next hop for the TDS is then determined based on the number of time intervals in which it is the predicted next hop. The predicted value of the decision attribute is determined from the TDS based on the probability of a particular value of the decision attribute being the predicted value in the different time intervals. This probability is the number of time intervals in which that value of the decision attribute is the predicted value divided by the total number of time intervals. The predicted value of the decision attribute is the value for which this probability is greater than a threshold . In other words, that particular next hop has been the predicted next hop in most of the time intervals. In Weighted Temporal Information Systems (WTIS) and Weighted Temporal Decision Systems (WTDS), weights are assigned to the elementary sets between time instances and , the elementary sets between and , and the elementary sets between and , respectively. The predicted value of the decision attribute is determined after associating weights with the time intervals. The predicted value of the decision attribute is that value of the decision attribute where the probability is greater than a threshold . The probability is the sum of the weights of time intervals in which that value of the decision attribute is the predicted next hop divided by the sum of the weights of all the time intervals. When the more recent time intervals play a more important role, the weight of a more recent time interval is higher than the weight of a less recent time interval. 3

MOBILE AD HOC RECENT ROUTES

ROUTING USING

This section first describes the original Dynamic Source Routing (DSR) protocol, an ondemand routing protocol. The DSR protocol is then modified so that the most recent applicable route in the route cache is used at each intermediate node. The performance of the modified protocol is evaluated. 3.1 Dynamic Source Routing In Dynamic Source Routing (DSR) [5], each mobile node has a route cache to store the routes that are known to that mobile node. The source node is the node that wants to send a data packet. It uses the shortest route present in its route cache to the destination. If there is no

route in the route cache, it initiates a route discovery, and gets back a route reply with the route to the destination. This source route is placed in the data packet and the data packet is sent to the next hop in the route. When a data packet reaches an intermediate node, the source route in the data packet is used to forward the data packet to the next hop. If a node while sending the data packet to the next hop, finds that the link does not exist, it uses the shortest route present in its route cache to that destination. If the route is not found in the route cache, route discovery is done. When a route discovery is required, the node broadcasts route request packets. If any intermediate node receiving the route request has a route to the required destination in its route cache, it sends a route reply to the initiator of the route discovery. Else, the node appends its own address to the route in the route request and re-broadcasts the route request. If the route request reaches the destination, the destination reverses the route and sends back a route reply to the initiator of the route discovery. When a path is to be added to the cache, the following are done. If a prefix of the path to be added is present in the cache, the rest of this path is appended to the path present in the cache. If the whole of the new path to be added is not present in the cache, the path is added to the cache. If there is no free space in the cache, then a victim is picked up and the route to be added is put in the victim's place. If there is any path or a subpath in the cache entry that is a prefix or the same as that of the path that is added, then the time stamps of those links are set to be equal to the time stamps of the links in the path that is added. When a link error occurs, a route error with information about the dead link is sent to the original sender of the data packet. Paths, or subpaths starting with the given dead link, are removed from the cache in nodes that receive the route error. 3.2

DSRrecent

This section describes the proposed DSRrecent protocol and the modifications made to the existing DSR protocol. In the source node, in DSR, the shortest route in the route cache is used, whereas in DSRrecent, the route to the destination in the route cache, that has the most recent next hop, is used (using algorithm findRecentRoute).

Ubiquitous Computing and Communication Journal

6

If no route is found (to the destination) in the route cache of the intermediate node, or if the found route will result in a loop, the data packet is forwarded according to the existing route in the data packet. If a link error occurs in any node, the best route found in the route cache (using algorithm findRecentRoute) is used. If there is no route in the route cache, route discovery is done.

findRecentRoute() { besttime = 0; bestroute = NULL; foreach possible-route do t = time of next hop in possible-route; if t > besttime then besttime = t; bestroute = possible-route; end end return bestroute; }

3.3

Performance Evaluation

(iv) Average hop count: The average number of hops from the source node to the destination node. The network simulator ns2 [10] is used for the experiments. The following parameters are ones that have been often used in such studies. The random waypoint mobility model is used in a rectangular field. Constant bit rate traffic sources are used. The radio model in the simulator is based on the Lucent Technologies WaveLAN 802.11. providing a 2Mbps transmission rate. A transmission range of 250 m is used. The link layer modeled is the Distributed Coordination Function (DCF) of the IEEE 802.11 wireless LAN standard. The sourcedestination pairs (connections) are spread randomly over the network. 512 byte data packets are used. Nodes move in a field with dimensions 1500 m X 300 m with a maximum speed of 2 m/sec. The pause time is 20 seconds. The number of nodes is kept fixed as 50. The number of communicating source-destination pairs is varied from 5 to 40. Simulations are run for 1000 simulated seconds.

Packet Delivery Ratio (%)

In intermediate nodes, in DSR, the source route is used to determine the next hop. Only if there is a link error, the route cache is used. The shortest route to the destination in the route cache is then placed in the data packet, instead of the original source route. However, in DSRrecent, the best route is determined from the route cache (using algorithm findRecentRoute). The route in the data packet is then modified such that the route from the route cache replaces the subpath (from the current node) in the route in the data packet.

120 100

(iii) Average end-to-end delay: The average delay from when a packet is sent by the source node until it is received by the destination node.

DSRrec

40 20 0 10

20

30

40

Number of Connections

Figure 1: Packet delivery ratio vs. number of connections for DSR and DSRrecent

Normalized control overhead

(ii) Normalized control overhead : The ratio of the number of control packets sent to the number of data packets received in the application layer.

DSR

60

5

The performance of DSRrecent is evaluated using the following metrics, that are normally used in such studies: (i) Packet delivery ratio: The ratio of the data packets delivered to the application layer of the destination to those sent by the application layer of the source node.

80

6 5 4

DSR

3 DSRrec

2 1 0 5

10

20

30

40

Number of connections

Figure 2: Normalized control overhead vs. number of connections for DSR and DSRrecent

Ubiquitous Computing and Communication Journal

7

Average hop count

The packet delivery ratios for DSR and DSRrecent are very similar for 5 and 10 connections. When the number of connections is increased from 20 to 40 there is an improvement in the packet delivery ratio from 3% to 11% (Fig. 1). The normalized control overhead for DSRrecent is more than that for DSR when the number of sources is 5. With increase in the number of connections from 10 to 40, there is an improvement of 4% to 25% over DSR (Fig. 2). In average hop length and average end-to-end delay, DSRrecent is seen to perform worse than DSR as the number of connections is increased (Fig. 3, Fig. 4).

18 16 14 12 10 8 6 4 2 0

The use of the WTIS to predict the value of the decision attribute has already been described in section 2.6. This uses the predicted value of the decision attribute in different time intervals. The experiment described here uses a simple approach to determine the predicted value of the decision attribute in a particular time interval. A predicted value of the decision attribute in a time interval has atleast one element, with that value of the decision attribute, in the union of elementary sets. That is, the union is in the upper approximation for that value of the decision attribute.

4.1 Routing Based on WTIS DSR DSRrec

5

10

20

30

40

Number of connections

Figure 3: Average hop count vs. number of connections for DSR and DSRrecent

Average end-to-end delay

more recent time intervals are assigned higher weights than the less recent time intervals.

10 9 8 7 6 5 4 3 2 1 0

DSR DSRrec

5

10

20

30

40

Number of Connections

Figure 4: Average end-to-end delay vs. number of connections for DSR and DSRrecent

Here, the route cache of the mobile node is used as the WTIS. Routes that are learnt and used are added to the cache of the mobile node. When routes are added, the time stamp of each link is added along with the routes. However, unlike DSR, even if the same route is present in the cache earlier, the new route is added with the new stamp stamps. So, the cache now has the same route multiple times, but with different time stamps. In the source node, initially, as in DSR, a shortest route in the route cache, if available, is placed as the source route in the data packet. If not available, route discovery is done. Then in the source node, and in any intermediate forwarding node, the WTIS is used to determine the best next hop (using algorithm findWeightBasedHop). If the next hop is found, and does not result in a loop, the data packet will be forwarded to this next hop. If this next hop is different from the one in the source route that is already in the data packet, this new next hop is appended to the source route in the data packet at the current node and the route is invalidated by setting a flag in the data packet.

MOBILE AD HOC ROUTING USING WEIGHTED TEMPORAL INFORMATION SYSTEMS (WTIS)

If a next hop cannot be determined from the WTIS, or if the next hop results in a loop, if the source route in the data packet has not been invalidated earlier, the data packet is forwarded according to the source route. Else, a route discovery is done.

In Temporal Information Systems, each elementary set is associated with a particular time interval. In Weighted Temporal Information Systems, elementary sets in different time intervals have weights. Since it is seen in the previous section that the recent route in the route cache is useful,

The total time is divided into time intervals. The list of next hops to the destination that are present in the route cache is found. For each possible next hop, from the current time interval till the initial time interval, a weighted sum of the number of times that the particular next hop is used is found. More

4

Ubiquitous Computing and Communication Journal

8

The ratio of the weighted sum of the usage of the node to the total weight is found. The node for which the ratio is greater than a threshold $\beta'$ is chosen as the next hop.

120 100 80

The proposed protocol used in this section is referred to as TIME_WT. The packet delivery ratios for DSR and TIME_WT are nearly similar for 5 and 10 connections. When the number of connections is increased from 20 to 40 there is a slight improvement in the packet delivery ratio from 5% to 7% (Fig. 5). The normalized control overhead for TIME_WT is more than that for DSR when the number of sources is 5 and 10. With increase in the number of connections from 20 to 40, there is an average improvement of 14% to 22% over DSR (Fig.6).

TIME_WT

40 20 0 10

20

30

40

Number of Connections

Figure 5: Packet delivery ratio vs. number of connections for DSR and TIME_WT

6 5 4

DSR

3 TIME_WT

2 1 0 5

10

20

30

40

Number of connections

Performance Evaluation

The parameters used are the same as those given in section 3.3. The size of the time interval is taken as 40 seconds. The value of $\beta'$ used is 0.5.

DSR

60

5

Figure 6: Normalized control overhead vs. number of connections for DSR and TIME_WT

Average hop count

4.2

Packet Delivery Ratio (%)

findWeightBasedHop(){ Find all possible next hops that will lead to the destination from this node; foreach possible next hop nh timeInterval = currentInterval; weightedSum = 0; weight = maxWeight; totalWeight = 0; while timeInterval >= 0 do if nh is used as a nexthop in timeInterval then weightedSum = weightedSum + weight; end timeInterval = timeInterval -1; //previous timeInterval totalWeight = totalWeight + weight; weight = weight -1; end ratio[nh] = weightedSum / totalWeight; end Find the nexthop nh for which the value of ratio is the maximum and return }

The average hop length and the average end-to-end delay for TIME_WT are more than that for DSR when the number of sources is 5 and 10. But when the number of connections is increased from 20 to 40, it is seen that there is a slight improvement of about 2% in average hop length and of about 5\% in average end-to-end delay over DSR (Fig.7, Fig.8).

Normalized control overhead

weight is assigned if the next hop has been used in the recent past. That is, the weights assigned decrease for earlier time intervals.

16 14 12 10 8 6 4 2 0

DSR TIME_WT

5

10

20

30

40

Number of connections

Figure 7: Average hop count vs. number of connections for DSR and TIME_WT

Ubiquitous Computing and Communication Journal

9

DSR TIME_WT

5.2 5

10

20

30

40

Number of Connections

Figure 8: Average end-to-end delay vs. number of connections for DSR and TIME_WT

5

5.1

The routing protocol is similar to that of the previous section. The next hop is chosen using the notion of threshold $\beta$ ($\beta$--positive regions) as described in algorithm findVPRSWeightBasedHop().

MOBILE AD HOC ROUTING USING BETA-POSITIVE REGIONS IN WTIS

Performance Evaluation

The parameters used are the same as that given in section 3.3. The size of the time interval is taken as 40 seconds. The value of $\beta$, $\beta'$ used are 0.6,0.5 respectively. The proposed protocol used in this section is referred to as VPRS_WT. The packet delivery ratio for VPRS_WT is less than that for DSR for 5 and 10 connections. When the number of connections is increased from 20 to 40 there is a slight improvement in the packet delivery ratio from 2% to 6% (Fig. 9).

Routing Based on Beta-Positive Regions

The experiment described in this section determines the predicted next hop as that value of the decision attribute where the union of these elementary sets is in the $\beta$-positive region, as described in section 2.5. findVPRSWeightBasedHop(){ Find all possible next hops that will lead to the destination from this node; Foreach possible next hop nh do TimeInterval = currentInterval - 1; weightedSum = 0; weight = maxWeight; totalWeight = 0; while timeInterval >= currentInterval – k do nhopCount = the number of routes with next hop nh and willlead to the destination in timeInterval ; totalCount = the number of routes that will lead to the destination in timeInterval ratio1 = nhopCount/totalCount if ratio1 > $\beta$ then weightedSum = weightedSum + weight; end timeInterval = timeInterval -1; //previous timeInterval totalWeight = totalWeight + weight; weight = weight -1; end ratio[nh] = weightedSum / totalWeight; end Find the nexthop nh for which the value of ratio is greater than $\beta'$ }

The normalized control overhead for VPRS_WT is more than that for DSR when the number of sources is 5, 10. With increase in the number of connections from 20 to 40, there is an average improvement of 14% to 19% over DSR (Fig. 10). The average hop length and the average end-to-end delay for VPRS_WT is more than that for DSR when the number of sources is 5, 10. But when the number of connections is increased from 20 to 40, it is seen that there is a slight improvement of about 4% in average hop length over DSR (Fig. 11). The average end-to-end delay for VPRS_WT is similar to that of DSR when the number of sources is 5. But when the number of connections is increased from 10 to 40, it is seen that there is an improvement of about 6% in average hop length over DSR (Fig. 12).

Packet Delivery Ratio(%)

Average end-to-end delay

7 6 5 4 3 2 1 0

120 100 80

DSR

60 VPRS_WT

40 20 0 5

10

20

30

40

Number of Connections

Figure 9: Packet delivery ratio vs. number of connections for DSR and VPRS_WT

Ubiquitous Computing and Communication Journal

10

Normalized control overhead

6 5 4

DSR

3 VPRS_WT

2 1 0 5

10

20

30

40

Number of connections

Average hop count

Figure 10: Normalized control overhead vs. number of connections for DSR and VPRS_WT

16 14 12 10 8 6 4 2 0

DSR VPRS_WT

5

10

20

30

40

Number of connections

Average end-to-end delay

Figure 11: Average hop count vs. number of connections for DSR and VPRS_WT

7 6 5 4 3 2 1 0

DSR VPRS_WT

5

10

20

30

40

Number of Connections

Figure 12: Average end-to-end delay vs. number of connections for DSR and VPRS_WT

6

CONCLUSIONS

This paper presents temporal extensions to Rough Set Theory and Variable Precision Rough Sets. These extensions are applied to Mobile Ad hoc routing. Illustrative experiments are described and the results are presented.

Using recent routes (DSRrecent) was found to improve packet delivery ratio and normalized control overhead. Temporal information was brought into information systems. Recent elementary sets were given more importance in the two proposed methods, TIME_WT and VPRS_WT. The VPRS_WT method uses notions from VPRS. It was seen that the control overhead is much better, while the packet delivery ratio, average hop length and average end-to-end delay are slightly better than that of DSR. It was also seen that the improvement in performance increases with the number of connections. 7

REFERENCES

[1] A. Skowron and P. Synak. Patterns in Information Maps. In Rough Sets and Current Trends in Computing, volume 2475 of Lecture Notes in Artificial Intelligence, pages 453 – 460. Springer, 002. [2] A. Skowron and P. Synak. Reasoning Based on Information Changes in Information Maps. In Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing, volume 2639 of Lecture Notes in Artificial Intelligence, pages 229 – 236. Springer 2003. [3] A. Wieczorkowska, J. Wroblewski, P. Synak and D. Slezak. Application of temporal descriptors to musical sound recognition. Journal of Intelligent Information Systems, 21(1):71 – 93, 2003. [4] J.K. Baltzersen. An attempt to predict stock market data: a rough sets approach. Master’s thesis. 1996. [5] David B.Johnson and David A. Maltz. Dynamic source routing in ad hoc wireless networks. In Imielinski and Korth, editors, Mobile Computing, volume 353. Kluwer Academic Publishers, 1996. [6] Zhongmin Cai, Xiaohong Guan, Ping Shaoa, and Guoji Sun. A rough set theory based method for anomaly intrusion detection in computer network systems. In Expert Systems, volume 20, pages 251 – 259, 2003. [7] Frank Chiang and Robin Braun. Intelligent failure domain prediction in complex telecommunication networks with hybrid rough sets and adaptive neural nets. In 3rd International Information and Telecommunication Technologies Symposium, 2004. [8] Slezak D., Synak P., Wieczorkowska A., and Wroblewski J. Kdd-based approach to musical instrument sound recognition. In Proc. of the 13th International Symposium on Foundations of Intelligent Systems, Vol. 2366, Lecture Notes in Artificial Intelligence, Springer, pages 28 – 36, 2002. [9] Rohit Dube, Cynthia D. Rais, Kuang-Yeh Wang, and Satish K. Tripathi. Signal stability-based adaptive routing (SSA) for ad hoc mobile networks. IEEE Personal Communications, 4(1):36{45, 1997. [10] K. Fall and K. Varadhan. The ns manual

Ubiquitous Computing and Communication Journal

11

(formerly ns notes and documentation), 2002. http://www.isi.edu/nsnam/ns/doc/index.html. [11] Roed G. Knowledge extraction from process data: A rough set approach to data mining on time series. In Mater's thesis, 1999. [12] Wang Haijun and Chen Yimin. Sensor data fusion using rough set for mobile robots system. In Proceedings of the 2nd IEEE/ASME International Conference on Mechatronic and Embedded Systems and Applications, pages 1 – 5, 2006. [13] Xiaowei He, Liming Xu, and Wenzhong Shen. Dynamic information system and its rough set model based on time sequence. In Proc. of 2006 IEEE International Conference on Granular Computing, pages 542 – 545, 2006. [14] Peng Hong, Dongna Zhang, and Tiefeng Wu. An intrusion detection method based on rough set and svm algorithm. In 2004 International Conference on Communications, Circuits and Systems, ICCCAS 2004, pages 1127 – 1130 vol. 2. [15] Herbert J. and Yao J. T. Time-series data analysis with rough sets. In Proc. of 4th International Conference on Computational Intelligence in Economics and Finance, pages 908 – 911, 2005. [16] Li J., Xia G., and Shi X. Association rules mining from time series based on rough set. In Proc. of the Sixth International Conference on Intelligent Systems Design and Applications, pages 509 – 516, 2006. [17] J. Komorowski, Z. Pawlak, L. Polkowski, and A. Skowron. Rough sets: A tutorial. In S. K. Pal and A. Skowron, editors, Rough Fuzzy Hybridization: A New Trend in Decision-Making, pages 3-98. Springer-Verlag, 1999. [18] Shen L. and Loh H. T. Applying rough sets to market timing decisions. Decision Support Systems, Special Issue: Data Mining for Financial Decision Making, 37(4):583 – 597, 2004. [19] Synak P. Temporal templates and analysis of time related data. In Rough Sets and Current Trends in Computing, volume 2005 of Lecture Notes in Computer Science, pages 420 – 427. Springer, 2000. [20] Synak P. Temporal feature extraction from temporal information systems. In Ning Zhong, Zbigniew W. Ras, Shusaku Tsumoto, Einoshin Suzuki, editors, Foundations of Intelligent Systems, 14th International Symposium, ISMIS 2003, Vol. 2871, Lecture Notes in Computer Science, Springer, pages 270 – 278, 2003. [21] Z. Pawlak. Rough sets. International Journal of Computer and Information Sciences, 11(5):341– 356, 1982. [22] Z. Pawlak. Rough Sets — Theoretical Aspects of Reasoning about Data. Kluwer Academic Publishers, Dordrecht, The Netherlands, 1991. [23] Zdzislaw Pawlak. Rough set theory and its applications. In Journal of Telecommunications and Information Technology, 2002. [24] Yuqing Peng, Gengqian Liu, Tao Lin, and

Hengshan Geng. Application of rough set theory in network fault diagnosis. In Proceedings of the Third International Conference on Information Technology and Applications (ICITA 05), pages 556 – 559 vol. 2. [25] C. Perkins and E. Royer. Ad-hoc on demand distance-vector routing for mobile computers. In Proceedings of the Second international workshop on Mobile Computing Systems and applications, pages 90 - 100, 1999. [26] V. Mary Anita Rajam, V. Uma Maheswari, and Arul Siromoney. Mobile ad hoc routing using rough set theory. In 2006 International Conference on Hybrid Information Technology -Vol2 (ICHIT'06), pages 80 - 83, November 2006. [27] V. Mary Anita Rajam, V. Uma Maheswari, and Arul Siromoney. Extensions in mobile ad hoc routing using variable precision rough sets. In IEEE International Conference on Granular Computing, pages 237 – 240, November 2007. [28] Lin S., Chen S., and Ning Z. Several techniques usable in translating a TIS into IS. 30(5), 2003. [29] Bjorvand A. T. Mining time series using rough sets -a case study. In Komorowski H. J. and Zytkow J. M., editors, Principles of Data Mining and Knowledge Discovery, Vol. 1263, Lecture Notes in Computer Science, Springer, pages 351 - 358, 1997. [30] Kowalczyk W. and Slisser F. Analyzing customer retention with rough data models. In Komorowski H. J. and Zytkow J. M., editors, Principles of Data Mining and Knowledge Discovery, Vol. 1263, Lecture Notes in Computer Science, Springer, pages 4 – 13, 1997. [31] W.Ziarko. Variable precision rough set model. Journal of Computer and Systems Sciences, 46(1):39 – 59, 1993. [32] Wang Xuren, He Famei, and Xu Rongsheng. Modeling intrusion detection system by discovering association rule in rough set theory framework. In Proceedings of the International Conference on Computational Intelligence for Modelling Control and Automation and International Conference on Intelligent Agents, Web Technologies and Internet Commerce, page 24, 2006. [33] J. Zhang and R. D McLeod. A udp-based file transfer protocol (uftp) with flow control using a rough set approach. 2005. [34] W. Ziarko. Set approximation quality measures in the variable precision rough set model. In Proc. of 2nd Intl. Conference on Hybrid Intelligent Systems, Santiago, Chile, 2002.

Ubiquitous Computing and Communication Journal

12