Routing in Cognitive Networks

This work was funded by the National Basic Research Program of China (“973” Program, No.  2009CB320404).

1 Origin of Cognitive Networks
It was Mitola[1] who first proposed the concept of Cognitive Radio (CR) and the architecture of the cognitive loop. A CR system senses the spectrum environment and automatically reconfigures its radio transceiver to use spectrum holes for communication. The CR system has the capability of learning and reasoning, and adjusts itself intelligently to achieve efficient spectrum resource use.

    The Cognitive Packet Network (CPN) was proposed by Gelenbe[2]. In a CPN, intelligent packets which carry executable codes are responsible for collecting network information. When an intelligent packet arrives at a node in the network, it exchanges context information with the node, and updates the route table of the node. In this way, the route is optimized.
With the Cognitive Network (CN) concept, Ramming[3] applies the concept of cognitive loop to the network level. The definition of a CN according to Thomas[4] is a network composed of elements that, through learning and reasoning, dynamically adapt to varying network conditions in order to optimize end-to-end performance. Thomas analyzed the learning and reasoning mechanism of cognitive networks, and provided a functional description of the architecture and component units. During their discussion of integration architecture of heterogeneous wireless access networks, the IEEE adopted the concept of cognitive networking[5].

2 Routing Algorithm Frame of Cognitive Networks
The future network will be a large-scale heterogeneous network. In such an environment, there are many alternative routes for each pair of ends.  Conditions for efficient use of network resources are thereby achieved. However, designing the routing algorithm in heterogeneous networks is a big challenge. First, in a heterogeneous network, the performance of links belonging to different networks is quite different.Second, the heterogeneous network environment often varies. Link transmission data rate and reliability change with the environment. In addition, in an overlapped network scenario it is difficult to predict and control spectrum interference of wireless links. Routing strategy is affected by factors such as the ability to access multiple networks, link throughput, user preference, QoS requirements, and location.

    In this complicated network environment, routing algorithm needs to solve the issues of context adaptation, efficient use of link, network, user resources, and end-to-end optimization. Figure 1 shows a cognitive routing scheme of policy-based for heterogeneous networks. The framework includes the following functional entities:

    (1) Situation Awareness Entity
    This is responsible for sensing context and mapping a service request to an end-to-end QoS request.

    (2) Route Manager Entity
    This is responsible for construction, update, and restoration. It selects routing policies according to context information and optimization object.

    (3) Route Reconfiguration Entity
    This is responsible for route configuration. If the cross-layer routing protocol has been adopted, the entity instructs the configuration of the network layer, data link layer, and physical layer.

    (4) Reasoning and Learning Entity
    This is responsible for evaluation, amendment, and generation of the policies in order to adapt to context.

3 Key Problems

3.1 Situation Awareness Entity
A cognitive network implements decision-making, reasoning, and learning functions according to context aware information. The coverage, timeliness, consistency, accuracy, and reliability of context information directly affects the performance of the cognitive network. Retrieval and distribution of the context information directly affects the network load.

    In a large-scale network, many factors affect route selection between two ends; for example, link parameters, services carried by the network, and available networks between ends. The nodes of a cognitive network exchange their obtained context information using various methods. In a large-scale heterogeneous network, it is difficult to synchronize context information. Various cognitive nodes may have different understandings of the network status, and as a result, routing algorithm oscillation may occur. Inconsistent node information may mislead the route manager entity to make a suboptimal decision, so as to cause route oscillation.

    Generally speaking, network information is collected in three ways: active retrieval, passive retrieval, and a combination of both. The information collection mode, frequency, and range affect the performance of routing algorithm and network load. Therefore, the collection mode of context information and parameter settings should be adjusted to the network environment. The adjustments of situation awareness entity parameters also constitute a cognitive loop.

3.2 Route Manager Entity
The objective of the routing algorithm is to construct a transmission path satisfying certain QoS for end-to-end nodes in the network. Considering the issue of resource optimization, when the network load is heavy, the cognitive routing algorithm enables services to be distributed evenly in the network. When the network load is light, the cognitive routing algorithm can improve users’ satisfaction by utilizing storage capabilities of the network and users to pre-consume network resources.

    The cognitive routing algorithm is a complicated decision-making issue. First, in a heterogeneous network, the number of available link modes is large. The number of end-to-end paths constructed by multiple-mode links is also large. In order to adapt to varying contexts, and to use network resources efficiently, route evaluation criteria and a multiple path mode should be adopted. Second, nodes in a large-scale heterogeneous network generally determine routes in a distributed way. Decision-making processes are concurrent. Conflict between node policies may occur, leading to inconsistent routing tables within the nodes after the reconfiguration.

    The relationship between NEs is competitive but also cooperative. The scale of the heterogeneous network is large, and the issue of complex decision-making is difficult to model and solve. How to design a cognitive routing algorithm in the complicated network is an academic problem to be solved. For complex decision-making, a solution based on policy library may be adopted. In Figure 1, existing and newly developed routing strategies are kept in a routing policy library. According to the context information and service requirements, the policy selection algorithm is responsible for selecting policy. This algorithm may be considered as mapping from the context to the policy.

    The routing policy library contains regular routing protocols such as IP protocol. However, new routing protocols applicable to the heterogeneous network can be facility added into the library (e.g. the routing algorithm applicable to MIMO link, and the cross-layer routing algorithm supporting link cooperation and network cooperation[6]). Figure 2 illustrates the link cooperation scheme of Ad hoc networks. Between any two nodes of an Ad hoc network, multi-hop links compose the end-to-end multi-channel "cooperative path". In Figure 2(a), adjacent links on the same path are configured with different channels. When the node is working in a half-duplex mode, links A-B, C-D, and E-F, or links B-C, D-E, and F-G can transmit concurrently. As a result, the capacity of the path is increased and “cooperative path” gain is achieved. When channel configuration of the path conflicts with the neighboring path, a cooperative path shown in Figure 2 (b) can be constructed.

3.3 Self Learning and Reasoning Entity
The reasoning and learning mechanism distinguishes the cognitive process from the adaptive process. In the cognitive routing algorithm, the reasoning and learning entity evaluates the execution results of routing policy and then amends the policy selection algorithm and routing policy itself.

    In the large-scale heterogeneous network environment, the scope of service QoS varies greatly.  Network links can be quite different from each other. Different networks have different management modes, QoS capabilities, and power consumption. In addition, user preferances are different. In such a network environment, it is impossible for one routing policy to meet the requirements of various networks and users. The routing policy library should be constructed to adapt to service and network context.

    In a complicated network environment, routing policy selection from the policy library, and configuration and reconfiguration of routing policy parameters, are two problems affecting the implementation of policy-based routing algorithms. A routing policy library contains multiple routing policies, including single path routing, multi-path routing and cross-layer routing. Selection rules are therefore necessary for selecting a routing policy. Because the large-scale heterogeneous network environment is so complex, a learning mechanism should be adopted to construct and update the selection rules. Reasoning and learning belong to machine learning, and the reasoning and learning entity uses context information and policy selection results as inputs.

    Benedetto[7] has proposed a cognitive solution to routing policy update in Ultra Wideband (UWB) networks, providing a route update mechanism based on reinforcement learning. Thomas has designed a cross-layer routing update solution based on game theory. But whether the decision-making tree and Bayesian reasoning (and their associated learning algorithms) are applicable to cognitive networks needs further study. For the design of the reasoning and learning mechanism, the following theoretical and technical problems[8] need to be solved:

• The convergence rate of the reasoning and learning algorithm should be faster than the change in context.
• Coordination in the distributed reasoning and learning algorithm.
• Design of routing performance evaluation functions.

4 Conclusions
With expansion of the network scale, network configuration cannot be optimized manually. The coexistence of heterogeneous networks also brings about a more complicated networks environment. Cognitive technology provides a way of configuring networks dynamically, and of optimizing the usage of link, network, and user resources. In this paper, a cognitive routing scheme for heterogeneous networks has been proposed. This scheme involves a routing algorithm frame composed of a situation awareness entity, route manager entity, route reconfiguration entity, and reasoning and learning entity.

References
[1] MITOLA J, MAGUIRE G Q. Cognitive Radio: Making Software Radios More Personal [J]. IEEE Personal Communications, 1999, 6(4): 13-18.
[2] GELENBE E, XU Z, SEREF E. Cognitive Packet Networks [C]// Proceedings of the 11th IEEE International Conference on Tools with Artificial Intelligence (ICTAI’99), Nov 8-10, 1999, Chicago, IL, USA. Los Alamitos, CA, USA: IEEE Computer Society, 1999: 47-54.
[3] CLARK D D, PARTRIGE C, RAMMING J C, et al. A Knowledge Plane for the Internet [C]// Proceedings of Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM’03), Aug 25-29, 2003, Karlsruhe, Germany. New York, NY, USA: ACM, 2003: 25-29.
[4] THOMAS R W. Cognitive Networks [D]. Blacksburg, VA, USA: Virginia Polytechnic and State University, 2007.
[5] IEEE Std 1900.1-2008. IEEE Standard for Architectural Building Blocks Enabling Network-Device Distributed Decision Making for Optimized Radio Resource Usage in Heterogeneous Wireless Access Networks [S]. 2009.
[6] SHI Y, HOU Y T. A Distributed Optimization Algorithm for Multi-hop Cognitive Radio Networks [C]// Proceedings of 27th IEEE Conference on Computer Communications (INFOCOM’08), Apr 13-18, 2008, Phoenix, AZ, USA. Piscataway, NJ, USA: IEEE, 2008: 1292-1300.
[7] DI BENEDETTO M G, De NARDIS L. Cognitive Routing Models in UWB Networks [C]// Proceedings of the 3rd International Conference on Cognitive Radio Oriented Wireless Networks and Communications (CrownCom’08), May 15-17, 2008, Singapore. Piscataway, NJ, USA: IEEE, 2008: 1-6.
[8] JEE Minsoo, YE Xiaohui, MARCONETT D, et al.. Autonomous Network Management Using Cooperative Learning for Network-wide Load Balancing in Heterogeneous Networks [C]// Proceedings of IEEE Global Telecommunications Conference (GLOBECOM’07), Nov 30-Dec 4, 2008, New Orleans, LA, USA. Piscataway, NJ, USA: IEEE, 2008: 2547-2551.

[Abstract] Cognitive networks are capable of learning and reasoning. They can dynamically adapt to varying network conditions in order to optimize end-to-end performance and utilize network resources efficiently. This paper proposes a cognitive network routing scheme that includes a context information collection entity, a route manager entity, a route reconfiguration entity, and reasoning and learning entity.