Advanced Wireless Networks - 4G Technologies

708 NETWORK MANAGEMENT

Figure 18.3 Network model for agent brokering environment.

The SP is informed periodically about the cost changes associated with each of those interconnection points. As a means of competition, all three networks offer the same access to the remote CP. The SP serving a particular client is responsible for identifying the best/optimal connection path (routing) per request of the customer.

In Chapter 7, QoS routing with multiconstraint has been shown to be an NP-hard problem [34]. For this reason, in this section we additionally consider a genetic algorithm (GA), which presents a good method to handle multiconstraint optimization problems and does not depend on the properties of the problem itself [37, 38]. The remaining issue is how the underlying agent architecture may interact with the genetic algorithm itself. It is assumed that an SP may host a particular kind of agent [named broker agent (BrkA)] which is in charge of identifying the optimal path to manage a specific connection request. The interaction between a BrkA and the algorithm may occur according to the following strategies:

(1)The BrkA is able to execute the algorithm in run-time upon the request from the PC client.

(2)The BrkA sends a request to a network node where the genetic algorithm can be executed. The optimal path is then sent back to the BrkA, which activates the setup procedure.

(3)A set of optimal paths for different pairs of PC client and CPs is stored in a database (eventually distributed), which is accessed from the BrkA to retrieve the more convenient path to satisfy the specific request. Once the connection is established, the genetic algorithm can be re-executed in order to identify a more convenient path, if the case.

If network performance and reliability change for some reason, monitoring agents distributed in the system will promptly react to pass the genetic algorithm the new data to recompute the new optimal paths.

18.3.3 Integration of routing algorithm and mobile agents

When network conditions change, SP always wants to find a good route for its customers in real time. That is, with certain QoS constraints, SP wants to find a cost-reasonable route for its costumers. The routing algorithm in SP needs to know:

(1)traffic from SP to CP;

(2)QoS requirements/constraints (i.e. time delay constraint from SP to CP);

(3)connectivity of nodes of NPs,

(4)bandwidth available for each link between nodes;

(5)cost for the traffic to pass through each link; and

(6)time delay for the traffic to pass through each link.

The use of mobile agents provides the complementary underlying structure in order to obtain this information in a distributed and efficient manner. In Section 18.3.1, we provided a brief description of how the agents can be used to deal with the collection of information [31, 33] about the state of the network and the monitoring of health functions that can be defined by the SP. The definition and creation of BAs and DAs serve the purpose of collecting specific variables from a set of nodes (e.g. NABs and INABs) specified by the SP. Then, MAs, during their migration through specific nodes of the network, interact with the other agents for collecting specific information produced by them and, therefore, obtain a general description about the state of the network. Moreover due to the mechanisms of remote evaluation and mobile agents described in the previous sections, the actions to be performed can be developed by the BrkA of a specific SP and sent to other remote devices where they will be executed on behalf of the BrkA, therefore limiting the generated traffic in the network and distributing the computational load and effort. Once the data are collected the routing algorithms can be executed.

A number of these algorithms were discussed in Chapter 6. For this reason in this section we additionally discuss only the GA. In general, GA is a stochastic algorithm searching process in the solution space by emulating biological selection and reproduction. It has been used to solve various optimization problems [38]. In this section, we discuss a genetic-based algorithm in order to address the problem described in the previous sections. In the following, we describe the different features and phases of the algorithm [35].

Encoding is used to map the search space of the specific problem into the space where GA can operate. In the literature, related work in using GA as an optimization tool to solve the famous Traveling Salesman Problem [37] has been reported. There are several encoding approaches mentioned in the literature, such as adjacency representation, ordinal representation and path representation. Some encoding approaches are not suitable for GA operation (crossover and mutation), and some other encoding approaches are inefficient in searching the solution space. In this section, path representation approach is used to naturally encode a route due to its easy implementation. That is, all the nodes that the route passes through are listed in sequence. In order to encode the route in a fixed data structure, ‘zeroes’ are filled into the empty space of the code.

710 NETWORK MANAGEMENT

For instance, in a scenario with 10 nodes in addition to the CP and SP, an array with 10 elements can be used to represent the route. Once the number of nodes that the route passes is less than 10, the corresponding element will be zero. For example [1 2 3 4 0 0 0 0 0 0] is used to represent the SP–1–2–3–4–CP route.

Population initialization is used to start GA computation. In the population initialization process, the number of nodes the route will pass through, which node will be in the route and the sequence of the nodes of the route can be randomly determined. However, there will be some solutions that may violate constraints of delay or interconnectivity. The ‘penalty method’ is used to deal with these constraints, as follows:

(1)for those links that do not exist, a very large delay value is assigned; and

(2)for those routes that violate the delay constraint, a penalty to their cost is added.

In the algorithm, the following expression is used to evaluate the weighted cost of those illegal routes:

C (r) = C(r)[α + D(r)/Dmax]

where C (r)is the weighted cost of route r, C(r) is the function that evaluates the total cost of the links that the route may pass through, D(r) is the function that evaluates the time delay of the route, Dmax is the upper bound of the time delay constraint, and α is the penalty constant (in the algorithm it is set to 2).

The fitness F(r) of the solutions is proportional to their survivability during the algorithm computation. The selection operation, defined below, will use these values to keep ‘good’ solutions and discard the ‘bad’ solutions. For simplicity, we can use the cost of each route as the fitness of each solution. In order to prevent those solutions with very low fitness from being discarded by selection operation of GA at the first several computation loops of GA, the value of fitness of those ‘bad’ solutions is increased. In this way, some ‘bad’ solutions still have chances to survive at the beginning of the evolution of GA and the ‘good’ parts in them will have chances to transfer to new generations. For convenience, we normalize the fitness of solutions to [0,1] by the following expression:

F(r) = [Cmax − C(r)]Cmin

(Cmax − Cmin)C(r)

where Cmax and Cmin and are maximum and minimum cost of routes in each generation of population, respectively.

Selection operation keeps ‘good’ solutions while discard ‘bad’ solutions at the same time. This operation tries to simulate ‘natural selection’ in real life. Those readers with background in communications theory will easily recognize the similarities between GA and the Viterbi algorithm (VA) used to approximate maximum likelihood (ML) demodulators.

Two selection operators are used in the algorithm. The first one is based on the ‘fitness proportional model’. It is also called ‘Monte Carlo selection’. The algorithm is as follows:

(1)add the fitness of all solutions;

(2)randomly generate a number between zero and the sum of fitness; this number is called the pointer of the Monte Carlo wheel; and

(3)add the fitness of each solution one by one until the value is greater than the pointer. Then the last solution is being selected.

Using this algorithm, the higher the fitness value, the bigger the chance of that solution being chosen. The second selection operator used in the algorithm is the ‘best solution reservation’. The best solution in the population will always survive and several duplicated copies will be generated for mutation operation. In this way, the GA will always converge to a certain ‘good’ solution. Moreover, there will be a good chance to find a better solution on the base of the best solution of each generation.

Crossover operation enables any pair of solutions in the population to have a chance to exchange part of their solution information with others. Therefore, those ‘good’ parts from different solutions may be combined together to create a new, better solution. The two original solutions are the ‘parents’ of the new solutions generated. There are many crossover operators designed to solve different problems. In this section, we use traditional one-point crossover method. That is, we find a certain point of the array and swap the part before and after the cross point to generate two new solutions. However, because the number of nodes the route may pass through is not fixed, it is difficult to determine a fixed crossover point. In Papavassiliou et al. [35] the crossover point is determined by (A + B)/4 , where A and B are the numbers of nodes that the two routes will pass through, respectively, and the operator ‘ ’ is a rounding function, e.g. if it is before the crossover operation, there are two routes: [1 2 3 4 5 0 0 0 0 0] and [6 7 8 0 0 0 0 0 0 0]. According to this procedure ( (A + B) /4 = 2), after the crossover we get: [1 2 8 0 0 0 0 0 0 0] and [6 7 3 4 5 0 0 0 0 0]. Note that only part of the population will experience crossover operation; this rate is called the crossover rate.

The mutation operation randomly chooses a solution in the population and then slightly change it to generate a new solution. In this way, there is a chance to find better solution that cannot be found by only crossover operation. In the algorithm, four mutation operators are used:

(1)randomly delete a node from a route;

(2)randomly add a node into a route;

(3)randomly delete two nodes from a route; and

(4)randomly add two nodes into a route.

Only part of population will experience the mutation operation (this is characterized by mutation rate). In order to enhance the local searching ability, those copies of the best solution of each generation are all treated by mutation operator. In this way, the GA may find a better solution that is ‘close’ to the best solution of each generation.

In the repair operation, during crossover and mutation operation, illegal representation of route may be generated because duplicated elements (nodes) may appear in the same route. In the algorithm, those duplicated nodes that would bring high cost to the route are deleted. For example, there may be a route like [1 2 3 4 5 3 7 0 0 0], where node ‘3’ is duplicated. We can evaluate the cost of strings (2 3 4), (5 3 7) and the delay of strings (2 3 4), (5 3 7). If the weighted cost of string (2 3 4) is less than (5 3 7), node 3 in (5 3 7) will be discarded.

The computation efficiency can be improved if after a minimum number of trails (MinTrails), when the algorithm has found a feasible solution and has made no more improvement for a specific period of time, the computation process is stopped. In the algorithm, the ‘improvement’ is presented by the average cost change rate of the best solution

714 NETWORK MANAGEMENT

As seen by the flow chart, in order to control the connection setup time, a timer is used to determine the deadline of the route searching procedure. If the BrkA receives an MA from NAB with satisfactory routing solution before the expiration of the timer, the route searching process stops and this solution is selected. Otherwise, when the timer expires the agent chooses the best route among the route candidates found until that time. Each NAB also creates a BrkAs to deal with the connection when it receives the MAs with the corresponding connection request from the SP. Then, three kinds of agents are used to implement the routing algorithm as follows.

A browser agent will be created and sent to nodes inside the individual private network that the NAB belongs to. These agents will collect resource information such as available bandwidth, delay of the link, price of the link, etc. In a similar way, the BrkA in each NAB will also send out BAs to INABs to see if it can take advantage of network resources from other NPs.

A daemon agent containing the GA code and resource-related information will be created after collecting the necessary resource information, to implement the routing algorithm described in detail in the previous section. Instead of executing the algorithm in each NAB, the BrkA sends DAs to the most suitable nodes inside its private network (e.g. nodes with enough computation resources such as CPU, memory, etc). In this way, we can balance the computation load among nodes in the private networks, if needed.

A messenger agent will be used to bring results back to the BrkA from DAs after the genetic-based route computation. This agent will be forwarded to the BrkA in the SP. Performance results for the algorithm can be found in Papavassiliou et al. [35].

18.4 AD HOC NETWORK MANAGEMENT

We start by identifying some of the properties of ad hoc networks that make them difficult to manage.

18.4.1 Heterogeneous environments

First of all, nodes of an ad hoc network can range in complexity from simple sensors located in the field to fully functional computers such as laptops. An implication of this diversity is that not all nodes will be able to contribute equally to the management task. For instance, it is likely that sensors and small personal digital assistant (PDA)-type devices will contribute minimally to the task of management, while more powerful machines will need to take on responsibilities such as collecting data before forwarding it to the management station, tracking other mobiles in the neighborhood as they move, etc. Thus, the management protocol needs to function in very heterogeneous environments.

18.4.2 Time varying topology

One mission of a network management protocol is to present the topology of the network to the network manager. In wireline networks, this is a very simple task because changes to the topology are very infrequent (e.g. a new node gets added, failure of a node, or addition/deletion of a subnetwork, etc.). In mobile networks, on the other hand, the topology changes very frequently because the nodes move about constantly. Thus, the management

station needs to collect connectivity information from nodes periodically. An implication of this is an increased message overhead in collecting topology information.

18.4.3 Energy constraints

Most nodes in ad hoc networks run on batteries. Thus, we need to ensure that the network management overhead is kept to a minimum so that energy is conserved. Different energy is consumed by a radio when a packet is transmitted or received. In addition, the CPU expends energy in processing these packets. Thus, we need to reduce the number of packets transmitted/received/processed at each node. This requirement is contradictory to the need for topology update messages previously discussed.

18.4.4 Network partitioning

Energy constraints and mobility can result in the network becoming partitioned frequently. For instance, nodes may power themselves off to conserve energy resulting in partitions, or a node may move out of transmission range of other nodes. Similarly, a node may die when its battery runs out of power. In all these cases, the partitioned subnetworks need to continue running independently, and the management protocol must be robust enough to adapt. For instance, when the network gets partitioned, the management protocol entities must quickly learn that the partition has occurred and reconfigure the subnetwork(s) to function autonomously. Furthermore, when partitions merge, the management protocol must be capable of updating the network view without too much of an overhead.

18.4.5 Variation of signal quality

Signal quality can vary quite dramatically in wireless environments. Thus, fading and jamming may result in a link going down periodically. An effect of this is that the network topology from a graph theoretic point of view changes. However, the physical layout of the network may not change at all. The management protocol must be able to distinguish this case from the case when node moves cause topology changes, because in the case of changing link quality/connectivity, it may not be necessary to exchange topology update messages at all. In order to be able to do this, the management protocol entity (which resides at the application layer) must be able to query the physical layer. This obviously violates the layering concept of OSI, but it results in enormous savings.

18.4.6 Eavesdropping

Ad hoc networks are frequently set up in hostile environments (e.g. battlesite networks) and are therefore subject to eavesdropping, destruction and possibly penetration (i.e. a node is captured and used to snoop). Thus, the management protocol needs to incorporate encryption as well as sophisticated authentication procedures.

18.4.7 Ad hoc network management protocol functions

In this section we will discuss some main functions of ad hoc network management protocol (ANMP). Data collection is a necessary function in ANMP where the management entities

716 NETWORK MANAGEMENT

collect node and network information from the network. SNMP specifies a large list of information items that can be collected from each node. However, this list does not include some crucial data items that are specific to the ad hoc environment like the status of the battery power (expected remaining lifetime), link quality, location (longitude and latitude), speed and direction, etc. All this information needs to be collected as (and when) it changes ‘significantly’. For example, the location of a mobile node changes continuously, but there is little point in updating it constantly because the overhead in message complexity is high. The best solution is to update this information when some other aspect of the node changes. For instance, if the node’s connectivity changes as a result of the motion, then we may need to update its location.

One problem that arises in ad hoc networks in relation to data collection is the message overhead. Ad hoc networks have limited bandwidth (whose quality is variable), and we must ensure that the process of management does not consume significant amounts of this resource. Since network management runs at the application layer, the simplest way to implement data collection (at the manager station) is to poll each node individually. This method, unfortunately, results in a very high message overhead. A more efficient method of data collection is to use a spanning tree rooted in the manager station.

Configuration/fault management is needed because nodes in ad hoc networks die, move or power themselves off to save energy. In all of these cases, the network topology changes, and the manager station needs to know the fate of these nodes. In cases when a node is unavailable for the reasons just stated, the manager records that fact in its database. However, even in the case when a manager knows that a node is dead, the entry for that node is not removed from the database because the node may be resurrected (e.g. we put in a new battery) or, keeping in mind that ad hoc networks are temporary, we may need a complete history of the network’s behavior to effect a redesign of protocols, evaluate security breaches, etc.

New nodes may join a network periodically, and these nodes must be incorporated seamlessly into the network. A network may also be partitioned periodically. In this case, we need to ensure that each partition selects its own manager. However, when these partitions merge, one common manager needs to be chosen. Manager selection must be done based on the hardware and software capabilities of nodes and the available battery power. We may also have geographically coexisting but independent networks. An example is a battlefield, where a naval unit may be physically collocated with an infantry unit, each of which is using its own ad hoc network. In this case, the two networks may decide to be managed together or continue being managed independently but exchange information (such as link quality, presence of jamming, etc.) with each other as an aid to better deploy the network resources. It is also possible that a node may belong to two different networks and be managed by two (or more) managers. An example is a disaster relief model, where a police officer may remain on a police (secure) ad hoc network but simultaneously be connected (and managed) to an ad hoc network of medical relief teams. In 4G management, protocols for ad hoc networks must be able to operate in all these scenarios.

Security management deals with security threats [42–53, 55]. Ad hoc networks are very vulnerable to security threats because the nodes (e.g. the unmanned nodes) can easily be tampered with, and signals can be intercepted, jammed or faked. Current protocols, such as SNMPv3 [41, 56, 62, 63], do provide us with some mechanisms to guard against eavesdropping and replay attacks using secure unicast, which is not efficient for all incoming network architectures.