Title of Invention

METHOD AND SYSTEM FOR EFFICIENT ROUTING IN AD HOC NETWORKS

Abstract

The present invention relates to a method for efficient routing in a multiple hop wireless communication network. The invention is characterized in that data packets are routed over transmission paths using the following steps providing link status information by acquiring link status quality between nodes in the network, updating a routing element (101) with said link status information, determining possible routes with essentially similar link quality status for said data packet, and routing said data packet via the determined routes.

Full Text

Field of invention The present invention relates to a routing system, method and apparatus, in particular for an ad hoc based network in a mobile or static environment using route diversity together with a predictive routing model. Background of invention Wireless communication between mobile users is becoming more and more popular as devices and technology is developed. The infrastructure roll out is expanding within both telecom systems and data network systems. Today also the telecom systems are increasingly using packet switched networks and the trend is clear towards this scheme of packet based routing. This system has been used for many years in the data network based systems and thus many standardized routing protocols exist for this purpose. However they are not prepared for rapidly changing network topographies like for instance so called ad hoc networks. Wireless ad hoc networks are characterized in that the network do not have the same static nature as an ordinary wired network infrastructure but the ad hoc based network do not have a centralized control and is often created in a spontaneous manner. It maintains control through a decentralized concept. Nodes will be installed or disconnected in an uncontrolled manner as compared to standard fixed network architectures; the nodes may come and go quickly which leads to a dynamically changing network topology. In some cases such ad-hoc networks are formed by user/client devices themselves as infrastructure components. These components are then truly mobile in the sense that the users move around, in and out of a network cell, and therefore the infrastructure will move around accordingly. This is an exciting way of building an infrastructure but it sets very high demands on the routing protocol. Other problems in a wireless infrastructure environment are due to radio specific questions that will degrade the performance and efficiency of the network flow. There may be fading problems due to the movement of infrastructure nodes or movement of objects in the radio environment, and there may be problems due to interference from other radio sources within range. These kinds of network topographies have been used in the military environment but are now migrating into the civilian area as well. Wireless systems are now used to rapidly build infrastructure areas for, e.g. wireless broadband access in residential areas or commercial areas. It may be used for temporary infrastructure build up, for example in an emergency situation, in a disaster area, or on the battlefield for military purposes. It could also be used to build up temporary access coverage areas during events like, for example, concerts, conferences, meetings, or seasonal tourist areas. In these kinds of areas, it is not necessary to have coverage all year around but only during specific periods. Today, several Internet Service Providers (ISP) offers wireless access at public or semi-public areas such as airports, restaurants, coffee shops, and hotels using fixed wireless infrastructure systems. These systems are often referred to as so called hots pots. As the demand from the users to gain access increases considering coverage and bandwidth, one way of expanding the area of wireless coverage or bandwidth is to install more infrastructure components, however doing this with normal fixed wireless components are expensive and thus the idea to build networks using wireless routers has emerged. In this case ad hoc routing protocols may be used to have a simplified installation procedure. There are basically two kinds of network usages when discussing ad hoc networks; the first one is the build up of a local area network without any external gateway providing access to an external network, for example Internet. This scheme may be found in installations concerning disaster areas or military installations on the battlefield. The other and probably more common usage is when one or several gateways provide the network with external connections to, for example, an IP based network (private or public, e.g. Internet). In such a network configuration, data packets may take different routes and/or use different gateways depending on, for example, the data traffic type, congestions, or routing cost. Packet: based routing schemes often build there communication network systems around a layered model, for instance the OSI reference model (Open Systems Interconnection). The communication software or hardware is divided into several smaller sub units, layers, working in a hierarchical manner. Information and communication control parameters are passed up and down locally and between the same layers between the sending and.receiving ends. Each such layer is responsible for different tasks in the communication order. In respect to routing the first three layers according to the OSI reference model are the most important. Layer 1 is responsible for the physical transmission of bits of data; examples of physical means may be, for instance, the wired link in an Ethernet based network or a wireless link in a Wireless Local Area Network (WLAN). Layer 2 is often called the Link layer and is responsible of transmitting chunks of data, error detection, and network resource coordination. Layer 3 is often called the Network layer or sometimes the MAC layer; it is responsible for enabling communication between any pair of nodes in a network. This layer takes, for example, care of routing calculations and congestion control. For this purpose different routing protocols has been developed depending on the type of network. Packet routing protocols in the IP-based networks are generally based on routing algorithms using distance vector or link state information to find and maintain a route for each pair of source and destination nodes in the network. In principle, in the distance vector routing algorithms, each router broadcasts the distance to all hosts to its neighbor routers, and each router receiving the information calculates the shortest route to each of the hosts in the network. In the link-state routing algorithms, each router broadcasts the status information of each of its adjacent network links to its neighbor routers, and each router receiving the information maintains the database of the entire picture of the network from the link status information and calculates the shortest route to each host based on the link costs in the database. These routing algorithms are designed for relatively static networks and thus new routing algorithms must be designed for ad hoc networks whose topology changes frequently. There are basically two categories of existing routing protocols for ad hoc networks. These are "proactive" (table driven) and "reactive" (on-demand) routing protocols. Protocols having combinations of these protocols are also possible. Proactive routing protocols constantly and periodically calculate a route to all hosts in the ad hoc network, and thus a route is always available when a packet needs to be sent to a particular destination host. The results are kept in routing tables in all infrastructure elements. In order to maintain routes to each host, control messages are exchanged among the routers to notify changes of the network configuration and link status. Distance vector and link state routing protocols are both categorized as proactive protocols. It should be noted that control messages lead to overhead and may result in reduced network efficiency. Also, the proactive protocols may have difficulty in maintaining valid routes when the network topology changes frequently. DSDV (Destination-Sequenced Distance Vector Routing) is a proactive routing protocol based on the distance vector algorithm, adapting the Routing Information Protocol (RIP) to ad hoc networks. Each node maintains a routing table m which the node stores the next hop node and hop count to each of all the reachable destination hosts. In DSDV, each node broadcasts or multicasts routing updates periodically, or when it detects changes of the network topology. Incremental updates, which update only information about changes since the last update, are also used in order to reduce control traffic. A reactive protocol only performs control message exchange to find/update a route when there is a data packet to be sent. When a source node wants to send data packets, it initiates the control protocol to find a route by sending a route request message to its neighbor nodes. By this principle, the reactive approach is good in that network resources are not wasted when there are no packets to be transported. However, it takes longer time to send packets when a route has to be formed for the first time. AODV and DSR are representative reactive protocols. AODV (Ad hoc On-Demand Distance Vector Routing) protocol uses the DSDV algorithm and creates/updates routes on an on-demand basis, that is, only when a source node wants to send a data packet. This leads to reduction of the number of required broadcasts for finding/updating a route. In AODV, each node maintains a list of detected neighbor nodes. The neighbor list is updated in one of the following three ways: a) when a packet is received from the neighbor node, b) by receiving local advertisement, that is, hello message, from the neighbor node, or c) through feedback from the link layer. Hello messages are broadcasted periodically from each node to its neighboring nodes to inform them about its presence. In AODV, each node maintains a routing table for ail the destinations, each of which the node is either communicating with or forwarding data packets to on behalf of other nodes. For each destination, there is an entry in the routing table that contains information about the destination, such as the IP address, the sequence number for the destination node, hop count to the destination, the next hop node to the destination, and lifetime for the route. When a node wants to communicate with a destination node, that is, to send data packets to the destination, then the source node initiates a route discovery mechanism, where the source node broadcast a route request (RREQ) to all detected neighbor nodes. When the neighbor node receives the RREQ message and has the entry for a fresh enough route to that destination in its routing table, then it sends back a route reply (RREP) message to the source node. If the neighbor node does not find a route entry for that destination, then it forwards the RREQ message to its own detected neighbor nodes. When the destination node receives the RREQ, it returns the RREP message to the source node. In the process of forwarding the RREQ packet, each intermediate node record the IP address of the neighbor node from which the first copy of the broadcast RREQ is received, by which a reverse route is established. The copies of the same RREQ messages received later are all discarded. The intermediate nodes add an entry to their routing table for the destination, where the neighbor node from which the RREP was received is recorded as the next hop node for that destination. The destination sequence number and lifetime of the route are copied from the RREP and recorded in the entry. When the RREP message is returned to the source node finally, a forward route from the source to destination is formed. When a node detects that a route becomes unavailable by failure of the incident link on the route, it sends a route error (RERR) message to all the neighbor nodes, which use the route. The RERR message is sent on to their neighbor nodes and so on until it reaches the source node. The source node can then decide to either stop sending data packets or initiate a new route discovery. DSR (Dynamic Source Routing) protocol uses a source routing mechanism in which the source node determines the complete sequence of nodes along the route on an on-dernand basis and sets the list of the intermediate nodes in the packet header to indicate the sequence of nodes for the route. In this way, each packet has to carry the overhead for packet routing. However, the intermediate nodes do not need to maintain any information about the route and they can learn routes when delivering data packets. In DSR, each node stores (caches) the routes it has learned. When a source node wants to send data packets to a destination node and has no entry in the cache for that destination, then it initiates a route discovery mechanism by broadcasting a RREQ message on its link-layer. Each node receiving the RREQ message appends their IP addresses to the RREQ message and then forwards it further. This process is done until the route to the destination is found or another node can provide a route to the destination node. Then a route reply (RREP) message containing the sequence of network hops to the destination node is returned to the source node. In DSR, when a link failure is detected at a node (i.e. when the package has been retransmitted a maximum number of times), that node removes the link from its routes cache and sends a route error (RERR) message to each of the nodes that have used that link since an acknowledgement was last received. Those nodes have to remove the routes including that link. The retransmission of the data packet from the source node is then handled by upper layers such as the Transmission Control Protocol (TCP). In ad hoc routing protocols that uses link expiration time and traffic load of nodes, the link expiration time is defined as the time interval during which the distance of certain two nodes is kept shorter than or equal to the radio effective distance. In this routing protocol, the metric is used as a cost of each link, and the node tries to find a minimum cost route, expecting that the lifetime of such a route is longer and thus it would reduce the route update frequency and overhead due to control traffic and increase overall throughput of data packet transfer. In this protocol, traffic load of a node is represented by a busy rate of the node during a given time period. A route that has the least traffic load of the nodes is chosen in a route selection algorithm. It is expected that the algorithm would lead to a better load balancing in the network, that is, it would avoid concentrating traffic to particular nodes in the network. When conventional ad hoc network routing methods are used in mobile radio communication networks, some problems may arise. One problem is that since the users are mobile they will move around and the system will experience changes in the radio quality due to e.g. fading, propagation-loss, and shadowing. This is true also if the infrastructure system consist of mobile elements, e.g. if the client equipment are part of the infrastructure. Even in a system with fixed wireless infrastructure components such problems may occur, for instance due to vehicles or other objects temporarily blocking the signal path between two infrastructure components, which leads to changes of the radio link quality. The main concerns for these types of problems arise when they change faster than the update frequency of the routing table or routing path changes. If one tries to solve the above mentioned problems by increasing the update frequency of routing information it will at some point start to degrade the transmission efficiency, due to that the updating of routing information will take up a substantial part of the possible data transmission volume in the medium. In US patent application 2003/0120809 a system is described that detects interference sources in a network by listening for unauthorized signals in the frequency band of usage, in this case the 2.4 GHz ISM band. In this document there is a main focus on problems arising on a network layer and less on the radio layer. The document only discloses an adaptation to the current status and no relevance is taken on the possibly coming nature of link status. The system tries to adapt the packet route accordingly to reduce the effects of the interference. The solution is focusing on detecting only interference and the problem is solved by adjusting the antenna position and direction of nodes close to the interferer so as to reduce the radio coverage towards the interference source. In US patent no. 5,537,394 a status prediction function is introduced for a fixed network solution. The solution involves large statistical calculations of information from a status monitoring function. The statistical calculations are done for the interpretation of the implications of the entire network system and cannot readily be adjusted for an ad hoc network, and in particular not for a wireless ad hoc network. Summary of invention It is an object of the present invention to provide an ad hoc routing method that reduces some of the above mentioned problems, by introducing a route-diversity method in collaboration with a predictive routing control. By periodically taking measurements of the radio channel property, link quality, or other link important parameters it is possible to analyze the network/link status. This information is passed on to a routing processing element that uses this information to decide on the type of signal quality and monitors in time the changes of the link status. The processing element may extrapolate the measured trends and predict the changes of signal quality, and thus respond in an appropriate manner accordingly to efficiently use the available network resources. Knowing the link status between nodes in available routes, a dual or multiple transmission function may be introduced where a data packet is sent via at least two different routes and combined at the destination. There is a higher probability that one of the data packets are transferred intact than if the packet was sent only via one route. By using the status acquiring method and the predictive model it is possible to even better take advantage of the route diversity scheme. This is done by selecting at least two different routes with good link status selected from the measurements of link status. Another possibility using the route diversity method is to send a data packet two different routes with systematic bits and parity bits introduced in the original and copied data packet, respectively. It is then possible to combine the two packets at the destination and handle errors using parity bit control. Also in this example the method may be even improved using acquired link status information and link status predictions. Channel property information obtained from layer 1 as of the OSI network reference model is transported, together with link quality information obtained from layer 2, to layer 3 wherein routing control and traffic scheduling is located. The measured and obtained information is stored and analyzed for trends in the link quality/status between available neighboring nodes and nodes within the network area that is part of the current node's routing scheme. From this the ad-hoc routing protocol decides on appropriate paths for data packets to be sent. Information about the channel properties and link quality can be obtained through measurement of several different parameters. Examples of these kinds of parameters may be Doppler spread of the radio signal due to radio signal fading, a different approach for this is to deduce the coherence time of the radio signal, Variation speed of received signal, or signal to interference noise ratio. The usage of this kind of predictive behavior is independent on the type of ad hoc routing protocol used. In one embodiment, a method for efficient routing in a multiple hop wireless communication network is characterized in that data packets are routed over transmission paths using the following steps: providing link status information by acquiring link status quality between nodes in the network, updating a routing element with the link status information, determining possible routes with essentially similar link quality status for the data packet, and routing the data packet via the determined routes. The method is further comprising the step of combining the data packets at a destination node. The method moreover comprising the step of replacing one of the data packets with parity bits for error detection and error correction purposes. The method is further characterized in that the wireless link comprise the step of using a transmission system based on electromagnetic radiation with a frequency in the range of 100 kHz to 100 PHz. The method is even further characterized in that the transmission system comprise the step of using a transmission system from one or several of the following radio standards: IEEE 802.11, IEEE 802.15, IEEE 802.16 HiperLAN, HomeRF, Bluetooth, IR, UWB, JTRS, 3G, GPRS, and EDGE. In another embodiment, a system for efficient routing in a communication network having a plurality of nodes, each node comprising link status acquiring (3001) means for acquring information about link status between neighboring nodes, updating means for updating routing means with the link status information, determination means using the link status information for determining possible routes for routing of a data packet, and routing means for routing the data packet via the determined routes. A system is further characterized with that communication between the nodes is wireless. The communication network is further characterized as an ad hoc network. The system further comprises the step of replacing one of the data packets with parity bits for error detection and error correction purposes. The system is characterized in that the wireless communication comprises a transmission system based on electromagnetic radiation with a frequency in the range of 100 kHz to 100 PHz. The system is even further characterized in that the transmission system is one or several of the following radio standards: IEEE 802.11, IEEE 802.15, IEEE 802.16 HiperLAN, HomeRF, Bluetooth, IR, UWB, JTRS, 3G, GPRS, and EDGE. In yet another embodiement of the present invention, a node in a communication network having a plurality of nodes, the node comprising processing means for processing network control information, storing means for storing network control information, transmission means for transmitting data packets, link status acquiring means for acquiring link information comprising link status and link quality between neighboring nodes, determination means using acquired link information for determining at least two routes to a destination for routing of a data packet, and routing means for routing the data packets via the determined routes. The node is further characterized in that the communication between nodes is wireless and the communication network is an ad hoc network. The node is further characterized in that one of the data packets is replaced with parity bits for error detection and error correction purposes. In another aspect of the present invention, the node is characterized in that the wireless communication comprises a transmission system based on electromagnetic radiation with a frequency in the range of 100 kHz to 100 PHz. The node is further characterized in that the transmission system is one or several of the following radio standards: IEEE 802.11, IEEE 802.15, IEEE 802.16 HiperLAN, HomeRF, Bluetooth, IR, UWB, JTRS, 3G, GPRS, and EDGE. In another embodiment of the present invention, a wireless communication network comprising a system according above description, comprising one or several nodes according to above description is defined. A computer program in a node according to above described node, comprising a first instruction set for acquiring link status information between nodes in the network, a second instruction set for updating a routing element (101) with the link status information, a third instruction set for determining possible routes with essentially similar link quality status, and a fourth instruction set for routing a data packet via the determined routes. This and other objects, features, functions, and benefits of the present invention will become apparent with reference to the detailed description, which follows. Brief description of drawings Fig. 1 is a schematic block diagram of some of the components and their respective role in an inter-layered concept of a preferred embodiment of the invention. Fig. 2 is a diagram of signal strength and a variation speed parameter versus time with a threshold level governing the slow or fast category determination. Fig. 3 is a schematic illustration on how channel status information and link quality information are passed back in the system for a reactive routing protocol. Fig. 4 is a schematic illustration on how channel status predictions are passed back in the system for a reactive protocol. Fig. 5 is a schematic depiction of a small ad hoc network and the possible routes between two nodes in this network. Fig. 6 is a schematic illustration of a wireless ad hoc network topology. Fig. 7 is a schematic block diagram illustrating part of the routing and route determination process for a reactive routing ad hoc protocol (Fig. 7A) and a proactive ad hoc routing protocol (Fig. 7B). Fig. 8 is a schematic block diagram illustrating a node in the network. Detailed description of invention In Fig. 6, the basic concept of a mobile multiple hop wireless ad hoc network of the present invention is shown. A plurality of nodes or infrastructure elements 601, 602, 603, 604 ... 60n builds up an ad hoc network 610 together by communicating with each other and forwarding data traffic and control traffic for each other, in order to maintain the network traffic between the communicating end nodes and intermediate nodes. Sometimes one or several gateways 601 are present in an ad hoc network 610. This gateway 601 acts as a link between for example a wireless ad hoc network 610 and a standard fixed IP network 620 (e.g. Internet). The connection 600 to the standard IP network may be either a fixed line, using for example an Ethernet network, or a fixed wireless connection using for example LMDS or "Minilink" systems or similar technology. Not shown explicitly in Fig. 6 are client/end user terminals that may communicate via these infrastructure nodes 601, 602, 603, 604 ... 60n; however, the infrastructure may actually be built up by using client/end user terminals themselves. It may also be built by dedicated routers or a network may be built on a combination of these two elements. Today client/end user terminals have the computing power to handle networking applications, even in an ad hoc environment. Client terminals may include equipment such as desktop computers, workstations, laptops, PDA's (Personal Digital Assistant), mobile phones, or other data processing equipment with communication or networking means. An infrastructure element or node 601, 602, 603, 604 ... 60n, 800 comprise of at least processing means (801), storing means (802), communication means 805 and routing means 101, 803. The communication means 805 may be wireless 806 or using a wired connection 806, however in a preferred embodiment the communication means 805 is wireless. The routing means 101, 803 is implemented in a routing algorithm, often using a software program, and normally both the routing means 101, 803 and/or communication means 805 are often embedded in the infrastructure element 800, but they may also be located in an external device connected to an infrastructure element 601, 602, 603, 604 ... 60n, 800 through a connector 804. An example of this arrangement may be a PDA that has an external device connected to the PDA; this external device handles the routing and/or communication means for enabling the PDA to be part of an ad hoc network 610 or a wireless network in general. In Fig. 1 the key components in the routing element 800 and their respective roles are shown together with the data and control traffic flow patterns within a layered network reference model, e.g. the OSI model. The first layer 104 (LI) is responsible for the physical transmission of data bits and in this layer there may be functionality to measure and obtain the status and quality of the properties of the physical medium, for example the wireless radio channel status. This information is passed on to the third layer 106 (L3) to a link status monitor 102. There are several different parameters that may be measured in order to obtain the status of radio links between the infrastructure nodes. One such parameter is the Doppler spread. The Doppler spread and coherence time (sometimes referred to as average fading duration) are both parameters that describe the time varying nature of the radio channel. If there is a relative movement between a mobile station and infrastructure node then there will be fading problems associated thereof. The same applies if there is an object moving in the radio path between two infrastructure nodes or an infrastructure node and a mobile station. When each node periodically sends and receives beacon signals, for example, "hello messages", or in any other way monitors the radio signals from neighboring nodes, it is possible to measure the so called Doppler shift fD which may give an indication of the radio channel quality, Doppler shift is a measure on the Doppler spread width. This measurement is compared to an upper limit for the Doppler shift fDUL which sets the limit to where the ad hoc routing algorithm still will be able to adapt without degrading the transmission efficiency. If the signal bandwidth is much greater than the Doppler spread the effects are negligible and this situation is defined as slow fading and thus not a problem for the ad hoc routing algorithm to adapt to by increasing the update frequency. However if the Doppler spread is higher than the determined threshold level, the fading is in a so called fast region, then the routing algorithm need to increase the frequency of route updating and this will at some point start to degrade traffic flow efficiency since the control traffic will have an increasingly larger portion of the available transmission capabilities. Average fading duration

Documents:

4082-delnp-2006---Claims-(04-03-2015).pdf

4082-delnp-2006--Correspondence Others-(04-03-2015).pdf

4082-delnp-2006--Form-5-(04-03-2015).pdf

4082-delnp-2006--GPA-(04-03-2015).pdf

4082-delnp-2006--Marked Claims-(04-03-2015).pdf

4082-delnp-2006-abstract.pdf

4082-delnp-2006-Claims-(25-07-2013).pdf

4082-delnp-2006-claims.pdf

4082-delnp-2006-Correspondence Others-(04-02-2013).pdf

4082-delnp-2006-Correspondence Others-(04-03-2015).pdf

4082-delnp-2006-Correspondence Others-(29-11-2013).pdf

4082-delnp-2006-correspondence-others 1.pdf

4082-delnp-2006-Correspondence-Others-(24-05-2013).pdf

4082-delnp-2006-Correspondence-Others-(25-07-2013).pdf

4082-delnp-2006-correspondence-others.pdf

4082-delnp-2006-description (complete).pdf

4082-delnp-2006-drawings.pdf

4082-delnp-2006-form-1.pdf

4082-delnp-2006-form-18.pdf

4082-delnp-2006-form-2.pdf

4082-delnp-2006-form-26.pdf

4082-delnp-2006-Form-3-(24-05-2013).pdf

4082-delnp-2006-Form-3-(29-11-2013).pdf

4082-delnp-2006-form-3.pdf

4082-delnp-2006-form-5.pdf

4082-delnp-2006-pct-101.pdf

4082-delnp-2006-pct-210.pdf

4082-delnp-2006-pct-306.pdf

4082-delnp-2006-pct-409.pdf

4082-delnp-2006-Petition-137-(25-07-2013).pdf

abstract.jpg

Petition under rule 137.pdf