Candidate:yao Ye

Vincent Hilaire

Ad Hoc Networks Measurement Model and Methods Based on Network Tomography

Keywords: Ad Hoc network, network tomography, network topology snapshot, link performance inference, topology identification

The measurability of Mobile ad hoc network (MANET) is the precondition of its management, performance optimization and network resources re-allocations. The traditional network interior measurement technique performs measurement on the nodes or links directly, and obtains the node or link performance through analyzing on the measurement sample, which usually is used in the wired networks measurement based on the solid infrastructure. However, MANET is an infrastructure-free, multi-hop, and self-organized temporary network, comprised of a group of mobile nodes with wireless communication devices. Not only does its topology structure vary with time going by, but also the communication protocol used in its network layer or data link layer is diverse and non-standard. Specially, with the limitation of node energy and wireless bandwidth, the traditional interior network measurement technique is not suited for the measurement requirement of MANET.

In order to solve the problem of interior links performance (such as packet loss rate and delay) measurement in MANET, this thesis has adopted an external measurement based on network tomography (NT). Being a new measurement technology, NT collects the sample of path performance based on End-to-End measurement to infer the probability distribution of the network logical links performance parameters by using mathematical statistics theory, which neither need any cooperation from internal network, nor dependence from communication protocols, and has the merit of being deployed flexibly. To the best of our knowledge, NT technique is adaptable for Ad Hoc network measurement.

This thesis has deeply studied MANET measurement technique based on NT. The main contributions are:

(1) An analysis technique on MANET topology dynamic characteristic based on mobility model was proposed. At first, an Ad Hoc network mobility model formalization is described. Then a MANET topology snapshots capturing method was proposed to find and verify that MANET topology varies in steady and non-steady state in turn periodically. At the same time, it was proved that it was practicable in theory to introduce NT technique into Ad Hoc network measurement. The fitness hypothesis verification was adopted to obtain the rule of Ad Hoc network topology dynamic characteristic parameters, and the Markov stochastic process was adopted to analyze MANET topology dynamic characteristic. The simulation results show that the method above not only is valid and generable to be used for all mobility models in NS-2 Tool, but also could obtain the topology state keeping experimental formula and topology state varying probability formula.

IV

(2) An analysis technique for MANET topology dynamic characteristic based on measurement sample was proposed. When the scenario file of mobile models could not be obtained beforehand, End-to-End measurement was used in MANET to obtain the path delay time. Then topology steady period of MANET is inferred by judging whether path delay dithering is close to zero. At the same time, the MANET topology was identified by using hierarchical clustering method based on measurement sample of path performance during topology steady period in order to support the link performance inference. The simulation result verified that the method above could not only detect the measurement window time of MANET effectively, but also identify the MANET topology architecture during measurement window time correctly.

(3) A MANET link performance inference algorithm based on linear analysis model was proposed. The relation of inequality between link and path performance, such as loss rate of MANET, was deduced according to a linear model. The phenomena that communication characteristic of packets, such as delay and loss rate, is more similar when the sub-paths has longer shared links was proved in the document. When the rank of the routing matrix is equal to that of its augmentation matrix, the linear model was used to describe the Ad Hoc network link performance inference method. The simulation results show that the algorithm not only is effective, but also has short computing time.

(4) A Link performance inference algorithm based on multi-objectives optimization was proposed. When the rank of the routing matrix is not equal to that of its augmentation matrix, the link performance inference was changed into multi-objectives optimization and genetic algorithm is used to infer link performance. The probability distribution of link performance in certain time t was obtained by performing more measurements and statistically analyzing the hypo-solutions. Through the simulation, it can be safely concluded that the internal link performance, such as, link loss ratio and link delay, can be inferred correctly when the rank of the routing matrix is not equal to that of its augmentation matrix.

Chapter 1 Introduction

Ad Hoc Networks

An Ad Hoc network is a self-configuration, self-organization, multi-hop wireless and temporary wireless network, which is composed of many wireless mobile nodes with wireless transceivers. Since the range of wireless communication is limited, long distance communications between any two nodes has to depend on the forwarding of intermediate nodes [1,2] . The mobile nodes collaborate with each other to set up a temporary network in order to implement the remote wireless communications, which is different from that in Cellular Wireless Networks with fixed infrastructures.

In Ad Hoc Networks, due to the diversity of nodes' motion mode, the randomness of wireless transceiver turnoff, the variety of transmission power, the disturbance between wireless channels and the influence of landform and weather, etc., network topology architecture based on shared wireless channels among different mobile nodes and link number distribution will change with time going by [3,4] . Specially, Ad Hoc network topology management, system architecture and protocol design is different from that in Cellular wireless network and IP network because of small transmission power of mobile nodes, low bandwidth of wireless channel, and energy limited or constraint. All above these facts directly influences the Ad Hoc network performance measurement method to be chosen.

Ad Hoc Network Topology Architecture

Ad Hoc networks commonly have two types of topology architecture, one is plane topology architecture, the other is the layered one [5] . In the plane topology architecture as figure 1-1, all the mobile nodes have an equal position about theirs' topology control, traffic management, transmission and reception of data, routing information choice.

Therefore, this architecture is also called as Peer-to-Peer one. The shortcoming of this architecture is that its expansibility is not good. When network scale increases to a certain degree, more network bandwidth will be consumed by routing protocol. Secondly, a great deal of network control information often leads to network congestion. Therefore, it only adapts to small scale networks. The merit of plane architecture is that there is no key node in theory, and it has high invulnerability, and it is easy to deploy and secure for its small overlay range. Therefore, the document uses the plane topology architecture of Ad Hoc network as its research objective. In layered architecture as the figure 1-2, Ad Hoc network is comprised of one or more clusters, and each cluster comprises one cluster header and more cluster members. More cluster-headers constitutes the higher layer network again, in which Ad Hoc network is divided into different clusters until it meets with user application requirement. Therefore, there are three types of nodes in layered architecture, such as cluster header, cluster member and gateway. The cluster members in the same cluster could communicate with each other depending on the forwarding of its cluster-header transmission, which is called as interior cluster communication. The cluster-members belonged to different clusters communicate with each other depending on the forwarding of gateway transmission, which is called as exterior cluster communication. Ad Hoc network layered topology architecture does not need to maintain the whole routing information so as to decrease the network control packets, so it has good expansibility. Its shortcoming is that gateway may become a bottleneck of network performance, and the maintenance and selection algorithm for the cluster-header is complicated. It is easy to deploy measurement proxy on the cluster-header so as to implement network performance measurement in the same cluster in the light of the traditional network measurement technique.

Ad Hoc Network System Architecture

According to Ad Hoc network inherent characteristics, such as self-organization, wireless multi-hop routing, dynamic topology, limitation of wireless bandwidth and energy and low security, its system architecture could be divided as the five layers as described in figure 1-3(a), such as physical layer, data link layer, network layer, transportation layer and application layer.

In the figure 1-3(a), physical layer mainly is in charge of wireless frequency choice, signal detection, transmission and reception, modulation/demodulation, wireless channel encryption/decryption. It also adopts wireless spread spectrum technique to implement wireless signal transmission and reception, such as DSSS and FHSS. Data link layer is divided into logical link control layer (LLC) and medium access control layer (MAC) again. The LLC has the function of assembling the data frame, checkout, flow and error control from point to point. In recent years, the MAC mainly adopts four mechanisms to control the shared wireless channel access which is chosen by mobile nodes. The first one is stochastic competition technique, i.e., CSMA/CA. The second one is sub-channel access mechanism, such as TDMA, FDMA, CDMA and SDMA, and so on. The last two mechanisms are polling method and dynamic adjusting method. Network layer mainly takes charge of neighbor discovering, routing choice and congestion control. The transportation layer could provide different processes in application layer with reliable or unreliable data transmission service. At present, transportation layer mainly adopts the traditional communication protocol, such as TCP, UDP or special protocols. Application layer provides different application service with the its application interface concerned.

(a) Ad Hoc network system architecture (b) Ad Hoc network adaptive system architecture Figure1-3 Ad Hoc network system architecture Considering Ad Hoc network characteristics, the five layers network system architecture (seen in figure 123) is often extended. For example, power and topology control are commonly added between physical and data link layer, cluster management function between data link and network layer, and position, self-configuration and security mechanisms between transportation and application layer. In order to decrease the complexity of Ad Hoc network system architecture, sometimes it is necessary to simplify the five layers system architecture. For example, data link and network layer, or transportation and application layer are often united as one layer, thus three or four layers Ad Hoc network system architectures have appeared. Since Ad Hoc networks are temporarily built up to implement special communication tasks, in different application environment, the number of mobile nodes, mobile rule, transceiver power and wireless link bandwidth are different too. In order to meet with requirements of specific applications, it is necessary to design cross layer network system architectures so as to support adaptive and performance optimization as the figure 1-3(b). In this figure, different layers could share each other's information to optimize network performance according to the constraint condition. Specially, this cross layer network system design could decrease information to be exchanged between different layers.

Ad Hoc Network Protocol

Data link layer communication protocol Ad Hoc network data link layer is divided into two sub-layers, i.e., LLC and MAC. LLC takes charge of data link management and control, and MAC controls nodes' access to shared wireless channel. Wireless channels in Ad Hoc networks are divided into three types, such as single channel, dual channels and multi-channels [5~8] .

In the communication protocols based on single channel, the mobile nodes share only one channel to transmit and receive data and control packet. However, confliction may occur among control packets, data, and between control packet and data for the problem of propagation delay, hidden and exposed terminal. Although this type of protocol adopts a certain mechanism to avoid the confliction among data, it is difficult to solve the problem of terminals, such as multiple access collision avoidance (MACA) [9] , MACA for wireless LAN (MACAW) [10] ], IEEE 802.11DCF [11] and Floor acquisition multiple access (FAMA) [12] . In the communication protocol based on dual channels, mobile nodes use two channels as control and data channel respectively to avoid conflicts occurring between data and control packet. This type of communication protocol has the ability to avoid the conflicts between data and control packet in theory. Basic access protocol solutions for wireless (BAPU) [13] and dual busy tone multiple access (DBTMA) [14] are all these classical dual channels communication protocols. In the communication protocol based on multi-channels, the neighbor nodes use different channels to communicate with each other at the same time t. In this case, access control is easier than in the other two cases. For example, one special channel could be used as common control one, or control packet and data could be transmitted on the same channel. But it should solve two problems, one is channel distribution, the other is access control. The former mainly solves the problem of distributing different channel for nodes to avoid confliction so that more nodes has the ability to communicate with each other at the same time. The latter focuses on when the nodes have the chance to use the channel. The classical protocols based on multi-channel is hop reservation multiple access (HPMA) [15] , multi-channel CSMA [16] , dynamic channel assignment (DCA) [START_REF] Wu | A new multi-channel MAC Protocol with on demand channel assignment for mobile ad hoc networks[END_REF] and multi-channel MAC (MMAC) [START_REF] So | Multi-channel mac for ad hoc networks: handling multi-channel hidden terminals using a single transceiver[END_REF] , and so on.

Besides, the data link layer protocol could also be divided into two types according to sending handshake signal method by different sources, one is sender active access channel protocol the other is receiver active access channel protocol. In the former one, before the sender sends a data, it firstly send RTS control packet to receiver to book channel, such as MACA and MACAW. In the latter one, the receiver is in charge of sending RTR(Ready to receive) control packet to the sender before its data transmission , and the sender which has received the control packet has the chance to send data so as to decrease the number of control packets and increase network throughput, such as MACA-BI [START_REF] Talucci | MACA-BI(MACA By Invitation): A receiver oriented access protocol for wireless multiple networks[END_REF] and RIMA [START_REF] Garcia-Luna-Aceves | US)Receiver-initiated multiple access for AD-HOC networks (RIMA) United States, The regents of the univerisity of California[END_REF] , and so on.

Network layer protocol When mobile nodes uses multi-hops method to implement data exchange in Ad Hoc networks, they need network layer protocol to provide packet data transmission with routing information. However, some factors, i.e., irregular channel varying, nodes' moving, joining and leaving state, will influence the Ad Hoc network topology dynamic characteristic [START_REF] Corson | Mobile ad hoc networking (MANET): Routing protocol performance issues and evaluation considerations[END_REF] . Therefore, network layer protocol need to solve the following problems, routing loop avoidance, routing cost control, expansibility, and its adaptability to network topology dynamic characteristic. According to different standards, Ad Hoc network layer protocols have different classification methods [22~24] . According to different routing choice algorithms, network layer protocols could be divided into distance vector protocol (DV), link state protocol(LS), source routing protocol(SR), and reverse link protocol(RL). According to the routing information obtained method, it could be divided into proactive and reactive protocol. The former one is often called as table driving routing protocol, such as DSDV [START_REF] Perkins | Highly dynamic destination-sequenced distance vector routing (DSDV) for mobile computers[END_REF] , FSR [START_REF] Iwata | ScalableRouting Strategies for Ad-hoc Wireless Networks[END_REF] , LANMAR [START_REF] Pei | LANMAR: Landmark Routing for LargeScale Wireless Ad Hoc Networks with Group Mobility[END_REF] , OLSR [START_REF] Adjih | Optimized link-state routing protocol[END_REF] and TBRPF [START_REF] Ogier | Topology dissemination based on reverse-path forwarding[END_REF] , and so on. The latter one sometimes is called as demand routing protocol, such as DSR [START_REF]The Dynamic Source Routing Protocol(DSR)[END_REF] , AODV [START_REF]Ad Hoc On Demand Distance Vector[END_REF] , TORA [START_REF] Park | Temporally ordered routing algorithm (TORA)[END_REF] , ABR [START_REF] Keong | Associativity based routing for ad hoc mobile networks[END_REF] and MSR [START_REF] Wang Lei | Multipath source routing in wireless Ad hoc networks[END_REF] , and so on. Specially, there exists another new network layer protocol which combines the merits of the two protocols to decrease the bandwidth cost and delay, and is called as hybrid routing protocol, such as ZRP [START_REF] Haas | The Zone Routing Protocol (ZRP) for Ad Hoc Networks[END_REF] , CEDAR [START_REF] Sinha | CEDAR: A core-extraction distributed ad hoc routing algorithm[END_REF] and SRL [START_REF] Sinha | Enhancing Ad-Hoc Routing with Dynamic Virtual Infrastructures[END_REF] , and so on. In recent years, multicast is used to Ad Hoc network layer protocol and has become a new hot point. The network layer protocol based on multicast includes ODMRP [START_REF] Gerla | On-demand multicast routing protocol (ODMRP) for ad hoc networks[END_REF] , MAODV [START_REF] Royer | Multicast operation of the ad hoc on-demand distance vector routing protocol[END_REF] , CAMP [START_REF] Garcia-Luna-Aceves | The Core-Assisted Mesh Protocol[END_REF] ,

AMRoute [START_REF] Bommaiah | AMRoute: Ad hoc Multicast Routing Protocol[END_REF] and AMRIS [START_REF] Wu | Ad Hoc Multicast Routing Protocol Utilizing Increasing id-numberS (AMRIS) Functional Specification[END_REF] .

In short, since Ad Hoc network system architectures are not fixed, and theirs applications are different according to user requirement, Ad Hoc network protocols are diverse and not standard [START_REF] Alfawaer | A novel multicast routing protocol for mobile ad hoc networks[END_REF][START_REF] Aguayo | Link-level measurements from an 802.11b mesh network. Sigcomm comput[END_REF] , which is different from IP network. Therefore, it is a challenge to implement measurement on Ad Hoc networks.

Ad Hoc Network Application

With the development of wireless communication and mobile terminals, such as PDA, mobile phones, laptops, pocket PC, some other communication devices based on wireless, infrared, and so on, Ad Hoc networks are becoming more and more interesting in the modern society [START_REF] Johansson | An enabler for personal area networking[END_REF]46] . Compared with cellular wireless networks, Ad Hoc networks have no base station. All the nodes in Ad Hoc networks not only are transceivers, but also have the router function. At present, Ad Hoc networks have become one of the hot research focus. For example, a famous international conference, i.e., Infocom, has published about 40% papers concerned with Ad Hoc network every year recently. Thus, Ad Hoc networks are used in many applications as the follows.

Military communication environment Since battle field communication system needs some special characteristic, such as flexibility, high invulnerability, high reliability, and easily deployment, and so on, Ad Hoc network justly meets with this specific communication requirement for its self-organization and nodes' mobility, which makes it the fist choice in digital battle field [START_REF] Aguayo | Link-level measurements from an 802.11b mesh network. Sigcomm comput[END_REF][START_REF] Aljnidi | Towards an autonomic security system for mobile ad hoc networks[END_REF] .

Temporary communication environment

In commercial conference, celebration and exhibition occasion, people often use Ad Hoc networks technique to organize some mobile terminals, such as laptops, pocket PC, and PDA, as a wireless mobile self-organization network to exchange information, which could avoid wiring and deploying network routing devices to establish the temporary communication environment.

Mobile communication environment Ad Hoc networks could be used to provide some mobile vehicles with wireless communication capability. University of California at Berkeley in U.S.A, Federal National Defense University in Munich, Germany are now studying how to adopt the Ad Hoc networks technique for freeway system so as to implement the autonomous wireless communication among automatic drive vehicles [START_REF] So | Multi-channel mac for ad hoc networks: handling multi-channel hidden terminals using a single transceiver[END_REF] .

Urgent communication environment After some visitation of providence events happened, such as earthquake, flood, fire or other disasters, the network communication environment with solid infrastructure often could not work well. Since Ad Hoc networks could quickly provide urgent communications in special environment, it is very significant for rescue and relief work [START_REF] Johansson | An enabler for personal area networking[END_REF] .

Research Background and Significance

Ad Hoc networks have now been used in both civil and military application, and have been one of the foreland research areas about network technique. At present, Ad Hoc network researches mainly focus on systematic architecture, communication protocols, self-organization and self-management technique, and so on[49~55]. However, little research is focused on Ad Hoc network performance measurement, there are the following reasons accounting for these phenomena:

(1) Ad Hoc network systematic architecture and communication protocol has not been standard for its inherent characteristic, it is difficult to adopts the traditional network measurement technique for Ad Hoc network, for it depends on certain network standard communication protocol and systematic architecture. For example, IP network with solid infrastructure adopts TCP/IP reference model and has standard communication protocol, it is easy to use an universal network performance measurement method on it based on ICMP, TCP, UDP and SNMP, and so on.

(2) Since Ad Hoc network is an autonomous system, it implements self-configuration, self-management during its different life period, such as deployment, operation and death period [START_REF] Asokan | An approach for reducing the end-to-end delay and increasing network lifetime in mobile ad hoc networks[END_REF][START_REF] Jain | Exploiting path diversity in the link layer in wireless ad hoc networks[END_REF] . However, the traditional network measurement technique depends on the collaboration among different nodes in the same AS(Autonomy System), which is difficult to adapt to Ad Hoc network autonomous characteristic.

(3) The traditional network measurement technique does not consider over the limitation of network resource and the nodes energy, but all these resources are expensive and limited in Ad Hoc network.

(4) The traditional network measurement technique is commonly used in wired networks with solid infrastructure and its network topology architecture keeps correspondingly steady, which could not adapt to the Ad Hoc network with topology dynamic characteristic. Therefore, it is necessary to find a new network measurement technique to satisfy the requirement of Ad Hoc network measurement according to Ad Hoc network topology dynamic characteristics.

The new applications about Ad Hoc networks have required high performance, and some Ad Hoc network theories and practical application systems all need to measure its performance, analyze and evaluate its performance parameters. The performance measurement could provide the new application deployment, resource optimization, system maintenance with scientific decision-making [START_REF] Anastasi | 11 b ad hoc networks: Performance measurements[END_REF] . There are various reasons accounting for the importance of Ad Hoc network performance measurement.

(1) Ad Hoc network is an important network application environment for digital battle field. However, war field situation analysis and efficiency evaluation is difficulty in information field research, it is importance to analyze and evaluate Ad Hoc network running state and dynamic characteristic, to adjust, deploy network and to resume the injured nodes or areas through network measurement.

(2) Network measurement could provide traffic engineering, network behavior analysis and communication protocol with verification means. With the appearing of Ad Hoc network new application, the flow characteristic is becoming more and more complicated in Ad Hoc network than before, and different application has different network behavior characteristic. It is effective to compare different network communication protocol and evaluate new protocols by network measurement.

(3) Ad Hoc network measurement could provide effective technique means for network management. For example, Ad Hoc network link delay, loss ratio, link connection state and congestion could be obtained by network measurement to position the network performance bottleneck and obtain its performance views. Moreover, It could also evaluate QoS of Ad Hoc network, optimize network resources to meet with users end to end experience through network measurement.

In a word, it is a key problem to establish an effective Ad Hoc network measurement theory and method for developing Ad Hoc networks technique. NT technique adopts end to end measurement without considering the network interior architecture and communication protocol so as to solve Ad Hoc network measurement. Therefore, research on Ad Hoc networks measurement theory and method based on NT technique is very significant to improve its network performance and manageability. In addition, It also provides the Ad Hoc network practical measurement application with necessary theory basis.

Research support

The research is supported in part by the Ph

Research Contents

The network topology architecture keeps steady during measurement period is one precondition of NT technique. It is a challenge to Ad Hoc network measurement for its topology dynamic characteristic. The document firstly summarizes and analyzes traditional network measurement and NT technique, and brings forth Ad Hoc network link performance inference methods based on NT technique. The main research ideas are as the follows.

(1) The research on Ad Hoc network topology dynamic characteristic based on mobility model. The scene file of mobility model is regarded as our research objective, and brings forth topology snapshots capturing method to obtain topology architecture of Ad Hoc network at any time. Next, the statistical analysis model is established to verify that there exists topology steady period for Ad Hoc network, which provides a method for extracting the characteristic information of Ad Hoc network topology steady period with theoretical basis.

(2) The research on Ad Hoc network dynamic characteristic based on measurement sample. If the scene file of Ad Hoc network could not be obtained beforehand, the end to end active measurement method is adopted to collect the path measurement sample in order to find out Ad Hoc network topology steady period and its architecture, which provides the Ad Hoc network interior link performance inference with technique support.

(3) Ad Hoc network link performance inference method based on NT technique.

According to different cases of routing matrix in linear analysis model, two methods are brought forth to solve Ad Hoc network link performance inference, one is based on linear analysis model, the other is based on multi-objective optimization.

The research contents are described as the follows in detail.

(1) The research on Ad Hoc network topology snapshots capturing method.

According to the snapshots in our routine photograph, the position of Ad Hoc network mobile nodes could be obtained in any time through scanning and analyzing on the scene file of mobility model. Then Ad Hoc network topology snapshots could be obtained by analyzing on these position data. Next, our research focuses on some dynamic characteristic parameters of Ad Hoc network, such as topology steady and unsteady period, link connection ratio, topology lifetime, and so on. At last, we use RW, RWP, RPGM, Freeway, and Manhattan mobility model as example to verify the methods above in simulation.

(2) Ad Hoc network topology dynamic characteristic analysis technique based on mobility model. The fit hypothesis testing is used to describe the Ad Hoc network topology dynamic characteristic rule, such as the number of steady period and unsteady one probability distribution in certain time t , the duration time probability of steady period and non-period, and so on. With the background provided by the methods above, Continuous Markov chain statistical method is used to infer the forecast formula of topology state keeping invariant and the warning formula of topology state varying, which provides the measurement window time for Ad Hoc network with theory thesis.

(3) Ad Hoc network topology dynamic characteristic analysis technique based on measurement sample. NT technique uses active measurement method to obtain end to end path performance sample. The Ad Hoc network topology steady period is found according to the inference rule that whether the path delay jitter is near to zero, and the long time of which is considered as measurement window time. Next, the Ad Hoc network topology architecture during measurement window time is inferred based on clustering algorithm according to path performance measurement sample. At last, simulation experiment is used to verify all the methods above.

(4) To bring forth an Ad Hoc network link performance inference method based on linear analysis model. Firstly, An uniform linear model is presented to analyze the Ad Hoc network delay and loss ratio in the document. Moreover, The inequality between path and link performance is inferred, which proves in theory that if the different sub-paths have more longer length of shared links, their communication characteristics are more similar. That is, the loss rate and delay are more similar. Secondly, In the linear analysis model, when the rank of the traffic matrix A is equal to that of its augmentation matrix, Ad Hoc network link performance probability distribution in certain time t could be obtained through discrete the solution space and analyzing on the statistical results, and the link performance having the maximum value of probability will be chosen as the inference one. In addition, the simulation results verified the effectiveness of all the methods above.

(5) To bring forth an Ad Hoc network link performance inference method based on multi-objective optimization. Firstly, in linear analysis model when the rank of route matrix is not equal to that of its augmented matrix, there is no solution for the non-homogeneous linear equations. In order to solve this problem, link performance inference problem is transformed to a multi-objectives optimal one through simple mathematical transform for the non-homogeneous linear equations in the document.

Secondly, we use the genetic algorithm to compute its sub-optimal solution. Furthermore, through analyzing on the sub-optimal solution statistically, the link performance probability distribution in certain time t could be obtained, and the link performance having the maximum value of probability will be considered as the inference one. At last, the simulation results verified the effectiveness of the method.

Plan of the Document

After a brief overview of the concerns of this research work concerned, we present the organization of this document, which have been divided into seven chapters. We now present it in more detail the contents of each chapter.

Chapter 1 as an introduction, it presents the basic conception of Ad Hoc network, research background and significance, research contents, main contributions and the plan of the document.

Chapter 2 mainly introduces the related works, summarizes and analyzes the traditional network measurement technique, NT technique principle and methods, and the current approaches used in Ad Hoc network measurement.

Chapter 3 presents an Ad Hoc network topology dynamic characteristic analysis

technique based on mobility model. An Ad Hoc network topology snapshots capturing method is brought forth firstly through analyzing on the scene file of mobility model.

Next, some dynamic characteristic parameters of Ad Hoc network topology are computed statistically through analyzing on the data of topology snapshots. On this basis, an Ad Hoc network topology dynamic characteristic analysis technique is presented according to Markov stochastic process and verified in simulation.

Chapter 4 presents an Ad Hoc network dynamic characteristic analysis technique based on measurement sample. The precondition of applying NT technique for Ad Hoc network measurement is that network topology architecture is known ahead, and keep invariable during measurement window time. On the analysis on the end to end path measurement sample, we present an Ad Hoc network topology steady period characteristic information extraction and topology identification methods, which are verified in its effectiveness in simulation.

Chapter 5 presents an Ad Hoc network link performance inference method based on linear analysis model. First of all, the delay and loss ratio analysis model are united as a linear analysis model. Then we have inferred the inequality relation between path and link performance and bring forth an Ad Hoc network link performance inference method based on linear analysis model.

Chapter 6 presents an Ad Hoc network link performance inference method based on multi-objective optimization. In linear analysis model, when the rank of route matrix is not equal to that of its augmented matrix, we transform the problem of solving the non-homogeneous linear equations to multi-objective optimization one and use gene algorithm to compute the sub-optimal solution of the non-homogeneous linear equations.

The simulation results prove the effectiveness and correctness of the method.

Chapter 7 summarizes all the related works, and discusses the deficiencies about our research works.

Chapter 2 Related Works

Introduction

Network measurement technique depends on certain measurement method and standard to obtain measurement sample based on measurement devices or tools. It applies the network performance analysis model to identify network topology architecture, and to infer performance parameter and traffic characteristics that provides the scientific decision for network resources optimization deployment, network management, failure point position, and so on. For the wired network with solid infrastructures, such as Internet, it often adopts an interior direct measurement method, that is also defined as traditional measurement technique in this chapter. During the middle period of years 90 in last century, NT measurement technique was brought forward by Y. Vardi [4] , who used the end-to-end measurement sample to infer network link performance parameters. Ad Hoc network performance varies with time going by for its network topology dynamic characteristic, which increases the difficulty to measure Ad Hoc network performance. At present, Ad Hoc network link performance measurement lacks of a systematical and effective measurement theory, there are about two reasons accounting for this case. (1) Traditional network measurement technique not only need the collaboration among nodes in the same AS, but also adopts a certain IP standard protocol, such as SNMP、ICMP for the wired network with solid infrastructures. Although it has high measurement precision, its computing complexity is too high for not considering the limitation of network bandwidth and energy. Therefore, it is difficult to introduce the traditional network measurement technique into Ad Hoc network measurement for its topology dynamic characteristic, self-organization and self-management. (2) It is difficult to bring forth a light, real time and effective link performance inference method for Ad Hoc network limited resource and topology dynamic characteristic. In order to solve the problem above, NT measurement technique is applied for Ad Hoc network measurement in the document, which analyzes and infers the Ad Hoc network link performance by using path performance measurement sample(i.e., delay, loss ) according to performance analysis model At first, the chapter summarizes the traditional network measurement technique, then, it discusses the basic principles and methods of NT measurement technique. At last, the up to date research results about Ad Hoc network measurement technique are presented.

Traditional Network Measurement Technique

The traditional network measurement technique could be traced back to 70 years in twenties century, Kleinrock founded ARPNet network measurement center in UCLA.

The objective of its network measurement is to position the failure point of network based on the pressure test. With the increase of network scale and the development of new network applications, its objective transformed to find the link connection state in order to ensure network system working well. As early as ninety years in the 20 century, with the appearance of Web technique and internet commercial application, its objective extends to network performance measurement, flow characteristic analysis, topology identification and QoS optimization.

The effective network management is the prerequisite to ensure network working well, and the network manageability is determined on by its measurability. Therefore, in recent years, some institutes at home and abroad have focused their research on network measurement [59~63] , such as CAIDA, NLANR, IEPM/SLAC, RIPE NCC, USCD, Cisco and Sprint, and so on.

In 1994, Michigan University and Merit network corporation collaborated to carry up an Internet Performance Measurement & Analysis (IPMA) project in order to build up internet data collection and statistical analysis infrastructure. It mainly solves two problems at that time, one is how to solve the problem of routing stability, network topology identification and Data visualization, the other one is network performance measurement. They deployed some proxies in the gate of backbone network to collect the routing information about interior and exterior AS to obtain the statistical data of routing jitter, routing table increment, topology architecture and invalid routing, and displays the routing and network performance statistical information in data visualization mode. The fruit of this project mainly embodied that it fund several abnormality trends and systematical morbid behaviors of network which lead to routing jitter. At present, its main research emphases on the routing information and network flow analysis, and has developed some tools concerned, such as BGP-Inspect and Flamingo.

Stanford Linear Accelerator Center (SLAC) founded an Internet End-to-End Performance Monitoring (IEPM) research group in 1995. It mainly implemented two projects about network performance measurement. One is Ping End-to-End Reporting (PingER), which not only uses Ping program to measure network end to end performance, such as delay, loss ratio, delay jitter, TCP throughput and network connectivity, but also researches on disorder and repeated packets in internet. The other project is IEPM-BW, the objective of which is to establish a simple, creditable, open infrastructure to measure and manage the network based on active end to end network measurement. It integrated some measurement tool sets, such as Ping, traceroute, Iperf, Pipechar,bbcp and bbftp, and so on, to achieve end to end user experience(i.e., path bandwidth) and high speed link bandwidth. At present, the latter one has deployed about ten nodes in North America, Europe and Asia, each node could measure the performance the remote computers from 2 to 36. Of course, there are some other organizations and projects about network measurement.

Advanced

For example, Sprint corporation in U.S.A. has implemented some network measurement projects, such as IPMon. UCSB and PAT (Internet2 Performance Architecture and Technology) collaborated to implement perfSONAR (Performance Service Oriented Network Monitoring Architecture) project. University of Oregon has implemented the Routeviews project about BGP routing. These projects could not be described in detail for the limitation of length.

Since IP network is gradually changed as telecommunication backbone one, and the requirement of telecommunication for IP network measurement is becoming stronger and stronger. Some network switching equipment manufacturers at home and abroad have produced some measurement devices concerned for its engineering application. For example, TI corporation in U.S.A. adopts DSP and embedded technique to implement a real time distributed IP QoS management system (PIQUA). it could provide the QoS control mechanism for audio and video transmission, etc., multimedia information transmission with QoS. Fluke Networks Corporation in U.S.A. has developed the Ethernet network performance analysis apparatus in telecommunication level to implement four network performance parameters measurement, such as delay, loss ratio, delay jitter and throughout, and so on. It also could analyze the network performance trend in 24 hours incessantly. Ixia Corporation in U.S.A. has implemented an IxRave system, it could be deployed at the client node, network edge, and network center node to achieve failure node position, end to end server quality experience. Sprint Corporation in U.S. has implemented a network measurement platform, such as SprintTestCenter, It integrates some measurement tools to achieve performance, pressure and communication measurement for Ethernet network from its second layer to seventh layer.

In recent years, some network measurement projects has also been implemented in Chinese education systems and institutes, and have achieved a certain fruits. The network information center of Tsinghua University adopts distributed probes, centralized data process and analysis mechanism to implement a end to end network performance measurement and failure node analysis system(i.e., PlanetLab). PLA Technology University has implemented an extended, distributed network measurement platform, which integrated some measurement tool and used active or passive method to achieve large scale network performance measurement. Xi Dian University has developed a distributed network measurement and analysis system (i.e., DNMAI). It comprised control node, monitoring node and probes, and used XSL as data model to achieve custom-built network performance measurement according to users' requirement.

In short, network measurement system commonly includes the following three factors, measurement objective, measurement environment, and measurement method [34~36] . The network measurement in different environment could choose different measurement objective according to different measurement objective. It could be divided as performance measurement, topology identification, flow measurement, and so on [37~39] , according to different objective. It could also be classified as active or passive measurement according to whether probes are infused into the network [40~43] . It is according to the number of source nodes that Network measurement could be divided as single source or multi-source measurement. Of course, it could be classified as collaboration or non-collaboration one according to whether the network interior nodes collaborate with each other. Since different network measurement methods adopt different network communication protocol, it could be divided as measurement based on BGP protocol, measurement based on TCP/IP protocol set, measurement based on SNMP, and measurement based on special measurement protocol, such as IPMP, OWAMP, TWAMP, IPFIX and PSAMP, and so on.

However, with the increment of network scale, it is hardly or not possible to exchange network measurement information among different AS because of network different systematic architecture and non-collaboration. It is difficult to deploy large number of measurement nodes in the AS belonged to other IPS for security. Vardi firstly brought forth the idea of introducing CT in medicine area into network measurement. Then a new network measurement technique is coming into being, which is called as Network Tomography(NT) [START_REF] Vardi | Network tomography: Estimating source-destination traffic intensities from link data[END_REF] , The main idea of NT technique is to use end to end or edge to edge performance measurement to infer network interior link performance and identify network topology architecture.

NT Measurement Technique

NT measurement technique adopts active or passive measurement method for the limited nodes that users are interested with to infer link performance, topology architecture or flow characteristic according to the path performance measurement sample [75~77] . The objective of NT measurement technique mainly focuses on link delay or loss rate inference, link bandwidth and throughput inference, network topology architecture identification and traffic matrix estimate. The measurement process in NT technique consists of three steps [78~82] . Firstly, measurement system model must be built on, including measurement topology model and performance analysis model, which generally adopts logic tree network topology model, and makes use of the relationship between nodes in measurement topology model and packet transmission behavior to build up performance analysis model. Secondly, active or passive measurement method is used to obtain the end-to-end measurement sample, then to evaluate the temporal and spatial independence of measurement sample. At last, the mathematics and statistics theory are used to analyze and evaluate the measurement sample based on performance analysis model to infer link performance or to identify topology architecture.

Thus it can be seen that there is much difference between traditional network measurement and NT technique. The latter adopts end to end or edge to edge measurement to obtain the path performance measurement sample, and infers network link performance according to the measurement sample, which does not need the collaboration among nodes in the same AS and neither deploy measurement devices in the interior network. Therefore, NT measurement technique is irrespective of network interior architecture and communication protocol.

NT Measurement System Model

Measurement system model is the basis on NT measurement technique. If the number of source node which has the chance to send measurement probes, is only one in measurement process, and the number of leaf nodes collecting measurement sample is more than one, where exists one-to-many relationship between source node and leaf nodes, this measurement style is often called as single-source measurement model. we often uses a tree topology measurement model to descript it as the figure 2-1(a) .

Otherwise, if the source nodes and leaf nodes exit many-to-many relationship, this measurement style is generally called as multi-source measurement and often uses the non-loop graph topology measurement model to describe it as the figure 2 , Because there is only one source node to send the probes. However, leaf nodes 4,5,6,7 all have the chance to collect the measurement sample. The member of link set L contains ordered pairs (i, j) such that node i sends its data to node j directly, destined for the leaf node r( r R ∈ ). The link (i, j) is simply denoted by , l i j ( , l L i j ∈ ). However, the path from the node i to j is denoted by , P i j . Let f(i) denote the father set of the node i, then the ancestor set of node i could be denoted as :

1 2 ( ) { ( ), ( ),..., ( )| ( ) } n n F i i i i i S f f f f = ∈
. noted that there exists the following rules:

0 ( ) i i f = , 1 ( ) ( ) i f i f = and 1 ( ) ( ( ))( 1) n n i f i n f f - = ≥ .
In the multi-source measurement model as in figure 2-1(b), there are more than one source nodes which have the chance to send probes, such as {0, } S i =

. If the number of source nodes and leaf nodes are M and N respectively, the network architecture in multi-source measurement is called as M-by-N topology one [16]. Multi-source measurement recently mainly focuses on the network topology identification. The literature [83] supposes that if the link performance of 1-by-2 and 2-by-1 topology architectures could be inferred, then M-by-N topology could be identified also, but it does not bring forth the method how to identify the topology architecture. The literatures [84,85] put forward a method to identify a 2-by-2 network topology architecture, but this method has a certain limitation and some unreasonable hypothesis. This chapter adopts the single source measurement model as the figure 2-1(a).

NT Measurement Analysis Model

NT measurement analysis model mainly consists of performance analysis model and network topology architecture identification model. The former focuses on link loss rate and delay inference, and the latter on topology architecture identification.

Link Loss Rate Analysis Model

The principle is to use the mathematical method to describe the relationship between the link and path performance. For example, Bernoulli model [86~92] and Gilbert model [START_REF] Dong | Bayesian inference of network loss and delay characteristics with applications to TCP performance prediction[END_REF][START_REF] Vijay | Multicast inference of temporal loss characteristics[END_REF] are often used in link loss rate inference. The former supposes that the loss of packets in one node is independent among each other, which actually is a Bernoulli stochastic process. Stochastic process

( ) X x r = ( r R ∈ ) is used to
describe state of the leaf node r receiving probes, 1

x r = denotes node r receiving a probe, otherwise 0 x r = . For the N probes, the receiving state of leaf node r could be denoted as

( ) { } n X x r r = (1 n N ≤ ≤ ).
If the link loss rate parameter is presented as

( )( ) L l l r r α α = ∈ ,
where r α is the loss rate of link l r , the aim of Bernoulli model is to obtain the maximum estimate:

arg ( | , ) Max P X T r R α α α * = ∈
. However, the Gilbert model considers that there exits time dependence correlation between the consecutive probes. For instance, if the probe with sequence one is lost in one node, the probability of probe with sequence two in the same node being lost is higher. Therefore, Gilbert model uses two state Markov process to describe this temporal dependence, where one denotes probe loss and zero no loss in figure 2-2.

No Loss 0 Loss 1

q p 1-q 1-p Figure 2-2 Gilbert loss model
In Gilbert model as in figure 2-2, p denotes that the probability of current probe is not lost where the one after which is lost, while q denotes that the probability of current probe is lost where the one after which is not lost. If 1 p q + = is satisfied, Gilbert model could be changed into Bernoulli model. The parameter of link l k could be denoted as

( , ) p q l l k k
when Gilbert model is used to describe and infer link packet loss. Then the link loss performance could be denoted as ( , ) {( , ),

} P Q p q l L l l k k k =
∈ , the problem of link loss inference is transformed to solve that of maximum likelihood estimate, that is

( , ) arg ( |( , ), ) ( , ) P Q Max P X P Q T P Q k R * = ∈
, where T denotes different time.

Link Delay Analysis Model

In link delay analysis model, we often suppose that the system clocks in each node are synchronous, and the discrete delay mode and continuous delay one are often used. In general, the discrete delay model adopts the discrete time method to study the probability distribution of link delay based on NT. However, the continuous delay time model often uses the cumulate generating function (abbreviated as CGF) to infer link delay parameters. Owing to using the logarithmic operation in CGF for its un-linear correlation, there exists some variances in the inference result, and even sometimes the variance is high. Network delay includes the fixed delay time and mutative one. The sending delay ( T t ) and transmission one ( T g ) composes the former, and the process delay ( Tp ) and queuing delay ( Tq ) the latter. Therefore, the link delay analysis model could be presented as the formula 2-1.

n m m d i j i j V x x i j m = ⊕ ∈ ∑ =
Where n is the number of measurement times. If ( , ) d i j ε < is satisfied, node i and j are deemed to brother node, and ε is a threshold value. Therefore, network topology architecture could be inferred through computing the ( , ) d i j between nodes, but it is a bin-tree architecture. However, a tree topology architecture could be inferred by expanding the method above.

NT Measurement Method

The NT measurement methods could be divided as the active measurement and passive one according to whether there are probes to be infused into the network.

Active measurement method It uses one or more sources to send probes into the network. However, the background flow will influence the transmission behavior of probes and lead to its delay, loss and out of order phenomena. The link performance and topology identification is inferred according to the measurement sample which is collected by leaf nodes. The characteristic of this method is its deployment flexibility and high controllable merit. However, the shortcoming of this method is that the probes will influence real network performance, which could be solved by constructing special probe, choosing right measurement time and sample technique, and so on. At present, the active measurement method is used in many network measurement research projects.

Passive measurement technique It uses the leaf nodes to collect the background flow to infer link performance, identify topology architecture, and analyze on the flow characteristic according to the measurement system model and analysis model without infusing probes into the network. The merit of this method is that it does not need to send additional packets into the network which will influence the real network performance.

However, its merits are that it needs to collect large number of background flow and high sample technique for the high speed network. For the low speed network, it will spend more time on collecting enough background flow. Specially, there exists the problem of information leakiness for user data and privacy.

NT Measurement Probes

Unicast probe [104~107] is transmitted by the source node to the leaf nodes according to a certain sample rule as in figure 2(a). Link loss rate and delay could be inferred on the basis of the number of unicast probes and that the leaf node receiving, end-to-end delay, and so on. Owing to unicast, communication is supported by many networks, the merit of unicast probe is its broad application scope. Although the interval between unicast probes accords with a certain sample rule, which could reduce the influence brought by active measurement in a certain extent, as well as it will destroy the correlation of the two neighbor unicast probes and reduce the precision of measurement. As in figure 2-2(a), the source node 0 sends unicast probe, since the leaf node 3 and 4 receive unicast probe dependently, if the node 3 receives a unicast probe, but node 4 not, it is difficult to judge where the unicast probe is lost.

Multi-cast probe

In order to settle the limitation of unicast probe above, the multicast probe is put forward in network measurement [108~108] . As in figure 2-2(b), the source node 0 transmits the multicast probe to a group of leaf nodes, such as node 4,5,6 and 7. Since the multicast probes have the same communication characteristic in the shared path, it will resolve the problem of correlation among probes, and improve the precision of measurement. If node 3 receives the multicast probe, but node 4 not, it is easy to infer that the probe is lost in the link 4 l . Of course, there are much limitation on multicast probes.

One is that some network switching devices, such as switcher and router, do not support or configure multicast communication protocols, which will influence its application scope. The other is some network switching devices adopt difference process methods on unicast and multicast, which will also affect the measurement precision in some extent. measurement network performance as in figure 2-2(c) [119~121] . A packet pair usually comprised of two unicast probes with small interval. The interval between two unicast probe is smaller than that between different packet pairs. In figure 2-2(c), source node 0 sends one packet pair to node 3 and 4, if the first unicast probe in the packet pair arrives at node 3 successfully, then we could safely guess that the probability of node 4 receiving the second unicast probe is near to 100%. Therefore, packet pair not only has the properties of multicast probe, but also extends the application scope of unicast probe.

However, packet pair only takes into account the correlation between unicast probe in packet pair, and it is just used for bin-tree measurement analysis model.

Packet stripes probe In order to resolve the limitation of packet pair above, N.G.

Duffield [122] introduced the packet strips into network measurement, which extends the number of unicast probes from two to many as in figure 2-2(d). From the other point of view, the packet strip could be considered as many packet pairs, which supports the different packet pairs with correlation in the shared path. However, when the number of unicast probes is more enough, packet strip could be changed as unicast probe.

NT Measurement Sample Technique

No matter what measurement methods are adopted, sample technique is often used to decrease measurement sample and storage space for high speed network without influencing the precision of measurement. The sample technique used in active method focuses on the distribution function which accords to the probe interval rule, such as periodic sample, stochastic sample and Poisson sample, and so on.

However, the sample technique used in passive measurement method focuses on the distribution function that leaf nodes adopt to collect the background flow, such as system sample, stochastic sample and hierarchical sample. System sample uses a distribution function to determine the start time of sample and the time duration, which mainly includes fixed periodic sample and variable periodic sample. Stochastic sample uses a stochastic process which has been defined beforehand to determine the start time of sample and time duration to assure the independence of sample choice and agonic characteristic of measurement, it mainly includes n out of N sample and probability sample. Hierarchical sample divides the collectivity into many subsets according to a certain application characteristic, then extracts sample from these subsets.

NT Measurement Inference Method

NT measurement inference method aims to use end-to-end network performance measurement sample to infer the probability distribution of link performance based on measurement analysis model and performance analysis model, which mainly is composed of Maximum Likelihood Estimate (MLE), Expectation Maximization method(EM) and Bayesian estimate.

Maximum Likelihood Estimate Method MLE [START_REF] Duffield | Inferring link loss using striped unicast probes[END_REF] is one of the elementary method on parameter estimate, which supposes that link performance parameter accords with distribution ( ; ) f X Θ , where , then its pseudo function follows the formula 2-2.

∏ = = n i i Θ y p Θ Y L 1 ) ; ( ) ; ( (2-2)
The objective of MLE is to find the value of the parameter Θ when ( ; ) L Y Θ being its maximum value, which could be denoted as ˆarg

( ; ) Θ MaxL Y Θ =
. Nevertheless, it is difficult to find the transcendent distribution function ( ; ) f X Θ of network link performance parameter X. Even though it is found, there are high computing complexity degree of pseudo parameter estimate for its complexity of pseudo function with large network scale.

Expectation Maximization method EM algorithm [START_REF] Liang | Maximum pseudo likelihood estimation in network tomography[END_REF][START_REF] Tsang | Passive network tomography using EM algorithms[END_REF][START_REF] Wei | Mobile Ad hoc Network Delay Tomography[END_REF] uses partial measurement sample to infer maximum pseudo value of link performance distribution function. It includes two procedures, that is, E-step and M-step. The main problem about EM algorithm is that it could obtain the partially optimized solution, not the unitary optimized one. For the sake of computing complexity increasing by the scale of network, Pseudo-EM Algorithm could decompose a large scale problem to several small scale ones.

The maximum likelihood of these small scale problems could be expressed as the following formula 4, where S is set of all small scale problems.

( , ,..., ; ) ( ; ) 1 2 1

n s s s L Y Y Y X P Y X i n i s S ∏ = ∏ = ∈
Bayesian estimate method It uses the transcendent probability distribution of link performance to infer the posterior one. However, how to get the former probability distribution is a difficult work. It is also difficult for Bayesian estimate method to obtain the link performance parameter with large network scale for its computing complexity. In order to solve this problem, Markov Chain Monte Carlo method is brought forth to infer link performance parameters by using Gibbs and Metropolis-Hasting sample rule based on Bernoulli and Gilbert probability model [START_REF] Dong | Bayesian inference of network loss and delay characteristics with applications to TCP performance prediction[END_REF]124] .

In short, MLE and Bayesian estimate methods need to know the transcendent distribution, but it is very difficult to obtain in practice. EM resolves the problem of computing the estimated parameter of network link performance in math, but it is easy to converge on a partially optimized solution.

Ad Hoc Network Measurement

Andreas Johnsson and L. J. Chen [START_REF] Johnsson | A Study of Dispersion-based Measurement Methods in IEEE 802.11 Ad-hoc Networks[END_REF]140] , et al., bring forth to apply active measurement for Ad Hoc network and research the useable bandwidth and capacity of path respectively.

In order to decrease the additional cost that is brought by the active measurement, Fragkiskos [START_REF] Papadopoulos | Predicting the performance of mobile ad hoc networks using scaled-down replicas[END_REF] , et. al., brings forth to reduce the network scale to forecast the throughput, delay and loss ratio of Ad Hoc network path, but a whole Ad Hoc network performance measurement model and system is not put forward. Y. Lu [142] ,et al., uses traditional measurement method to obtain the Ad Hoc network link loss ratio ,and the influence of Ad Hoc network congestion and node mobile characteristic on link performance under the AODV and DSDV protocol. Cheikh Sarr [START_REF] Sarr | Estimating Average End-to-End Delays in[END_REF] , et al., puts forward a path delay measurement protocol, that is, Delay Estimation in Ad Hoc Networks(DEAN). In this method the neighbor nodes send Hello packet to exchange each other's link delay information, collaborate with each other to obtain path delay. Since all the measurement methods above adopt the traditional one, they need the collaboration of network interior nodes and certain measurement protocol, which do not accord with Ad Hoc network self-organization, self-organization. Specially, they do not consider over the influence of Ad Hoc network topology dynamic characteristic on network performance, and only could evaluate the path performance, not the interior link performance [START_REF] Hou | Performance Evaluation of Wireless Multihop Ad Hoc Networks Using[END_REF] . There are the following reasons to explain the cases above. Firstly, since Ad Hoc network has limited bandwidth, the traditional network measurement method will consume a certain additional expensive bandwidth to collect, process and transmit the statistical data, which will increase Ad Hoc network load. Secondly, because of node mobility and environment influence, link connection state will change with time going by, which not only bring much trouble in link performance measurement, but also will influence the real link performance. Therefore, it is a challenge for Ad Hoc network performance measurement because of its characteristic and the limitation of traditional measurement method.

Although NT technique is mainly applied for the wired network with solid infrastructure (i.e., internet) for its advance, it has been introduced into some wireless networks, such as 3G network, wireless sensor network, and so on. For example F. [START_REF] David | Efficient monitoring of end-to-end network properties[END_REF] . This method adopts passive measurement method and deploys some proxies to collect the background flow on central network of 3G to estimate TCP performance parameters, such as the number of re-transmission, RTT, and so on. The literature [145] used unpiloted aircraft cruise (PAC) as its research background, and brings forth a REC mobility model. In REC, since the initial position of nodes and its mobile rule are known beforehand, it is easy to use mathematical method to obtain the Ad Hoc network topology architecture at different time. Then NT technique is used to infer link performance, such as delay and loss ratio, during the minimum value of Ad Hoc network topology lifetime.

Ricciato et al., introduces NT technique into 3G network performance measurement

The literature [172]adopts expectation maximum (EM) to infer link delay probability distribution based on discrete link delay analysis model according to the packet transmission relativity on the shared paths. The literature [147]adopts factor graph to obtain logical link packet successful transmission experimental distribution. But all the methods based on NT technique are all used REC mobility model as its research background, it is unknown whether they adapt to other mobility models.

Conclusion

NT technique adopts end to end measurement to obtain the path performance measurement sample, and infers network interior link performance according to the measurement sample based on network measurement model, system analysis model and statistical theory. It does not need the collaboration among nodes in the same AS and neither deploy measurement devices in the interior network. Therefore, NT measurement technique is irrespective of network interior architecture and communication protocol. At present, NT technique is mainly used in wired network measurement with solid infrastructure to infer link performance based on path performance sample. There are some problems to be solved before it is used in Ad Hoc network measurement. Firstly, it should be verified in theory that it is practicable to use NT technique in Ad Hoc network. Secondly, NT technique in Ad Hoc network should be implemented at a certain measurement occasion because of its topology dynamic characteristic. Thirdly, if Ad Hoc network topology varies frequently and the topology duration time is short, it is necessary to bring forth a light inference method to take a tradeoff between inference precision and computing cost. At last, if the mobile scene file could not be obtained beforehand, it is necessary to research on the characteristic information extraction method of Ad Hoc network steady period and topology identification to provide the NT technique on Ad Hoc network measurement with technique basis.

Chapter 3 Topology Dynamic Characteristic Analysis

Technique Based on Mobility Model

Introduction

For the Ad Hoc network topology dynamic characteristics, there are many problems for using traditional network measurement technique in Ad Hoc network. However, NT technique makes use of end to end measurement to analyze and infer link performance or network topology architecture, which provides a new research method for Ad Hoc network measurement. The premise of using NT technique on Ad Hoc network is that the network topology does not vary or preserves relatively steady during measurement period.

Nevertheless, the Ad Hoc network topology dynamic characteristics not only influences network performance, but also affects the precision of link performance inference results.

Although researches have focused on the dynamic characteristics of mobility models in Ad Hoc network and taken some achievements recently, little attention was paid on the link topology dynamic characteristics of mobile models [168,169] . Narayannan Sadagopan et al. [170] puts forward a statistical method to obtain the dynamic characteristic of mobility model, which includes how to compute the probability density distribution of link and path connection time. Nevertheless, the research mainly studies on the viewpoint of the influence of dynamic characteristic on the performance of active network protocols, not on that of the Ad Hoc network measurement. At the same time, statistical analysis method is only applicable for the certain mobility models with mobile node having only one time to change its' velocity or direction in one second, such as RPGM, Freeway and Manhattan mobility model, not for the other mobility models in NS-2 tool, such as RW and RWP. Although Tian et al. [START_REF] Guangli | Topology Variety Model for Mobile Ad Hoc Networks[END_REF] brings forward a link connection time model which could be used to compute the link connection minimum time, and further to obtain the minimum value of network topology lifetime. However, the computing model is too complicated for not being simplified. Besides, it is only adaptable for the RWP mobility model, not for the other mobility models in Ad Hoc networks. Wang et al. [START_REF] Wei | Mobile Ad hoc Network Delay Tomography[END_REF] brings forth a circle mobility model, in which when the initialization position of mobile nodes is known beforehand, the network topology architecture of Ad Hoc network could be computed according to the rules of nodes' movement. Specially, the minimum of network topology lifetime could also be obtained statistically. However, this research on NT measurement technique in Ad Hoc network mainly focuses on circle mobility model, it fails to be useful for other mobility models. Therefore, how to put forward an analysis technique on the dynamic characteristic of Ad Hoc network topology, which could be used for all the mobility models which are supported in NS-2 tool, is an interesting issue to be solved.

This chapter firstly builds up a model for MANTs by using holonic multi-agent systems, then analyzes and summarizes Ad Hoc network mobility models, and puts forward a formalization description for mobility models. Secondly, an Ad Hoc network topology snapshots capturing method is presented, which could be used to obtain not only the network steady period and its duration, but also some other Ad Hoc network topology dynamic performance parameters, such as link connection ratio, topology varying ratio and topology lifetime, and so on. Through analyzing on its topology snapshots, the times of network topology in steady state or unsteady state during a certain time t could also be obtained statistically, as well as the durative time of network topology in the two states, which is the basis on the selection of NT measurement time. Thirdly, The fit hypothesis testing method is used to obtain not only the distribution of steady or non-steady period duration, but also the times distribution of steady or non-steady state in certain time t .

Moreover, the probability of the network topology invariable event could be predicated and that of the network topology variable event could be warned beforehand by adopting the Markov stochastic process theory. Furthermore, the experiential formula of the probability of the network topology invariable and variable events was deduced. At last, RWP mobility model is used as an example to verify all the methods above. The simulation result shows that the statistical analysis technique on Ad Hoc network topology dynamic characteristic not only is effective, but also has the universal attribute, which could be used in the analysis technique on Ad Hoc network topology dynamic characteristic under any mobility models.

Modeling Method for MANTs

In our view, MANTs are a self-organize or autonomous system if an ensemble rather than a collection of nodes coordinate with each other to form an entirely system that adapts to achieve a goal more efficiently. Regardless of any application domains, MANTs have the following characteristics from the viewpoint of organization under the consideration of the size constraint and constraint: (1) Single node can not achieve the systems goal. ( 2) Nodes must act together to achieve a sub-goal, and total nodes collaborate, even organize to achieve the systems goal more efficiently and accurately, on average. (3) Single node must change its internal state based on local stimuli, such as the states of other near nodes and its physical environment, Therefore, in large scale Ad Hoc networks, autonomous nodes require to some extent the capability to group and collaborate, even organize to achieve shared objectives.

The section first uses the idea of holonic multi-agent systems to establish a model for MANTs, then introduces the RIO diagram to analyze the roles of nodes during different periods of building up holonic architecture

A Holonic Model for MANTs

A holon is a self-similar structure composed of holons as sub-structures. The hierarchical structure composed of holons is called a holarchy. A holon can be seen, depending on the level of observation, either as an autonomous "atom" entity, or as an organization of holon [182~184] . If we consider MANT as a holon, specially in WSNs(Wireless Sensor Networks), we could say that the sink node could be considered as a super-holon from the viewpoint of the highest level. Furthermore, the super-holon is composed several sub-holons which are its neighbor nodes. In turn, we can consider the neighbor node as a holon composed of its own neighbor nodes. A holonic model of MANT could be depicted as in Figure 3-1.

Holon

Level n

Level n+! Level n+2 We describes the holonic model of MANT in detail according to the following six elements [START_REF] Yao Ye | A Holonic Model in Wireless Sensor Networks, IIH-MSP[END_REF] : holon structure, node architecture, communication, control and decision making, creation mechanism, environment, which are inspired by Sebastian [START_REF] Rodriguez | From analysis to design of holonic multi-agent systems: a framework, methodologiacal guidelines and applications[END_REF] . We also put forward a cluster based hybrid architecture which not only combines the advantages of both cluster and flat architecture, but also introduces multiple communication model

MANTs [START_REF] Yao Ye | A Cluster Based Hybrid Architecture for Wireless Sensor Networks[END_REF] . Furthermore, the hybrid architecture uses multicast to solve the problem of "broadcast blast", and adopts deployment of heterogeneous nodes to solve the problem of "hot spot". performance analysis results indicate that the hybrid architecture has the properties of scalability, distribution, long life-time and robustness.

A RIO modeling Approach

We takes an organizational approach, that is, Role-Interaction-Organizational (RIO)

model to analyze holonic model for MANTs above. In RIO model a role is defined as "an abstraction of the behaviour of an agent" [187~190] . Otherwise, in MANTs the role of each node has the following properties: (1) A node is specified as an active communicative and/or computational entity (namely an agent). ( 2) A node may play one or more roles and a role may be instantiated by one or more nodes. (3) The relationship between roles and nodes is dynamics. In other words, at any given time nodes may request to play new roles and quit roles that it is currently performing. The concept of interaction is defined in RIO model as how to link different roles in a way, and the third concept of RIO model is the organization that is an ensemble rather than collection of roles and their interactions [191~193] . In addition to its formal specification, RIO provides a graphical representation of organizations as in figure 3-3.

At the organizational level, we could only find one organization Holon, which contains four roles, noted Sense, Inter-mediator, and Aggregation. To distinguish the environment role we use dashed lines in the RIO diagram. If all the nodes, specially in WSNs, the sensor nodes receive the command from sink to complete a task, they will first play the role of Sense, that is, to measure the physical environment. If the furthest nodes has received the data from other node before transmitting its own original data, they will play another role(namely, Aggregation) except of Sense. The Aggregation role means that the sensor nodes will aggregate its own data and the data received from other sensor nodes into a new data, and transmit the result to its parent or its neighbor in order to reduce the length of data transmitted or the number of data in MANTs. If the furthest sensor nodes do not receive any data from other nodes before transmitting its original data, they will play only one role (namely, Sense). The nodes between orphan nodes and sink node, will play either three roles(namely, Sense, Aggregation, and Inter-mediator) or two roles(namely, Aggregation, and Inter-mediator ) in some application domains(i.e., object tracking). So call Inter-mediator role is that when nodes receive data from other nodes, they must make a decision how to find the next route. At the agent level we assign roles to agents. In fact nodes instantiate and organization (roles and interactions) when they exhibit behaviors defined by the organization's role and when they interact following the organization interactions [182] . We call an instance of an organization a cluster. A node may play one or more roles and a role may be instantiated by one or more nodes.

Actually a holon is a conceptual description of cluster which is the instantiation of a holon contrarily. Therefore, a holon is composed of many sub-clusters, that is, there is only one head but many sets in a holon. However, a sub-cluster is only made up of one head and one set. The nodes in a set are in the coequal position which are managed by its head and communicate with each other directly. Nevertheless, the nodes in different sub-clusters only communicate indirectly with the help of its head as a coordinator.

Because the nodes in the same set could communicate directly, therefore, the heads at higher level could collaborate with each other that will provide a chance to implement indirect communication between different clusters. now in the state of inactive, which will be awaken by its head, whereas Member means that the sensor nodes are now in the state of active. In order to describe simple, we consider that MANTs are now in steady state during these time.

The literature [184] also describes the deployment model, radio model and self-organization scheme for WSNs in detail. The literature [185] brings forth a location scheme for MANTs in support of data collection, and aggregation, which includes distance discretion, angle discretion, and location discretion. The document does not discuss these for the limit to its length.

Ad Hoc Network Mobility Model

The section first classifies the Ad Hoc network mobility models, then analyzes the mobile scene files of mobility models in NS-2 tool, and puts forward an Ad Hoc network mobility models formalization description method.

The Classification of Ad Hoc Network MM

The mobility of nodes, network topology dynamic characteristics and the self-organization is the difference of Ad Hoc network with other networks. In the Ad Hoc network simulation research, mobility model is used to descript the nodes mobile pattern, which uses mathematical method to simulate the mobile rule of nodes in practical scene [START_REF] Boleng | Metrics to enable adaptive protocols for mobile ad hoc networks[END_REF][START_REF] Xavier | Toward a mobility metric for comparable & reproducible results in Ad Hoc networks research[END_REF] . When the linear distance of two nodes is within the range of wireless communication, it is possible to establish a wireless link between each other [START_REF] Gerharz | Link stability in mobile wireless Ad hoc networks[END_REF] , therefore, the mobile rule of nodes will directly influent the connection state of wireless link. Now, many mobility models have been brought forward for different application, which could be classified as four classes.

MM based on independent entity

The mobile nodes move independently and are not correlative with other nodes in this case, such as Random Waypoint (RWP), Random Walk(RW),Random Direction(RDM), and so on. In RWP mobility model, the initial position of nodes is supposed to accord with even distribution. The recent research results

show that with the time going by, the probability of nodes in RWP mobility model appearing in middle mobile area is bigger than that in edge area, which is also called as Border Effect or Density Wave phenomenon [157~160] . Noteworthy the average velocity of nodes will become smaller and smaller with time varies. RW mobility model was initially put forward to simulate the stochastic motion of particles, which is also called as Brown motion. In practice, when the pause time of nodes is set as 0s, RWP could be changed as RW. The nodes in RD mobility model need not choose the next destination randomly, they choose an angle from (0°, 360°] as its next mobile direction randomly. When the node arrives at the edge of mobile area, they pause a little time, and then repeat the above mobile pattern. Therefore, RD mobility model could solve the Density Wave problem in RWP.

MM based on the constrained entity

The mobile nodes have a certain autonomous, only are limited on scene range in the mobile process in this case, such as City Section(CS)、Manhattan, and so on. All the nodes are required to move towards the destination in a certain mobile rule, that is, the city street route in CS and Manhattan.

Cluster MM without reference point All the nodes are composed of a cluster and mobile nodes as its member according to a certain rule, such as Column (CM) [START_REF] Sanchez | Mobility models[END_REF] and Freeway, and so on. In CM, all the nodes are required to form a column and move in a certain direction. However, in Freeway, all the mobile nodes are deployed on the different roadways in the freeway. The nodes on different roadway comprises of the clusters, each cluster moves with its direction and acceleration.

Cluster MM with reference point One node is the reference one, the rest of other nodes move around the reference point in this case, such as Pursue Mobility(PM) [START_REF] Lin | Mobility Models for Ad Hoc Network Simulation[END_REF] , Reference Point Group Mobility(RPGM) [START_REF] Ng | Reference region group mobility model for ad hoc networks[END_REF] and Nomadic Community Mobility(NCM) [START_REF] Lin | Mobility Models for Ad Hoc Network Simulation[END_REF] , and so on. For example, Mobile nodes in a cluster chase a certain mobile node which is considered as the reference point according to a certain rule in PM mobility model. In this case, one node in a cluster is defined as the lead one or reference point, the rest of other nodes keep a certain distance from the reference point, and move around the point at low velocity. However, all the nodes compose a cluster, and move from one place to anther as a whole.

In conclusion, the mobility model is a simple and abstract mathematic description for the real mobile scene to simulate the rule of nodes' mobility in Ad Hoc network, which could evaluate the influence of node' mobility on the performance of Ad Hoc network. … …

Scene File Analysis of MM

Formalization of Mobility Model

In the scene file of NS-2, after mobile nodes have chosen the initial position at time 0.0s, they should also need to choose the next position and velocity at different time according to their mathematical model. In order to describe simply, some terms are defined as the follows.

Definition 3-1 Choice time is the time when the mobile node has the chance to choose its next position or velocity.

In Cartesian planar reference frame, the position of mobile nodes could be denoted as the formula 3-1.

( , ) , , ,

y x d d D i j i j i j = (3-1)
Where , x d i j and , y d i j denote the position coordination x and y of node i at choice time j . In practical application, the destination position could be extended from Cartesian planar reference frame to the three one. The current position of node i at time j could be denoted as the formula 3-2.

( , ) , , ,

y x C c c i j i j i j = (3-2) Where { , } , , ,
y x v v v i j i j i j =
denotes the velocity choice that node i choose at choice time j , and , , ,

y x v v
i j i j denote the x and y vector of , v i j in Cartesian planar reference frame respectively. Definition 3-2 Choice cycle is the period from choice time j to 1 j+ , which is denoted as the choice cycle j .

In choice cycle j , the mobile nodes follow the two movement rules: (1) At choice time j , 0 ,

v i j = or , , C D i j i j =
indicates that node i keeps immobile during choice cycle

j . (2) if 0 , v i j ≠ and , , C D i j i j ≠
are all satisfied, it means that node i will move from current position , C i j to destination position , D i j at the speed of , v i j during choice cycle j . Therefore, In Ad Hoc network, mobility model could be denoted as ( , )

V P , where V denotes the node set , P the choice set at different choice time and is denoted as the following formula.

{ } , , p i j i V j N ∈ ∈
Where , p i j is the choice state of node i at choice time j , which is defined as the definition 3-3.

P i j i n i i i i N = ∈ (3-3) Where ( 0) n n>
is the sum of all choice time in the simulation. For example, ,0 p i denotes the choice state of node i at the first choice time. In mobility model, the node i chooses the next position and velocity independently at different choice time j . However, the current position at choice time j and its next destination position have a certain relativity, which is called as the position relativity as the formula 3-4. , , 1

C D i j i j = + if && ! 0 , , , C v D i j i j i j ≠ = , , 1 C C i j i j = + if 0 , v i j = (3-4)
If the time between choice time j and 1 j + is denoted as ε , the relativity between velocity and position could be denoted as the formula 3-5.

Where , x v i j and , y v i j could be computed according to the velocity , v i j and current position , C i j and destination position , D i j at choice time j according to the formula 3-6.

For any little time slice ( ) , , , 1

t t ε Δ Δ ≤ , if
x x x c c v i j i j i j ε = + × + , , , 1
y y y c c v i j i j i j ε = + × + (3-5) , , 1 sin(arc ( )) , , , , 1
y y c c i j i j x tg v v i j i j x x c c i j i j - + = × - + , , 1 cos(arc ( )) , , , , 1
y y c c i j i j y tg v v i j i j x x c c i j i j - + = × - + (3-6)

Ad Hoc Network Topology Snapshot Capturing Method

Firstly, the parameters, , , , v D i j i j and ,0 C i at time 0.0s could be obtained according to the scene file of mobility model in NS-2. Moreover, the current position ( ! 0, ) , j j n C i j = ≤ at different choice time j could be computed according to the position relativity formula 3-4. secondly, the velocity relativity formula 3-5 is used to verify the correctness of , C i j computed, and the choice set { } , ,

p i j i V j N ∈ ∈
of node i at different choice time .

Position Snapshots of Nodes Capturing Method

In order to obtain the Ad Hoc network topology snapshots, the position of all mobile nodes at different snapshot time should be computed firstly. The relationship between snapshot time and choice time is as the figure 3-1.

0 t 1 t 2 t 3 t 4 t 5 t 6 t ( ) i ( ) k Figure 3-6

relationship between snapshot time and choice time

In figure 3456, if the superposition occurs on the snapshot time i and choice time 1 t , the current position , 1 C j t of node j at choice time 1 t is considered as the current position at snapshot time i . Otherwise, if the choice time k is within the choice cycle

) , , , 1 x x x t t c c v i j i j i j Δ = + × Δ + ( ) , , , 1
y y y t t c c v i j i j i j Δ = + × Δ + (3-7)
The line 1 means that the scene file ScenceFile is read to compute the choice set for all mobile nodes and store them in the bidirectional list List chooseInfo -. Line 2 denotes that snapshot times N is computed according to the simulation time T and snapshot time t Δ . Line 3 presents that the first position snapshot of mobile nodes is computed at time 0.0s and line 4 means to compute the rest of position snapshot N-1. Then the choice cycle is obtained according to snapshot time t from line 5 t0 7 and the position snapshot of mobile node

Ad Hoc Network Topology Snapshot Capturing Method

At snapshot time i the Euclidian distance between node j and other nodes ( \{ }) l l V j ∈ could be computed according to position snapshots of nodes, which is denoted as R . If R is less than the wireless communication overlay range r , then the state of link from node j to l is set as one, which means that there is a wireless link between the two nodes, otherwise as zero and means there is no wireless link. If all the mobile nodes run the algorithm at the each different snapshot, the Ad Hoc network topology snapshot could be obtained. This algorithm is described as the follow in detail.

If the Euclidian distance between node i and j is less than the wireless communication overlay range r , then the link , l i j between them is established at line 2. the snapshot time of Ad Hoc network topology snapshot is computed at line 3. The Ad Hoc network topology snapshot ( ) { , , }

G t V L t =
at snapshot time t is stored at line 4.

Some dynamic characteristic parameters of mobility model could be obtained through analyzing on the Ad Hoc network topology snapshots, such as link varying number, link meaning duration time, node connection ratio, node inactive degree, node relative velocity, link connection ratio and topology varying ratio, and so on. All the performance parameters are defined as the table 3-2. End For 3.

t k t = ×Δ 4. Store ( ) { , , } G t V L t = k + + ; End For Return: ( ) { , , } G t V L t =

Algorithm Complexity Analysis

The temporal complexity of Ad Hoc network topology snapshot capturing algorithm mainly includes two parts, one is that of the position snapshot capturing method, the other is that of the topology snapshot capturing method. If the nodes number is N , simulation time and snapshot time are T and t Δ respectively, then the temporal complexity of position snapshot capturing method could be expressed as the follow.

The temporal complexity of topology snapshot capturing method is as the following formula.

Therefore, the sum of the Ad Hoc network topology snapshots capturing algorithm temporal complexity is as the formula 3-8.

The spatial complexity of this algorithm mainly includes three parts, one is the choice state storage space, the other is the position snapshots, and the last is topology snapshots.

If the meaning number of the choice time for each node is M , the spacial complexity of choice state is (

) O M N ×
, and that of the position snapshots is as the following formula.

When the topology snapshots are stored, since the algorithm in this chapter does not storage the whole Ad Hoc network topology architecture, only storages the link state information between nodes. For example, if the node i and j are within each other's communication range, the link state between node i and j is denoted as one, otherwise as zero. Therefore, the spatial complexity of link state storage is as the follow.

Therefore, the spatial complexity of Ad Hoc network topology snapshots capturing

( ) T O N t × Δ 2 ( ) T O N t × Δ ( ) T O N t × Δ + 2 ( ) T O N t × Δ 2 ( ) T O N t = × Δ (3-8) ( ) T O N t × Δ 2 ( ) T O N t × Δ
algorithm could be denoted as the formula 3-9.

From the formula 3-8 and 3-9, it clearly shows that the temporal and spatial complexity of Ad Hoc network topology snapshots increase with the simulation time and mobile nodes number, and decrease with the snapshot time.

Simulation

Simulation Experiment

Simulation experiment adopts the NS-2 tool to establish the RW and RWP mobile scenes, which are denoted as the scene 1 and scene 2 respectively. In simulation scen1, the number of mobile nodes is 50, pause time is 0.0s, and the maximum velocity of nodes is 20m/s, the simulation time and scene range are 900s and 1200 m *1200 m rectangle respectively. The wireless communication overlay range is a circularity with its radius equal to 250m. In the simulation scene 2, the pause time is 5.0s, the rest of other parameters are the same as that in simulation scene 1. In the two simulation scenes, the snapshots are set as 1.0s and 0.5s respectively, the three dynamic characteristic of mobility model, such as link connection ratio, topology varying ratio and Ad Hoc network topology lifetime, are shown as the figure 3-7 and 3-3. From the figure 34567we could see that during the period from 0.0s to 200.0s simulation time, the link connection ratio decreases from 4% to 2%. However, during the period from 200.0s to 900.0s simulation time, the link connection ratio varies like a sinusoid curve approximatively. In practice, the topology duration time is equal to topology varying ratio in this section, since when topology varying ratio is not equal to zero, the value of y coordinate is set as 0.02, otherwise set as zero, which means the consecutive two network topology architectures do not vary, that is, Ad Hoc network topology is in its steady state. It shows that through analyzing on the topology duration time from 300.0s to 900.0s that when snapshot time is 1.0s, there are 30 periods during which the topology duration time is more than 5.0s, the maximum duration time is 8.0s. When snapshot time is 0.5s, there are 54 periods during which the topology duration time is more than 5.0s, and the maximum duration time is 10.5s. From the figure 345678we can see that during the period from 0.0s to 250.0s simulation time, the link connection ratio decreases from its maximum value from 98% to 10%.

( ) O M N × + ( ) T O N t × Δ + 2 ( ) T O N t × Δ 2 ( ) T O M N N t = × + × Δ (3-9)
However, during the period from 250.0s to 900.0s simulation time, the link connection ratio varies about 10%. It also shows that through analyzing on the topology duration time from 300.0s to 900.0s that when snapshot time is 1.0s, there are 41 periods during which the topology duration time is more than 5.0s, the maximum duration time is 11.0s.

When snapshot time is 0.5s, there are 66 periods during which the topology duration time is more than 5.0s, and the maximum duration time is 15.0s At last, some Ad Hoc network topology dynamic characteristic parameters at different snapshot time for different simulation scenes are showed as the table 3-3 through analyzing on the Ad Hoc network topology snapshots. The simulation results show that the relative velocity of mobile nodes in scene 2 is 13 multiple of that in scene 1. The node inactive degree is 0 in scene 1, but 47.7 in scene 2, which shows that the steady degree of network topology in scene 2 is better than that in scene 1. Specially, the node connection ratio in scene 2 is 6.7 multiple of that in scene 1, and link duration time in scene 2 is 2.5 multiple of that in scene 1. However, the link varying number in scene 2 is 2.6 multiple of that in scene 1. We could use the figure 3-2 and 3-3 to explain the phenomena above. In the figure 3-2, during the time from 0.0s to 200.0s, the link connection ratio decreases from 4% to 2% shows that there is a few connection links at the start simulation time, then small part connection links states changed from connection to disconnection in scene 1 with time going by. However, in the figure 3-3, during the time from 0.0s to 250.0s, the link connection ratio decreases from its maximum value from 98% to 10% shows that there are lots of connection links at the start simulation time in scene 2, and then many connection links states changed from its connection to disconnection with time going by

Result Analysis and Problem Discussion

Result analysis The simulation results in figure 34567show that if the Ad Hoc network measurement could be finished with 10.0s, it is measurable for the Ad Hoc network, that is, there exists Ad Hoc network measurement occasion. Of course, the snapshot time will also influence the precision of statistical data result. For example, the number of topology duration time being no less than 5.0s at snapshot time equal to 0.5s is more than that at snapshot time equal to 1.0s in scene 1. Furthermore, if the snapshot time is set as 1.0s and 0.5s respectively, the minimum value of Ad Hoc network duration time (or topology lifetime) also is 1.0s and 0.5s respectively. Therefore, at a certain snapshot time, Ad Hoc network in scene 1 has its minimum topology lifetime and it is equal to the snapshot time according to the simulation data. In practice, there is some errors which is brought to by the snapshot time for the minimum topology lifetime. In order to verify the conclusion above, we set the snapshot time as 0.25s again, the statistical data of topology snapshots shows that the minimum topology lifetime is 0.25s too. Therefore, in simulation scene 1, although there exists Ad Hoc network minimum value of topology lifetime, it maybe no more than 0.25s, which could be verified through the data from the figure 3-8 too.

At last, the computing cost of Ad Hoc network topology snapshot capturing algorithm and statistical method of its dynamic characteristic parameter are analyzed respectively.

The computing cost is defined as the runtime of program concerned. The detection and identification algorithms were run on the same computer with 512M RAM and 2.66GHz

CPU. The data of algorithm computing cost is shown as table 3-4. The data in table 3-4 shows that in different scenes and at different snapshot time, the computing cost is no more than 1.5s. Although the computing cost at snapshot time equal to 0.5s is more than that at snapshot time equal to 1.0s, but its increment is no more than 312ms. Specially, the increment of computing cost does not increase more with the snapshot time decreasing, which shows that the algorithm has a certain real time characteristic. [START_REF] Blough | A Statistical Analysis of the Long-Run Node Spatial Distribution in Mobile Ad Hoc Networks[END_REF] .

Problem discussion

Ad Hoc Network Topology Dynamic Characteristic

In order to research on the Ad Hoc network topology dynamic characteristic, the chapter firstly uses the Ad Hoc network topology snapshots capturing method to obtain some dynamic characteristic performance of mobility model, such as Freeway, Manhattan

and RPGM, and so on. The link connection ratio, topology varying ratio and topology duration time(or topology lifetime) curves are shown as the figure 3-9(a)~(d).

Topology Statistical Characteristic

This section sets RWP as an example, and uses mathematical statistical theory to analyze the Ad Hoc network topology dynamic characteristics. There are all four stochastic variables are mainly studied, that is, the times of steady or non-steady state appearing in certain time t, which are discrete, and the duration of steady or non-steady period, which are all continuous variables.

Discrete Stochastic Variable

In a certain time t, the number of steady state and non-steady one are all discrete stochastic variable denoted as X and Y respectively. Through analyzing on these two stochastic variable, we could obtain the frequency of the steady sate (or non-steady period) appearing in a certain time. The data of RWP in scene 2 was used as an example to obtain the probability distribution chart of the number of steady period appearing in 10 t= s, and According to the hypothesis 0 H , the number of steady period accords with the following distribution formula.

{ } ! k P X k e k γ γ - = = ( 0,1, 2, ...) k =
Where γ is the distribution parameter unknown, its maximum likelihood estimate value could be denoted as follows according to the formula 3-10 and the simulation data. , that is, we could count the number of steady state once per 10 seconds. Through processing the simulation data of RWP in scene 2, statistical data is obtained as in the table 3-5. According to analysis on the data in table 3-5, where m i is obtained from the statistical samples, and p i is computed from the poison distribution function in theory under the condition that λ equal to 4.14. Then, we could compute the value of the test statistic variable , V , according to formula 3-11.

2 2 9 ( ) ( ) 7.40 1 1 r n n p p m m i i i i V n n p p i i i i - - = = = ∑ ∑ = = (3-11)
Under the condition that if significance level α is equal to 0.05, and free degree r equal to 9, we could get the inequality relation between the theoretical value of 2 χ distribution function and its statistical one as the follow. could also be verified as the method above. When the statistical time is equal to different values, such as 15s, 20s, and so on, or when we choose other different mobility models, such as RW, Freeway, Manhattan and RPGM, we could also safely arrive at the conclusion that the number of steady or non-steady state appearing in a certain time also accords with the poison distribution with different parameter λ as the table 3-7. The paper does not discuss these for the limit to its length.

Continuous Stochastic Variable

When Ad Hoc network topology is in the steady state, the duration of which is called as steady duration time, otherwise, called as non-steady duration time. Because the steady or non-steady duration time is a continuous stochastic variable, and denoted as Z and W respectively, the statistical analysis method on the data about steady duration time is different from that on the number of steady state appearing in a certain time. Therefore, we divide the analysis method into three steps as the followings.

Step1: Coordinate the data.

At first, we should coordinate the data about steady duration time, such as { , ,..., } 1 2 z z z n , in the sort ascending order as ... 1 2 z z z n ≤ ≤ ≤ , where n is the scale size of data sample about steady duration time, 1 z is the minimal value of the steady duration time, and z n the maximal one.

Step2: Discrete the zone [0, ] z n . Secondly, the topology duration time zone [0, ] z n is discrete to l smaller zones according to the scale size of data sample about steady duration time n. In general, if 100 n≥ , the value of l belongs to the zone [10,20] ; when n is equal to 50 or so, l usually is set as 5 or 6 according to some experiences in 2 χ fit hypothesis testing problem.

Since in Fig. 1(d),

332 100 n= ≥
comes into existence, we set the value of l as 10. The case of small zones about the measurement sample is processed and analyzed as the table 3-6. Step3: Analyze on the steady duration time

According to the data of RWP in scene 2 in the anterior three lines in table 3-6, the probability distribution of steady and non-steady duration time is shown as the Fig. 3-12 and Fig. 3-13 respectively. If we connect the middle points in the upper side line of the each rectangle to construct a fold line, when n and l are big enough, the fold line is approximate to the PDF curve of the stochastic variable, the steady or non-steady duration time, according to the probability statistic theory as in Fig. 3-12 and 3-13. The larger is the scale size of data sample, the steady duration time, the smaller is the each zone, and PDF curve of the steady duration time of Ad Hoc network topology is more precise. According to the curve in figure 3-12, we could also likely arrive at the inconclusive hypothesis that the steady duration time approximately accords with the exponential distribution. Next, we will use 2 χ fit hypothesis testing method to verify this hypothesis. At first, we put forward the following hypothesis test problem as above in section 3.8.1. Where λ is the parameter unknown, its maximum likelihood estimate value could be denoted as the formula 3-12.

1 1 0.584 1 n Z n z i i λ ∧ = = = ∑ = (3-12)
According to analysis on the data in table 3-6, the value of the test statistic variable V could be obtained as the formula 3-13.

r n n p p m m i i i i V n n p p i i i i - - ∑ ∑ = = = = = (3-13)
Under the condition that if significance level α is equal to 0.05, and free degree r equal to 9, we could get the inequality relation between the theoretical value of 2 χ distribution function and its statistical one as the following formula. This inequality relation means that the test statistic variable V does not belong to the rejection range, therefore, we have to refuse the hypothesis 1 H , and accept another hypothesis 0 H . It is reasonable for us to believe that the steady duration time accords with the exponential distribution with the 0.584 λ= , when we choose RWP mobility model in a certain mobile scene as our research objective. At the same time, we could also prove that the non-steady duration time in the whole simulation time accords with the exponential distribution with 1.276 λ= . In the same way, when the statistical time is equal to different values, such as 15s, 20s, and so on, or when we choose other different mobility models, such as RW, Freeway, Manhattan and RPGM, we could also safely arrive at the conclusion that the steady or non-steady duration time accords with the exponential distribution with different parameter λ as the table 3-7. The paper does not discuss these for the limit to its length.

Topology Dynamic Characteristic Analysis

Markov stochastic process could be classified as three classes. The first one is the Markov chain with discrete time and state, the second is the Markov stochastic process with continuous time and discrete state, and the third is the one with continuous time and state. For the Ad Hoc network topology snapshots capturing method, if the snap time is big enough, although the two successive snapshots have the same topology architecture, this dose not guarantee that topology dose not change during the two snapshots time interval. Under this condition, the Markov chain theory with discrete time and state could be used to analyze the Ad Hoc network topology dynamic characteristics. Otherwise, if the snapshot time is small enough to guarantee that not only the two successive snapshots have the same topology architecture, but also the topology dose not change during the two snapshots time interval, then many discrete steady or non-steady states could be united as steady or non-steady period respectively, and Markov stochastic process theory with continuous time and discrete state could be used to analyze the Ad Hoc network topology dynamic characteristics.

Discrete Markov Chain Statistical Analysis

During the Ad Hoc network topology dynamically changes period, there exists two states i and j ( , , {0,1 }

i j E E ∈ =
),where 0 and 1 denotes the steady or non-steady state respectively. p ij expresses the probability when the current state of Ad Hoc network from 0 t to 0 m t t + ×Δ for the limitation of the Markov chain.

Continuous Markov Chain Statistical Analysis

In order to solve the limitation of Markov chain with discrete time and state, the Markov stochastic process with discrete state and continuous time could be used to analyze the Ad Hoc network topology dynamic characteristics through decreasing the snapshot time t Δ and increasing the number of snapshots. The following results could be obtained according to section 3.8.

(1) If the state of Ad Hoc network topology enters i , the duration of state i accords with exponent distribution with parameter i γ .

(

) 2
t > + Δ > = > Δ (3-16) ( | , ,..., ) ( | ) 0 1 0 1 P j P j i i i i X X X X X X t t n n t t t t n n = = = = = = = (3-17) ( | ) ( ) P j i X X P s t s ij t = = = +Δ Δ (3-18)
Formula 3-18 indicates that the conditional shift probability of the stochastic process about Ad Hoc network topology changing dynamically is independent of start time s , which is only correlative with time slice t Δ , that is, the stochastic process of Ad Hoc network topology has the homogeneous attribution.

Definition 4-1

The homogeneous shift probability of stochastic process about Ad Hoc network topology changing dynamically, { , 0} t X t ≥ , is corresponding to a shift probability matrix, ( ) {( ( ))}, 0 expresses the speed of Ad Hoc network topology changing from state i to j as the formula 3-23.

P
(

( ) 0 t P ij ≥ and ( ) 1

P ij t j E ∑ = ∈ (3-19) (2) ( ) ( ) ( ) t s t s P P P ij ik kj k E + = ∑ ∈ (3-20) ( ) ( ( ) | ( ) ) P ii t P X t t i X t i Δ = +Δ = = 1 ( ) t o t i γ = -Δ + Δ (3-21) ( ) ( ( ) | ( ) ) P ij t P X t t j X t i Δ = +Δ = = ( ( )) t o t P ij i γ = Δ + Δ ( ) t o t P ij i γ = Δ + Δ (3-22) ij γ
in formula 3-23 is also called as shift speed of state changing from i to j , and matrix

( ) Q ij γ =
is called as state shift intensity matrix, which satisfied the following rule.

According to the analysis results in section 3, if the Ad Hoc network topology is in steady state (denoted as "0")now, after a steady duration time in this state, it transfers to the non-steady state (denoted as "1"), and the non-steady duration time accords with the exponential distribution with parameter 1 λ . However, the steady duration time accords with the same distribution with parameter 2 λ . Therefore, the density matrix of this Markov stochastic process could be denoted as the following Q .

Theorem 1 The sum of each row in the density matrix Q equals to zero.

Proof:

Supposed that 0 and 1 denotes steady and non-steady state respectively. The duration of Ad Hoc network topology steady and non-steady duration time accords with exponent distribution with parameter 1 λ and 2 λ .

( ) , t P i j denotes the probability of the state about Ad Hoc network topology changing from state i to j after time t . According to the exponent distribution, the following formula could be obtained.

If ( ) , t P i j

is successive at time t equal to zero, for any state i and j ( ,

{0, 1 } i j E ∈ =
),

There exists the following formula.

According to the formula ( ) 0,1 t P Δ , ( ) 1,0 t P Δ , and the exponent distribution of Ad Hoc network topology steady and non-steady duration time, each element of the density matrix Q could be obtained as the following formula.

( ) ' (0) lim 0

P ij t P ij ij t t γ = = + → (3-23) 0 ii γ ≤ , 0( , , ) i j E i j ij γ ≥ ∈ ≠ (3-24) ( ) ( ) 0,1 1 t t o t P λ Δ = Δ + Δ ( ) ( ) 1,0 2 t t o t P λ Δ = Δ + Δ lim 0( ), 1( ) ( ) 0 i j or i j P ij t t = ≠ = = →
Next, The sum of the first row in the density matrix Q is expressed as the following formula which equals to zero according to conditional probability in complete set. In the same way , that of the second row in the density matrix Q also equals to zero. Therefore, the theorem 2 is proved.

According to the forward differential equation of continuous time Markov stochastic process [START_REF] Haifeng | Research on Intelligent Vehicle Development[END_REF][START_REF] Abouzeid | Comprehensive performance analysis of a tcp session over a wireless fading link with queueing[END_REF] , ' ( ) ( )

t P t Q P =
, the following differential equations 3-25 could be obtained.

According to the probability theory, there exists the following restriction condition as the formula 3-26. Through implementing the integral operation on the both sides of the formula 3-27, the following formula could be obtained.

If we use the equation

λ λ λ λ λ λ Δ - - Δ - -Δ + Δ = = = = - Δ Δ Δ + + + Δ → Δ → Δ → Δ - Δ + Δ - = = = Δ Δ + + Δ → Δ → Δ - Δ + Δ - = = = Δ Δ + + Δ → Δ → = + Δ → ( ) ( ) (0) [1 ( )]
-Δ + Δ Δ - - Δ - = = = - Δ Δ Δ + + Δ → Δ → ( ) (0)) ( ( ) (0)
The constant C is determined according to the initial condition as the formula 3-29.

Then the formula 3-31~3-34 are obtained according to the formula 3-25, 3-26, 3-28, 3-29 and 3-30. Formula 3-31 means that if the Ad Hoc network topology is in the steady state (denoted as 0) now, after time t, the probability that it is still in steady state is ( ) (3-34) Formula 3-32 presents that if the Ad Hoc network topology is in the non-steady state (denoted as 1)now, after time t, the probability that it is still in non-steady state is ( ) 11 t p . Therefore, formula 3-31 and 3-32 are called as the Ad Hoc network topology steady and non-steady duration time forecast experimental formula respectively. Next, we use the concept of opposite events in probability theory to obtain warning experimental formal 3-33 and 3-34.

00 t p . ' ( ) ( ) ( ) 2 1 2 00 00 p p t t λ λ λ = - + (3-27) ' ( ) ( ) ( ) 1 2 [ 1 2 ] 2 00 dt dt t C p e e λ λ λ λ λ - + + ∫ ∫ = × + ∫ ( ) ( ) 1 2 [ 1 2 ] 2 t t dt C e e λ λ λ λ λ -+ + = × + ∫ ( ) 1 2 2 ( ) 1 2 [ ] 1 2 t t e C e λ λ λ λ λ λ λ + -+ = + + ( ) 1 2 2 ( ) 1 2 [ ] 1 2 t t e C e λ λ λ λ λ λ λ + -+ = + + 2 ( ) 1 2 1 2 t C e λ λ λ λ λ -+ = + + (3-28) (0) (0) 1, (0) (0) 0 00 11 01 10 p p p p = = = = (3-29) 1 1 2 C λ λ λ = + (3-30) 1 ( ) 1 2 ( ) ( ) 1 2 00 1 2 t e t p λ λ λ λ λ λ -+ = + + (3-31) 1 ( ) 1 2 ( ) ( ) 1 2 11 1 2 t p t e λ λ λ λ λ λ -+ = + + (3-32) 1 ( ) ( ) 1 1 2 ( ) (1
Formula 3-33 means that if the Ad Hoc network topology is in the steady state now, after time t, the probability that its state varies as non-steady one is ( ) 01 t p . While formula 3-34 presents that if the Ad Hoc network topology is in the non-steady state now, after time t, the probability that its state varies as steady one is The parameter 1 λ and 2 λ are set as 1.276 and 0.584 respectively in the formula 3-31~3-34, the experimental probability about state keeping invariable and varying with the time t according to the formulas concerned is considered as its theoretical value, and its statistical data as its real value. The computing method about maximum error and meaning error between them is shown as the table 3-8. 3-9 shows that there is some errors between the theoretical value and its real one, the former maximum error is 0.120, but the latter one is 0.095, and the meaning error is not more than 0.075, which verifies the effectiveness of the formula 3-31~3-34

Result Analysis and Discussion

As shown in figure 3-14~3-16, we could safely arrive at the following conclusions: (1) When P01(t) and P11(t) increase, P00 and P10 decrease with the increment of parameter If the number of steady period appearing in a certain time is larger than two, with the increment of parameter 1 λ in passion distribution, the number of steady period appearing will becomes smaller according to the progression theory. That is, the probability of Ad Hoc network topology keeping steady period will decrease. Therefore, P01(t) and P11(t) increase, while P00(t) and P10(t) decrease with the increment of 1 λ in a certain time. If steady duration time is lager than 1.0s, with the increment of parameter 2 λ in exponential distribution, the steady duration time will become larger according to the progression theory. that is, the probability of Ad Hoc network topology keeping steady period will increase. Therefore, When P01(t) and P11(t) decrease, P00(t) and P10(t) increase with the increment of parameter 2 λ in a certain time. With the increment of time t, the probability of Ad Hoc network topology keeping its former state(i.e., steady state or non-steady state) will become smaller. Therefore, P01(t) and P10(t) increase, while P00(t) In a practical Ad Hoc network application system, we could use GPS or other position location technology to obtain the position of mobile nodes in any moment, instead of analyzing on the scene file. Next we could use the computing and analysis method in the document above to obtain the dynamic characteristic of Ad Hoc network topology, which could also be used for performance evaluation and optimization of Ad Hoc network

Probability P00 P01 P11 P10 1 λ ↑ ↓ ↑ ↑ ↓ 2 λ ↑ ↑ ↓ ↓ ↑ t ↑ ↓ ↑ ↓ ↑

Conclusion

This chapter brings forth an Ad Hoc network topology snapshot capturing method to obtain the network topology architecture at any moment under any mobility models in Ad Hoc network. Through analysis on the data about the link topology snapshots, we could arrive on the following conclusion: (1) The dynamic varying process of Ad Hoc network topology architecture is actually a discrete state and continuous time Markov stochastic one. The discrete state means that there exists two states in Ad Hoc network topology, one is steady state, the other is non-steady one. Furthermore, the consecutive time slices during which the Ad Hoc network topology stays in steady state compose the steady period, otherwise, it composes the non-steady period. The continuous time means that the steady or non-steady duration time is a continuous time stochastic variable. (2) The Ad Hoc network topology steady period and non-steady period appear in turn periodically.

Moreover, the number of steady or non-steady state appearing in a certain time follows the Poisson distribution, and the steady or non-steady duration time follows the exponential distribution. Since the statistical analysis method in the document could be used for all the mobility models supported by NS-2 tool, it has the attribute of universality.

However, all data and results in this paper comes from the simulation results, which are not tested in the practical Ad Hoc network application environment.

Chapter 4 Topology Dynamic Characteristic Analysis Technique Based on Measurement Sample

Introduction

If the scene files of Ad Hoc network mobility model could not be obtained in advance, it is not possible to use topology snapshot capturing method to find Ad Hoc network topology steady period in NT network measurement. Although some position techniques such as GPS could be used to obtain the position of any mobile node to solve the precondition in NT, theirs costs are high.

In order to solve the above problem, some mobile nodes are chosen as source nodes or leaf ones according to different application requirements, then an active measurement technique is adopted. The characteristic information of Ad Hoc network topology steady period is obtained from the end-to-end network measurement sample to find its steady period and topology architecture. Therefore, this chapter mainly focuses on how to identify the Ad Hoc network topology steady period and its architecture when it is not possible to obtain the position of any mobile node in advance.

Ad Hoc Network Steady Period Characteristic

Problem

Ad Hoc network topology steady period detection is one of the preconditions for link performance inference based on NT technique. The authors of [170] bring forth a statistical analysis method to obtain the Ad Hoc network path durative time. This method uses the mobile scene file in NS-2 to obtain all the link information of all paths per second. For the same source and leaf nodes, the path duration time distribution is obtained by judging whether the fore-and-aft two paths information is the same. But it is difficult to apply the method for practical Ad Hoc networks. Since the literature [170] only used RPGM、Freeway and Manhattan mobility model to verify the methods above, specially its' velocity and direction choice occurs only once per second, which is not flexible and universal. Moreover, the path durative time obtained by this method could not identify accurately the steady or non-steady period of Ad Hoc networks.

Steady Period Characteristic Information

In order to solve the problem above, this chapter brings forth an Ad Hoc network topology steady period detection method. Firstly, the path delay time is obtained by adopting the end-to-end measurement. Secondly, the path performance characteristic is analyzed when Ad Hoc network topology is steady and its routing algorithm converges.

Thirdly, the path delay variety being near to zero is regarded as the judgment basis to detect the Ad Hoc network topology steady and non-steady period. The method is described in detail as follow. Probes The probe architecture is constituted on the basis of its transmission relativity to decide its sending and receiving mode. The probe transmission relativity is that the communication characteristic of two packets with small interval on the same link is similar. The chapter adopts single source measurement model and active measurement method, that is, it chooses one mobile node as the root one or source node which has the chance to send probes, and other ones as the leaves which users are interested with. If the Ad Hoc network communication protocol supports multicast mode, the probe could adopts the multi-cast ones, where source nodes and leaf nodes all belong to only one multicast group. Otherwise, the packet strips are adopted to simulate the multicast ones in order to preserve a certain communication relativity between probes as shown in the figure 2-2(d). For the packet strips, the packet communication relativity denotes that the communication characteristic of different packets is similar in one packet strip. In Figure 2-2(d), the interval of different strips t is far more than that of different neighboring packets in one strip t Δ , and the number of packets in one strip is just equal to that of leaf nodes.

Ad Hoc network measurement model

Measurement sample collecting and cleanout

The leaf nodes are in charge of measurement sample collecting in network measurement model. The information of measurement sample mainly includes the number of source and receiver node, the time of sending and receiving, packet types, the number of probe and packet, TTL, and so on. In Ad Hoc networks performance measurement, some natural network communication packets will also be collected this is called the background flow. Therefore, before the analysis on the measurement sample, it should be cleaned firstly to clean out the irrespective measurement sample. At last, the path delay is obtained as Delay = Tr-Ts,

where Tr represents the probe receiving time, and Ts the sending time.

Topology steady or non-steady period detection In general, if Ad Hoc network topology is in the steady period and each mobile node has enough buffer, the path delay commonly keeps on a certain value and its variety is near to zero without reference to network communication protocol, such as reactive or active ones. Firstly, the measurement time is divided into many small slots averagely. Next, the path delay of each time slot is computed, if its meaning variety is close to zero, the topology in the small slot could be considered as in steady state, otherwise non-steady state. At last, The Ad Hoc network topology steady and non-steady period are obtained by uniting each small time slot.

For example, in small time slot t i , the meaning delay time and its variety of any path delay between source node and any leaf node ( )

j j R ∈
are , d i j and , D i j respectively as described by the formulas 4-1 and 4-2.

, 1 ( ) ( ) , , , 1
n i j k d x i j i j n i j k ∑ = = (4-1) , 1 ( ) | | , , , , 1
n i j k x d D i j i j i j n i j k ∑ = - = (4-2)
Where ( ) , k x i j denotes the path delay between source node and leaf node j in t i small time slot for the probe k , and , n i j presents the number of probes received by leaf node j . Then the path meaning delay variety between source node and leaf node j in small time slot t i is denoted as the formula 4-3.

1 ( | |) , 1 N N R d D i j i N j = = ∑ = (4-3) If ( 0) ε ε > is used to denote a threshold which satisfies 1 D D i i ε ε < ∧ < +
, the consecutive time slot t i and 1 t i+ could be united as 2 t i , where 2 denotes that there are two slots having been united. In order to avoid that there are too large variety of meaning delay for time slot t i and 1 t i+ to bring much error, it is necessary to compute the path delay in having united time slot 2 t i as 2 D i again as the formula 4-4.

, 1 , , 1 ,

1 1 1 ( ) ( ) ( | | ) 2 , , , 1 , , 1 , 1 1 1 n n n n N i j i j i j i j k k x x D i i j i j N n n n n i j i j i j i j j k k + + + + ∑ = - ∑ ∑ + + + + = = = (4-4) If 2 D i satisfies 2 D i ε <
, which means that it is successful to unite the time slot t i and 1 t i+ as 2 t i . At the same time, it shows that Ad Hoc network topology is in its steady period, Otherwise in non-steady period. As in figure 4-1, the time slots 1~5, 9~11, 18~21 t t t t t t are united unsuccessfully; it shows that in the period of [ 1, 5], [ 9, 11], [ 18, 21] t t t t t t

, Ad Hoc network topology is in non-steady period. In the same way, the time slots 1~5, 9~11, 18~21 t t t t t t are united successfully, thus in the period of [START_REF] Yao Ye | A Link Loss Rate Inference Method for Ad Hoc Networks Based on End-to-End Measurement[END_REF]8], [ 12,[START_REF] Wu | A new multi-channel MAC Protocol with on demand channel assignment for mobile ad hoc networks[END_REF], [START_REF] Lindgren | Future Directions in Ad hoc Networking Research[END_REF][START_REF] Perkins | Highly dynamic destination-sequenced distance vector routing (DSDV) for mobile computers[END_REF] t t t t t t

, Ad Hoc network topology is in steady period.

Therefore, Ad Hoc network topology steady or non-steady period could be detected; the algorithm is described as the follows.

Input: path delay

1 i i = + ; (b) If ( 1 D D i i ε ε < ∧ > + ) t i .state = 0; 1 t i+ .state = 1; (c) If ( 1 D D i i ε ε > ∧ < + ) t i .state = 1; 1 t i+ .state = 0; (d) If ( 1 D D i i ε ε > ∧ > + )
Unite the t i and

Algorithm Complexity Analysis

In Ad Hoc network measurement model, if the number of leaf nodes is N , that of time slots is M , and that of measurement times occurring in slot t i is k , the temporal complexity of computing meaning delay time , d i j and its variety , D i j between source node and leaf node ( )

j j R ∈ are all ( ) k N Ο × .
The meaning variety of path delay from source node to leaf node j (i.e., D i ) is ( )

N Ο . The temporal complexity of computing 2 D i is ( 2 ) N k N N Ο + × +
when judging whether the two uniting consecutive time slots t i and 1 t i+ is successful. Therefore, the temporal complexity of detecting the steady or non-steady period in the two consecutive time slots t i and 1 t i+ is as the formula 4-5.

(

) k N k N N N k N N Ο × + × + + + × + (4 2 ) k N N = Ο × + ( ) k N = Ο × (4-5) 2
If the number of time slots is M , there are 1 Mtimes at most to unite the consecutive time slots. Therefore, the temporal complexity of detecting algorithm is (

) k N M Ο × × .
Spatial complexity is mainly determined by storage all the path delay from source node to any leaf nodes. Therefore, the spatial complexity of detecting algorithm is (

) k N M Ο × × .

Ad Hoc Network Topology Identification Method

Problem

In Ad Hoc networks, the wireless link state will change with time going by because of nodes mobility characteristic, which leads to the Ad Hoc network topology dynamic characteristic. Topology identification method mainly solves how to obtain the Ad Hoc network topology architecture by using the end to end network performance measurement sample when it is in steady period, which is one of the precondition for Ad Hoc network link performance inference based on NT technique. The reference [96] brings forth a network topology computing method. Firstly, it uses receiving state of the probe at leaf nodes to compute its similarity and judges whether the two leaf nodes have the brother relationship according to the similarity. Secondly, receiving state of its father node for the probe is also computed according to that of its child nodes. At last, the brother relationship between the father node and the other nodes is judged till users satisfy.

The precondition of the method above is that there exists the partial order relationship for receiving state of brother nodes for the probes. This case may exist in the wired network with solid infrastructure using cable as the transmission medium. However, since almost all wide area networks use optical fiber as its transmission medium with low loss rate, the partial order is not obvious nowadays. Moreover, if all the mobile nodes have enough buffers to avoid network congestion, some networks adopt QoS warning mechanism, which will destroy the partial order relationship of probe receiving state. In addition, if network congestion occurs frequently between father node and the wireless link between its child nodes, it will bring much error to use the partial order relationship of probe receiving state to identify the Ad Hoc network topology architecture. In the tree measurement model, there exists much similarity for packet transmission characteristic from the source node to the brother nodes except that of the last link. The chapter adopts the cluster method to identify Ad Hoc network topology architecture in steady period.

Network Topology Identification

The path delay time measurement sample is obtained by using end to end network measurement and uses the TTL to identify the degree of different leaf nodes in network measurement model. For the leaf nodes belonged to the same degree i , the similarity of path delay is used to judge if the nodes have brother relationship. If there exists a relationship, then a virtual father node is created, and the path delay time from source node to the virtual father node is equal to the minimum value of that from source node to all its child nodes. For all the nodes and the new father nodes at 1 i-degree implement the same operation as that at i degree till the Ad Hoc network topology architecture is identified. The method is described as the follow in detail. x i = shows that node i successfully receives the probe in the k measurement times. Otherwise k x i is equal to one. Then the hamming distance of the probe receiving state between node i and j is denoted as ,

Probe disposal

H i j . !( ) , 1
N k k x x H i j i j k = ⊗ ∑ = (4-6)
Then the similarity of probe receiving state between node i and j is denoted as

, SH i j . , , H i j SH i j N = (4-7)
For a threshold ( 0) ε ε > , if

, SH i j ε > is satisfied then there exists the brother relationship between node i and j and its virtual father node is ( ) f i . Then the probe receiving state of the virtual father node ( ) f i is computed as the formula 4-8.

(

( ) k k k k x x x x i j f i f j = = ∨ (4-8) )
Similarity of delay time Path delay k d i is computed according to the information of the probe having been received in k measurement times by leaf node i . The path delay difference between node i and j is

( | |) , , k k k k d d d d i j i j i j = -
. After N times measurement, the similarity of path delay meaning value between node i and j could be denoted as the formula 4-9.

1 , , 1
N k sd d i j i j N k = ∑ = (4-9)
Network topology identification The leaf nodes are divided into different layers according to theirs degree. At the maximal layer, one of the leaf nodes is chosen as a cluster center 1 w . Then, the similarity of delay from any other leaf node i to this cluster center is computed as , 1

sd i w . If , 1
sd i w is more than a threshold ρ , the leaf node i is also chosen as another new cluster center. The rest may be deduced by analogy, all m cluster centers are produced and denoted as ( ), 1,2,...,

l i m w i =
, where l is the iteration number. The parameter ji λ is computed according to the formula 4-10, if node j belongs to the cluster i , then

1 ji λ = , Otherwise 0 ji λ = . 1, min{ }(1 ) , , ( ) ( ) 0, if z m sd sd j j w w i l z l ji λ ⎧ = ≤ ≤ ⎪ = ⎨ ⎪ ⎩ (4-10)
The cluster centers ( ) w i l is modified according to the formula 4-11.

{ } ( 1) ( ) k w d i l w i l = +
, and

( ) 1 ( 1) 1 1 N k k d d ji j w i l j k d w N i l ji j λ λ + ∑ = = + + ∑ = (4-11)
If the error between two iterative values for the same cluster center e as the formula 4-12 satisfies max e E < , then 1 l l = + , it is required to continue modifying the cluster centers ( )

w i l till it satisfies the user requirement, that is max max e E l l > ∨≥ . 2 || ( 1) ( )|| 1 k l l e w w i i i + - ∑ = = (4-12)
For each cluster center ( 1) i m w i ≤ ≤ , the meaning similarity of probe receiving state between node j and the cluster center w i is computed according to the formula 4-13.

, SH j w i = | | , 1 w i SH j i i ∑ = (4-13)
For each cluster center ( 1) i m w i ≤ ≤ , a virtual father node is produced and the path delay is the minimum from source node to its cluster center. The probe receiving state of the virtual father node is produced by the two nodes which have the maximum value of hamming distance according to the formula 4-8. All the nodes in a cluster are the child of its virtual father node and have the brother relationship, the rest nodes are the isolated one.

The degree of the virtual father node requires to be reduced by one, that is

1 d d = -.
All the nodes of 1 ddegree implement the same method above till the degree is two. Then, the network topology architecture is identified. The network topology identification algorithm based on cluster is described as follows.

Algorithm Complexity Analysis

The temporal complexity of topology architecture identification algorithm is mainly composed of four parts, probe packet process, cluster center choice, ( ) w i l modification and the similarity of probe receiving state computing. For example, if the maximum degree of tree measurement model is h and in the i degree the leaf nodes number is r i , the sum of all leaf nodes is r r i =∑ . If the measurement times and cluster centers are N and m respectively, then the temporal complexity of probe packet process is ( ) O r .

In the process of cluster center choice the temporal complexity is ((

) ) O N m r i +
, that of ( )

w i l modification is ( ) O m l r i × ×
, where l is the modification number, and that of computing the similarity of probe receiving state is ( ( 1)) O m r r i i × -. Therefore, the sum of temporal complexity is as the formula 4-8.

Input: Ad Hoc network node set V , Measurement number N ,The probe receiving state of

leaf nodes { }, \ 0, k i V s k N x i ∈ ≤ ,Path delay time from source node 0 s to leaf node i { }, \ 0, k i V s k N d i ∈ ≤ , Link set ∅ L = 。 Output: ( , ) T = V L Process: For (each h , max h H ≤ ) Select the first leaf node in h degree as core member 1 w , 1 C w ∈ (a) For (Each other leaf nodes i , \ 0 i V s ∈ ) Calculate the , sd i w l , C w l ∈ ; If ( , 1 sd i w ρ ≤ ) i Cw l ∈ If (all , 1 sd i w ρ > , C w l ∈ ) i C ∈ End For (b) For (each , max l l l ≤ ) If( min{ }( ) , , ( ) ( )
( ) C sd sd w j j z l w w i l z l == ∈ 1 ji λ = Else 0 ji λ = ; Calculate e ; If ( max max e E l l > ∧≤ ) 1 l l = + End For (c) For (each node j , j Cw l ∈ ) If , SH j w i ξ > , select j as an orphan node j O ∈ ;
( ) f j j = and ( )

f j V ∈ ; ( ( ), ) f j j ∪ L= L End for (d) For (each Cw l ) ( )( ) Cw l m f u u = ∀ ∈ and m V ∈ ; ( , )( ) m u u Cw l ∪ ∀ ∈ L= L
End for End For Return:

( , )

T = V L ( ) (( ) ( 1)) 2 h O r O N m m m r r r r i i i i i + + + × + × - ∑ = ( ) (( ) ( 1)) 2 h O r O N m m r r r i i i i = + + + × - ∑ = ( ) (( ) ( 1)) O r O N m r m r r = + + + × - 2 ( ) O N r mr = × + (4-8)
The spatial complexity of the algorithm is mainly comprised of two parts, one is to storage the path delay, the other is to storage the probe receiving state, and they have the same spatial complexity as ( )

O N r × .
Therefore, the sum of spatial complexity is ( )

O N r × .

Simulation

Simulation Experiment

Simulation experiment adopts NS-2 tool to build up simulation scene. The number of mobile nodes is 60 and 120 respectively. in RWP mobility model, the pause time is 5.0s

and the maximum velocity of nodes is 10.0m/s and simulation time is 900.0s. The mobile area is constrained in a 1000 1000 s s × rectangle region. In view of the probes' temporal correlativity, many UDP packets are used to compose the packet strip. In each packet strip, the interval of each packet is 1.0ms, and that of each packet strip is 50.0ms. The background flow is UDP packets which are sent by source node 0, and the size of each packet is 1024 Byte and the sending speed is 80Packets/s.

In order to evaluate the effectiveness of the detecting and topology identification algorithm, the conception, such as effective steady period and similarity of steady period are defined. The effective steady period is that the range of inferred steady period is within the real one. The similarity of steady period is the ratio of the number of effective steady period to that of the real one. In order to avoid counting the number repeatedly, many effective steady periods in a real one is only counted as one. In order to evaluate the effectiveness of the topology detecting algorithm, the chapter adopts the topology similarity as its evaluation parameter [START_REF] Yongjun | Wireless Sensor Network Measurment based on NT technique[END_REF] . The network topology similarity is the ratio of the number of nodes which have been identified correctly to the sum of all mobile nodes in Ad Hoc network. In network topology identification algorithm, the nodes which have been identified have the following characteristic: if the real network topology is denoted as the T =(V,L), and the inferred one is

' ' ' ( , ) V T L = , for ' ' v V ∈ ∀ , if the set of father node set ' ) ( f v
and its child nodes set ' ) ( c v accords with the ( ) f v and ( ) c v where v V ∈ is satisfied, the we consider that the node v is identified in network topology detection.

The chapter firstly adopts the Ad Hoc network topology snapshots capturing method of section 3.3 to obtain its steady and non-steady period as the theoretical value. The figure 4-1(a) shows the relationship between inferred network topology similarity with the number of leaf nodes number after 150 times measurement for 60 mobile nodes.

Simulation results make clear that the Ad Hoc network topology similarity increases with its leaf nodes number. When the leaf nodes number is 24, the detection method could infer Ad Hoc network steady period correctly. The figure 4-1(b) shows the same relationship after 150 times measurement for 120 mobile nodes. Simulation results show that when the leaf nodes number is 48, the detection method could infer Ad Hoc network steady period correctly. Specifically, the former similarity is more than that of the latter, because with the increment of Ad Hoc network scale, the higher stochastic characteristic of mobile nodes results in the stronger network topology dynamic characteristic. The number of leaf nodes Topology steady period similarity degree (%) (b) 120 mobile nodes Figure 4-1 The relationship between topology similarity with the number of leaf nodes Under the condition of having obtained the Ad Hoc network topology steady period, one of which has the long time could be chosen as the measurement window time. The path delay measurement sample in measurement window time is the input of network topology identification algorithm. The chapter considers the Ad Hoc network in steady period obtained by network topology snapshots method as its theoretical value. The figure 4-2 shows the relationship between inferred network topology similarity with the measurement times when mobile nodes number is 60 and 120 respectively, and chosen leaf nodes number is 16 and 32 respectively. Simulation results show that the network topology similarity increases with the measurement times. Because more path performance measurement sample is obtained with the increment of measurement times, it improves the precision of network topology identification. However, it decreases with the increment of leaf nodes number. Because with the increment of leaf nodes number, the higher path performance stochastic characteristic for the network scale increases the difficulty of network topology identification, which certainly decreases the inferred network topology similarity. The number of measurement rounds Topology similarity degree (%)

Computing Cost

The detection and identification algorithms were run on the same computer with 512M RAM and 2.66GHz CPU. The data about algorithm computing cost is as table 4-1 and 4-2

The data of table 4-1 shows that the computing cost of detection algorithm is concerned with the network scale, leaf nodes number and measurement times. Under the same network scale, it increases with leaf nodes number and measurement times. If leaf nodes number is kept un-variable, it increases with network scale and measurement times, but the increment is not more, which proves that the algorithm has a certain real time characteristic. The data of table 4-2 shows that in measurement window time, the algorithm above could use no more than 5.0s to identify the Ad Hoc network topology when the mobile nodes number is 32. The computing cost is concerned with only the leaf nodes number, but also the measurement times. With the network scale increasing, since the measurement times increases when the algorithm is convergent, it needs to process more measurement sample and lead to high computing cost. For the same network scale, its run time increases by exponential rule with the leaf nodes number.

Conclusion

Since Ad Hoc network topology keeps invariable during its steady period, when the routing algorithm is convergent, the path performance of Ad Hoc network is near to be steady. The chapter uses the variety of path delay being near to zero as the judgment base to detect the Ad Hoc network topology steady and un-steady period. Secondly, the steady period which has long time is chosen as the measurement window time. Thirdly, the end to end active network measurement is implemented and measurement samples are collected. At last, the Ad Hoc network topology architecture in measurement window time is inferred by using the path delay similarity. Simulation results show that the detection algorithm could effectively detect the Ad Hoc network topology steady and un-steady period when the position of mobile nodes could not be known ahead.

Specifically, it flexible and has generality features. Moreover, it is independent of network communication protocol. Topology identification algorithm can effectively identify the Ad Hoc network topology architecture in measurement window time when the packet receiving partial order relationship does not occur or is not clear. Of course, How to find and use more Ad Hoc network characteristic in steady period to improve the precision of detection algorithm is required to be investigated more deeply next.

Chapter 5 Link Performance Inference Based on Linear Analysis Model

Introduction

Ad Hoc networks, as self-organized systems, can implement self-configuration, self-management and self-maintenance during the period of theirs deployment, application and death. There are no international standards for communication protocol in the different layers yet. Specially, for the network topology dynamic characteristic, it is difficult to adopt traditional network interior measurement technique for link performance of Ad Hoc networks. Since there is a dependency on time effectiveness for network measurement, that is, the measurement of time only reflects the network performance at this certain time, there is no application value for the Ad Hoc network performance at next time, since network topology has changed. Otherwise, if the Ad Hoc network topology does not change during the measurement period, link performance inference results could truly reflect the network performance during measurement period. This chapter firstly analyzes the inequality relation between link and path loss rate, and brings forward a light weight Ad Hoc networks link performance inference method based on linear analysis model. Secondly, the steady period of Ad Hoc network topology is found by using link topology snapshot capturing method, and the long time of steady period is selected as the end to end measurement window time. Besides, single source measurement method is used to implement end to end measurement. Thirdly, Ad Hoc network link performance inference problem is transformed in "how to a solve the solution space of non-homogenous linear equations according to measurement sample and linear analysis model". At last, the statistical property of Ad Hoc network link performance is obtained through discrete the solution space according to constraint condition. Simulation results show that this method not only is effective, but also has little computing time, which is adaptable for Ad Hoc network performance measurement.

Measurement Model

Network measurement technique could be classified as the single and multiply sources measurement according to the number of source nodes which could send the probes.

There is only one source node to send probes in single source measurement, the measurement model exhibits a tree architecture as illustrated in figure 2-1(a). In figure 2-1(a), the node 0 is a source node. It is the only one that has the chance to send probes, and node 4,5,6, and 7 are all receivers. However, there are more than one source node in multiply sources measurement, as it is that case in the measurement model of figure 2-1(b), where node 0 and i are the source nodes and node 4,5,6 and 7 are the receivers.

The two measurement models in this chapter are all called as the pseudo tree model as defined by definition 5-1.

Definition 5-1 A pseudo tree model is an acyclic graph where the number of nodes which incoming degree is equal to 0, is no less than one.

This model is denoted as

, , , TP S M R L =< > , where (| | 1) S S ≥
denotes the node set with the number of incoming degree equal to 0, which is also called as source node set, M denotes the middle node set with number of incoming degree or out-degree all not equal to 0, R denotes the leaf node set with the number of out-degree equal to 0, and L is the link set of the pseudo tree model.

Without loss of generality, in pseudo tree model, L ij denotes the link from node i to j . There is more than one child nodes in TP , the child node set is denoted as

( ) d k ( ( ) { |( , ) }( ) d k i k i L i M i R = ∈ ∈ ∨∈ ). if i M R ∀ ∈ ∪
is satisfied, and there is only one father node for each node i , the father node set is denoted as ( ) f i . According to the chapter 2.3.1, if n is a plus integer, then there exists the formula 1 ( ) ( )

i f i f = and 1 ( ) ( ( )) n n i f i f f - = . If ( ) n k i f =
is satisfied, k is called as the ancestor of node i . At the same time, node i is called as the offspring node of node k . The measurement model based on pseudo tree model has the properties described by the theorems 5-1, 5-2 and definition 5-2.

Theorem 5-1 when | | 1 S = is satisfied, a pseudo tree model TP is actually is a tree measurement one.

Proof (Contrary Evidence)

In a network measurement model based on pseudo tree, , , ,

TP S M R L =< >, if | | 1 S = is
satisfied, that is, the number of node with incoming degree equal to 0 is one, then the source node 0( 0 ) s s S ∈ could be regarded as the root node of pseudo tree.

Supposed that the pseudo tree model is not a tree network measurement model. When

, k k M R ∀ ∈ ∪ , , ( ) n i i k f ∃ = , ( ) f i =Φ , 0 i s ≠
is satisfied, then the ancestor node of node k , that is, node i could be regarded as another root node.

All the above shows that when

| | 1 S > is satisfied it is inconsistent with | | 1 S = .
Therefore, theorem 5-1 is proved.

Since the Ad Hoc network topology does not change during the measurement window time, it actually is a pseudo tree architecture, that is, , , ,

TP S M R L =< >.
It is difficult to infer the link performance through implementing network measurement on TP directly, since the temporal and spatial complexity will become more and more with the increment of problem scale. In practice, users care only about key links or mobile nodes performance, not all links and nodes. Therefore, a large TP could be decomposed into many sub-pseudo tree models, that is, , , ,

S TP M R L i i i i i =<
>, which have the property of orthogonality, and satisfies the following formula.

Where n is the number of sub-pseudo trees. In this case, it is enough to implement the network measurement on sub-pseudo trees which involve the key links and nodes which users care for. Since the measurement network scale is decreased, the complexity of inference algorithm is also reduced.

Definition 5-2 If TP i and TP j is two different sub-pseudo trees, and satisfies the formula (

)( ) S S S S R R R R i j j i i j j i ⊄ ∨ ⊄ ∧ ⊄ ∨ ⊄
, then they have the property of orthogonality.

Theorem 5-2 if , TP TP TP i j ∈ , then ,

k k S i ∃ ∈ or , m m R i ∃ ∈ ,which satisfies k S j ∉ or m R j ∉ Proof If ,
TP TP TP i j ∈ , then TP i and TP j have the property of orthogonality.

(1) if , k k S i ∀ ∈ and k S j ∈ , supposed that , m m R i ¬∃ ∈
exists, which satisfies m R j ∉ , then

S S R R i j i j ⊂ ⊂ ∧
. it shows that TP i and TP j have no property of orthogonality, which is inconsistent with the hypothesis in theorem 5-2.

(2) if , m m R j ∀ ∈ and m R i ∈ , supposed that , k k S i ¬∃ ∈ exists, which satisfies S S R R i j i j ⊂ ⊂ ∧
. It shows that TP i and TP j have no property of orthogonality, which is inconsistent with the hypothesis in theorem 5-2 too.

Combining (1) and (2), the theorem 5-2 is proved.

Network Performance Linear Analysis Model

The network performance analysis model mainly focuses on the relation between paths an links performance, which is the basis of NT technique. This chapter firstly unite the

1 n S S i i = = U , 1 n M M i i = = U , 1 n R R i i = = U , 1 n L L i i = = U
delay and loss rate analysis model to a uniform linear one through simply mathematical transformation, and then analyzes the inequality relation between path and link loss rate.

At last, the properties stating that the length of shared links among different sub-paths is longer and that the communication relativity between packets is higher, are theoretically proved.

Delay Analysis Model

According to the analysis result in 2.3.2, if path ( , )

Path i j has m different links, its end to end delay ( , ) d i j could be expressed as the formula 5-1.

In order to simplify the formula 5-1, the following sign is defined.

Then the formula 5-1 could be simplified as the following one.

If delay time of link k is denoted as ( ) d k , it actually is comprised of queue delay, process delay, transmission delay and propagation delay of link k . If ( , ) d i j is denoted as Y, and ( ) d k as X, the linear relation between Y and X could be denoted as the formula 5-2 when routing matrix A is known.

Where ε is measurement error, and A is the routing matrix. The row vector describes the different paths, and column vector the different links. The route matrix in figure 2-1(a)

and (b) could be denoted as the following A1 and A2, and formula 5-2 is called as the linear analysis model for delay in the chapter.

(

m d i j T T T T T T T t g t n g n p n q n q d n = + + + + + + ∑ = (5-1) , , , ) ( ) ,0 ,0 , , , , , 1
T t g d T T T T t n g n p n q n n d T q d m + = + + + = = ( , ) ( ) d i j d k ∑ = Y AX ε = + (5-2) 0 ,0 0 , , , , , , d T

Loss Rate Analysis Model

In pseudo tree model TP , supposed that the packet loss rule of mobile node accords with Bernoulli model. If the node k receiving a probe is denoted as

1 X k = , otherwise is 0 X k = ,
according to the property of pseudo tree and packet loss model, there exists the following rule about packet loss on the link:

1 1 ( ) X X k f k = ⇒ = and 0 0 ( ) X X f k k = ⇒ = . If
X k and ( ) X f k is denoted as X and Y respectively, then the packet loss analysis model could be expressed as

1 1 X Y = ⇒ = and 0 0 Y X = ⇒ = [99]
. That is, there exists the following truth, if the leaf node has received the probe successfully, all its ancestor nodes on this path must have received this probe successfully too. According to the logarithmic operation, there exists the following linear formula.

Where the successful transmission rate and loss are an opposite event, that is,

1 k k β α = - is satisfied. If ( ( , )) Lg S i j
is denote as Y, and

) (1 Lg k α -
as X, the linear model of loss rate could be denoted as Y X k

=∑

. Without loss of generality, when routing matrix A is known beforehand, the relation of Y and X could be expressed as the formula 5-3, which is 1 1 0 1 0 0 0

1 1 0 0 1 0 0 1 1 0 1 0 0 1 0 1 0 1 0 0 0 1 A ⎛ ⎞ ⎜ ⎟ ⎜ ⎟ = ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝ ⎠
, 1 1 0 0 1 0 0 0 1 1 0 0 0 1 0 0 1 0 1 0 0 0 1 0 2 1 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 1

A ⎛ ⎞ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ = ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ ( , ) S i j k β ∏ = (5-3) ( ( , )) ) ( Lg S i j Lg k β ∑ =
loss event only occurs on wireless link transmission. The source node 1 N sends m probes to leaf node N n , the loss event on path (i.e., ( ,) 1

Path N N n ) is expressed as : ( , ) { , ..., ,..., } 1 2 3 ,

Loss path N N x x x x n i n =
, where x i is the packet loss number on link l i . The number of successful receiving packets on node 1 N i-is denoted as 1 m i-, the packet loss rate of link l i and path ( , ) 1

Path N N n is denoted as the formula 5-4 and 5-5 respectively.

Thus it can be seen that although the packet loss number on link and path exists the linear relation, that is, the number loss packet is the sum of that on its links, the loss rate

) ( ( , ) ( , ) , 1 1
n m S i j S x y z w i j i j β = ∏ ∏ = = lim ( ) 1 1 x i i m i m i α = - →∞ - (5-4) ( ( , )) lim ( ) ( lim ) 1 2 2 n n x x i i path N N n m m m m i i α = = ∑ ∑ →∞ →∞ = = ( lim ( )) 1 2 1 n x i m i i m i ∑ ≤ →∞ - = - ( 1 m m i ≤ - ) 2
n i i α ∑ = =
(5-5)

does not accords with the same rule as the formula 5-5. Furthermore, the loss rate on path is no more than the sum of link loss rate. Besides, the packet loss rate on path and link accords with theorem 5-4 and 5-5.

Theorem 5-4 The difference of packet loss rate on path is no more than its link loss rate concerned , that is ( ( , )) ( ( ,

))) ( 1 1 path path f N N N N i i i α α α - ≤ , where ) ( 1 f N N i i = -. Proof (Theorem 5-4)
Theorem 5-4 is proved.

Theorem 5-5 packet loss rate on sub-path is not only no more than the sum of link loss rate, but also more than the difference of path loss rate, that is, which satisfies the following rule.

Proof (theorem 5-5)

(1) The right inequality proof

( ( ( , )) ( ( , ))) 1 1 f N path path N N N i i α α - 1 2 2 lim ( ) lim ( ) i i x x k k k k m m m m - ∑ ∑ = = = - →∞ →∞ lim x i m m = →∞ lim ( ) 1 1 x i m i m i ≤ - →∞ - i α = ( ( )) ( ( )) ( ( , )) ( lim ) 1, 1, 1 1 1 j x k path path path N N N N N N j i i j m k m k i k α α α - ≤ ≤ ∑ →∞ - = + - 1 ( ( , )) lim ( ) j x k k i path N N i j m i m i α ∑ = + = →∞ 1 2 lim ( ... ... ) x j x x x i i k m m m m i i i i m i + + = + + + + + →∞ 1 2 lim ( ) lim ( ) ... lim ( ) ... lim ( ) 1 1 1 1 1 1 x j x x x i i k m m m m i i k j m m m m i i k j + + ≤ + + + + + →∞ →∞ →∞ →∞ + - - + - - ( ... ... 1 1 m m m m i i k j ≥ ≥ ≥ ≥ ≥ + -) lim ( ) 1 1 1 j x k m k m k i k = ∑ →∞ - = + - 1 j k k i α ∑ = = +
(2) The left inequality proof Theorem 5-5 is proved.

In any path (i.e., ( , ) 1

path N N j ), N i is the ancestor node of N j , N k is the child node of N i and the ancestor node of N j .

( , ) 1

path N N i and ( , ) 1

path N N k are all the sub-path of ( , ) 1

path N N j , which are all different sub-paths for ( , ) 1

path N N j , and the length of ( , ) 1

path N N k is longer than that of ( , ) 1

path N N i , then the formula 5-6 is easy to be obtained according to theorem 5-3.

If ( ( , )) 1 d path N N i
denotes the delay of ( , ) 1

path N N i from node 1 N to N i , there exists the similar delay relation as the formula 5-7.

Deduction 5-1 If the different sub-paths have more longer length of shared links, the communication characteristic of them is more similar, that is, the loss rate and delay of them are more similar.

The deduction 5-1 is easy to be proved by using theorem 5-4 and formula 5-7.

According to the analysis above, when end to end loss rate is known, the minimum value of loss rate for any link l could be estimated by using theorem 5-4. the minimum and maximum values of loss rate for any sub-paths could be estimated according to theorem 5-5.

1 ( ( ) lim , j x k k i path N N i j m i m i α ∑ = + = →∞ 1 1 1 lim j i i x x k k x k k k i k m i m i + ∑ ∑ -∑ = =+ = = →∞ 1 1 1 lim ( ) j i i x x k k x k k k i k m m i m m + ∑ ∑ -∑ = =+ = ≥ ≥ →∞ 因为 1 1 1 lim lim j i i x x x k k k k k i k m m m m + ∑ ∑ ∑ = =+ = = - →∞ →∞ ( ( ))-( ( )) 1, 1, path path N N N N j i α α = ( ( , )) ( ( , )) ( ( , )) 1 1 1 path path path N N N N N N j k i α α α ≥ ≥ (5-6) ( ( , )) ( ( , )) ( ( , )) 1 1 1 d path d path d path N N N N N N j k i ≥ ≥
(5-7)

Inference Method Based on Linear Analysis

According to the above analysis result, network performance analysis model could be denoted as a linear relation:

Y AX ε = +
, where X denotes the link performance, and Y the path one, A is a routing matrix, and ε denotes measurement error which is omitted in this chapter. Link performance inference mainly solves the problem when A and Y are all known, how to obtain X, which practically is the process to solve the non-homogeneous linear equations according to linear algebra theory. Next the solution space, its discretion and the algorithm of link delay inference will be discussed on the condition of A being square traffic matrix and non-square traffic matrix.

Solution Space

Square Routing Matrix When the traffic matrix is a square one, the solution for the non-homogeneous linear equations is concerned with the rank of the routing matrix A .

On this condition, if the rank of traffic matrix A is full, there is a unique solution for the non-homogeneous linear equations, that is

1 X Y A - = × .
Otherwise, the problem of solution for the equation should be translated to that of a non-square traffic matrix problem. If the source node sends N probes to every leaf nodes respectively, then each link delay in Ad Hoc networks could be obtained at N different times. However, we do not care about the link delay at different time, but are concerned about the link delay probability distribution during measurement window time, which could be obtained through analyzing on the link delay statistically during measurement window time based on the discrete link delay time.

In practice, it is not possible to construct a square routing matrix A in Ad Hoc networks, since there is only one case: if there are N mobile nodes in Ad Hoc network, only one node is the source one, the other N-1 nodes are all leaf nodes. Under this condition, it is not necessary to use end to end measurement technology to infer the link delay, since there is only one step between the source node and leaf ones, we could obtain the link delay directly through measurement.

Non-square Traffic Matrix When the rank of routing matrix A is not full, or the routing matrix A is a non-square matrix, the problem could be translated to how to resolve a non-homogenous linear equations. We will discuss this problem from the following two sides.

(1) When the rank of the routing matrix A is not equal to that of its augmentation matrix (i.e., | AY ) , there is no solution for the non-homogenous linear equations.

(2) When the rank of the traffic matrix A is equal to that of its augmentation matrix, there is a solution space for the non-homogenous linear equations. If the routing matrix

A is denoted as Since the solution space S is comprised of infinite solutions, it is necessary to limit the scale of solution space. If the link l i ( L l i ∈ ) is shared by χ paths, the end-to-end performance of the χ paths is denoted as ( 1) j Y j χ ≤ ≤ , then the link l i performance(i.e., X i ) should satisfy the constraint condition as the formula 5-9.

Discretization Model of Solution Space

According to the constraint condition as formula 5-9, the performance of link l k could be denoted as the stochastic variable X k , which satisfies the relation as

0 min{ } X Y k j ≤ ≤
. The discretization model of solution space is to use discretization method for research link performance distribution, which use set {0, ,2 ,3 ,..., ,..., ,min{ ( 1)} q q q iq Bq j Y j χ ≤ ≤ to discretizee the link performance X k , where q denotes the discretization granularity as the figure 5-2.

0 q 2q 2 q iq 2 iq q - 2 iq q + iq 2 Bq q - iq ∞ Bq 0 q 2q 2 q iq 2 iq q - 2 iq q + iq 2 Bq q - iq ∞ Bq Figure 5-2 Solution space discretization In figure 5-2, [ , ) 2 2 q q iq iq - +
is denoted as iq and called as the i-th bin. That is, if the value of X k is between [ , ) 2 2 q q iq iq -+

, then the link performance could be discretized as

: 1 n r S X k i i i β η - ∑ = × + = (5-8) 0 m i n { ( 1 ) } j X Y i j χ ≤ ≤ ≤ ≤
(5-9)

iq . The discretization function ( , )

Discrete X q is called as the discretization model of solution space as the formula 5-10.

According to the discretization function ( , )

Discrete X q , when the value of bin is smaller, the solution space discretization value is more finer, and the link performance inference result is more precise, but the computing cost is more bigger. Therefore, there is a tradeoff between the computing cost and inference precise for the value of bin.

Performance Inference Based on Linear Analysis Model

The linear analysis model is a mathematical pattern which could directly reflect the relationship between path and link performance. The procedure of network performance inference based on linear analysis model is as the following three steps. (1) Ad Hoc network topology steady period is obtained statistically by using topology snapshots capturing method. In order to assure the correctness and effectiveness of network measurement, the longer time of steady period is chosen as the measurement window The link performance inference method based on linear analysis model is described as the following algorithm.

( , )

Discrete X q = 0 iq Bq [0, ) 2 q X i ∈ [ , ) 2 2 q q iq iq X i ∈ - + [ ,min{ (1 )) Bq j X Y i j χ ∈ ≤ ≤
(5-10)

Simulation

In order to verify the correctness and effectiveness of the link performance inference based on linear analysis model, NS-2 is used to simulate the Ad Hoc network scene. In the measurement window time, real link performance is computed statistically as the theoretical value, and link performance is inferred by using the algorithm above as the inference result. The difference between theory value and inference result is called as the inference error. At last, the computing cost of the algorithm above is discussed.

Simulation Experiment

There are 40 mobile nodes in the Ad Hoc network simulation scene, which adopts the RW mobility model. The mobile area was constrained in a 1000 1000

s s × rectangle region.
The maximum velocity of mobile node is 10.0m/s, and the simulation time is 900.0s. there is a 21.0s measurement window time from 816.5s to 837.5s according to the

5.

For (each

(1 ), i n r N K K i i ≤ ≤ - ∈ ) If ( [ , ) 2 2 k q q iq iq X - + ∈ ) iq X k = ; Count k X one time; End For End For 6. Calculate ] [ ) ( iq X P i k k = = α according to statistical results about k X Return: ] [ ) ( iq X P i k k = = α
analysis on the link topology snapshots. Since Ad Hoc network topology will stay invariable, some mobile nodes which the user is interested in will constitute a tree network measurement model as illustrated by figure 2-1(a). The node 0 is chosen as the source node which has the chance to send probes, and node 4,5,6 and 7 as the leaf node to receive the probes. In view of the probes' temporal correlativity, many UDP packets are used to constitute the probe pair. In each probe pair, the size of probe packet is 128Bytes, the interval of each packet is 1.0ms, and that of each probe pair is 20.0ms. The background flow are UDP packets sent by source node 0, and the size of each packet is 1024 Byte and the sending speed is 100Packets/s. The error model was adopted in the simulation to analyze three types of packet loss instances. The inference result by using linear analysis model in this chapter is compared with that of using partial order relationship for packet loss rate.

(1) The influencing of different link loss rate on inference result, when the link with big loss rate is distributed on different path. For example, the theoretical value of loss rate for link 2,5 and 6 are 0.03, 0.05 and 0.08 respectively, that is, when that of link loss rate is small, the inference result is showed as the figure 5-3(a). If the theoretical value of loss rate for link 2,5 and 6 are 0.10,0.20 and 0.30 respectively, that is, when that of loss rate is big, the inference result is shown as the figure 5-3(b). The figure 5-3 and 5-4 show that the inference result based on linear analysis model is better than that on partial order relationship. The inference errors of them are shown as the table 5-1. the former meaning error is 0.019, but the latter one is 0.033. The former maximum error average value is 0.030, the latter one is 0.057. The simulation scene is similar to that above about research on link loss rate, the theoretical value and inference result of link 1,2,3,4,5,6 and 7 delay time based on linear analysis model is shown as the figure 56, its meaning error is 1.39ms, and its maximum one is 1.60ms.

Computing Cost

In order to obtain the computing cost, the algorithm was run on the computer with 512M RAM and 2.66GHz CPU. Table 5-2 shows that the inference method based on linear analysis model could finish within 1.5 minutes for loss rate and delay in a measurement system model with 32 mobile nodes. Although the computing cost will increase with the network scale, it is not fast.

Result Analysis and Discussion

The simulation experiment results verify the effectiveness of link performance inference method based on linear analysis model, which is better than that based on partial order relationship, there are the following reasons accounting for this phenomenon.

In the tree measurement model as figure 2-1(a), the receiving state of any leaf node i and j which has the brother relationship is denoted as { } n x i and { } n x j respectively, where n is the measurement times. If the measurement number is

( ) k k n ≤
, the state of node i receiving the probe is denoted as 1 k

x i = , otherwise as 0 k x i = . If the probe receiving state of brother nodes , i j have been implemented, then that of its father node ( )

f j ( ( ) ( ) f j f k =
) will be obtained as the formula 5-9.

The rest may be deduced by analogy, if the probe receiving state of leaf node ( )

i i R ∈ is denoted as { } n
x i , according to the formula 5-9, that of any transferring node ( ) e e M ∈ could be obtained and denoted as { } n x e . Then the packet loss rate of any link l e (from node e to ( ) f e ) could be computed according to the formula 5-10.

(

( ) k k k k x x x x i j f i f j = = ∨ (5-9) ( ) ( ) e e f e α = )
the number of packet loss on link the sum of packets sent by node

(5-10)

In figure 2-1(a), if the node 4 and 5 do not all have received the probe, but node 6 and 7 receive, which shows that node 1 and 3 all have received the probe too. That is,

0) 1) 1) 1) ( ( ( ( 4 6 1 3 5 7 k k k k k k x x x x x x ∨ = ∧ ∨ = ⇒ = ∧ = .
Of course, there are two cases to explain the packet loss, one is that the packet is lost on link 2, the other is lost on link 4 and 5 at the same time. Thus it can be seen, there must exist some errors if the probe receiving state of father node 2 is obtained by implementing the operator as formula 5-9 on that of its child nodes 4 and 5. Therefore, the inference result by using partial order relation will bring much error in NT network performance measurement. This chapter brings forth a new inference method based on linear analysis model according to the relativity among no-homogenous linear equations, which could avoid the errors brought by using partial order relation. In the inference method based on linear analysis model, if the number of shared paths for one link is more, the relativity among the non-homogenous linear equations is stronger and precision of inference result is higher. In order to discuss the precision of inference result, the correlative degree is introduced to evaluate the intensity of this characteristic as the following CS. Theorem 5-6 The CS of a binary three is only related to its depth .

Proof (theorem 5-6)

If the depth of a binary tree is h , at the 1-th layer, there is only one node and it belongs to the 1 2 hdifferent paths. At the 2-th layer, there are two nodes, each one belonging to the 1 / 2 2 hdifferent paths. In the same way, at the i-th layer, there are

1 0) ( ) ( 1 ) ( ) k k n x x e f e k n k n x f e = ∧ = = ≤≤ = (1 )
( ) N l CS l L n ∑ = ∈ (5-11) ( ) N l CS l L n ∑ = ∈
Therefore, the theorem 5-6 is proved.

Deduction 5-2 the CS of a n-tree is only related to its depth (i.e., h ), and

( ) CS O h = when n h << is satisfied.
The spatial complexity of the inference method based on linear analysis model mainly focuses on the storage of routing matrix A . For a n-tree with its depth h , the storage space of routing matrix is

1 ( ) h h n n n - -×
, the spatial complexity of the algorithm is

( ) h SP O n = .
With the increment of network scale, the spatial complexity of the algorithm becomes high, so the algorithm only adapts to the link performance inference for the small scale network.

For a big scale of Ad Hoc network, a big problem could be decomposed to many small ones according to the idea of partition rule. Supposed that each element in vector X for the linear analysis model: Y AX = , the problem of NT measurement could be decomposed to many sub-problems. If S denotes the set of all sub-problems, for each sub-problem

( ) s s S ∈ , s s s Y A X =
could be obtained, where s X is the estimate and s A the routing matrix for sub-problems. Therefore, the algorithm above could provide the technique support with link performance inference for the big scale Ad Hoc network.

Conclusion

In Ad Hoc network link performance inference, since network measurement has time validity for Ad Hoc network topology dynamic characteristic, a light link performance inference method should be adopted. Firstly, the relation between path and link performance is analyzed. Moreover, that the performance of different paths is more similar when they have long shared links is proved in theory. Secondly, a link performance inference method was brought forth based on linear analysis model. Simulation result shows that this method is adaptable for small scale Ad Hoc network performance inference. For a big one, partition rule ideology could be adopted to decrease the scale of routing matrix to solve the problem.

1 0 1 1 1 1 1 2 1 / / ... / 2 2 2 2 2 2 2 2 2 2 2 h h h h h h - - - - - × + × + + × = - 1 1 / 2 2 2 0 2 2 h i h i i h - - × ∑ = = - 1 2 2 2 h h h - × = - / 2 h ≈ ( ) o h =

Chapter 6 Link Performance Inference Based on

Multi-objective Optimization

Introduction

In the linear analysis model, when the rank of routing matrix is equal to that of its augmented matrix, linear algebra theory could be used to obtain the solution space of the non-homogeneous linear equations, and furthermore to infer the network link performance.

However, there often exist measurement errors in practical network measurement, which will lead to ε not equal to zero in linear analysis model as Y AX ε = + . On this condition the rank of route matrix is often not equal to that of its augmented matrix, which will induce that there is no solution for the non-homogeneous linear equations and that one could not use linear algebra theory to infer network link performance. In order to solve this problem, in this document, link performance inference problem is transformed to a multi-objectives optimal one through a simple mathematical transformation for the non-homogeneous linear equations, and then the use of genetic algorithms allow to obtain a sub-optimal solution. Through the analysis of the sub-optimal solution statistically, the link performance probability distribution could be obtained too, and the sub-optimal solution which has the maximum value could be selected as the link performance inference result. Simulation result shows that this method could solve the problem of link performance inference when the rank of route matrix is not equal to that of its augmented matrix.

Multi-objective Optimal Problem

When x i ≤ , each equation in formula 6-1 could be changed to the multi-objective optimal problem as the formula 6-2.

( ) ( | ) R A R AY ≠ in linear analysis model, that is Y AX ε = + , ' Y is used to denote Y ε -,
When ( ) 0( )

x i m f i → ≤
is satisfied, the estimate ( ) i n x i ≤ could be obtained in formula 6-2. The least square method is generally used to solve the multi-objective optimal problem above as the formula 6-3.

Where ||.|| denotes the vector norm, For the extremum problem of a quadratic function, when

' ( ) { | , } n A A x x y y R ℜ = = ∀ ∈
, there exists the optimization * x , otherwise formula 6-3 has no optimization. Therefore, in a single source measurement model, the problem of least squares for linear fitting could be transformed into the minimum one with no constraint condition for a convex quadratic function as the following.

= + + + - = + + + - (6-2) 1 2 ' min ( ) || || 2 q x Ax y = - (6-3) 1 1 ' ' ' min ( ) 2 2

T T T T q x

Ax Ax y y y x A = -+ encoding of decision variables, the production of the initial population, the design of the fitness function, the genetic operators (selection operator, crossover operator, and mutation operator), and enactment of the parameter control [START_REF] Boleng | Metrics to enable adaptive protocols for mobile ad hoc networks[END_REF] .

Coding and Decoding

The code for decision variables is a conversion method that transforms the solution from its solution space to a search space. It changes the chromosome information from phenotype to genotype. The quality of decision variable code will directly influence the result of genetic operators. Supposing that the constraint condition of link l i performance is

[ , ] A B x i ∈
, A is usually equal to zero and B satisfies 0 min{ } B y i ≤ ≤ for loss rate and delay time, where y i denotes the performance of all paths which shares the same link l i . Gray code of decision variable is adopted in the chapter since it could solve the Hamming Cliff problem compared with traditional binary encoding. If the element of solution space, x i , which is often called as a chromosome and adopts Gray code with k length, there are 2 k different discrete solution, and the map relation between binary code and gray code is as the follow.

Where σ denotes the fixed step size and satisfies

Fitness Function

The fitness function is often used as a standard to judge whether an individual better fit over another one, the value of which will directly influence the probability of the 00000000...0000 00000000...0000 0 00000000...0001 00000000.

A A k B σ σ → =→ → =→ + → =→ + → = → Binary Code Gray Code 1 ( ) 2 1 2 1 k B A i x A b i k i - - = + × × ∑ - = (6-5)
individual's excellent gene being inherited to its offspring. The weight factor transform method is used in link performance inference, that is, weight factor i β is decided by the importance of each sub-objective function. The objective function in multi-objective optimal problem is a linear weighting sum of each sub-objective function as the formula 6-6.

Since each sub-objective function has the same importance in link performance inference, if the number of sub-objective function is m , the weight factor i β satisfies

1 ... 1 2 m m β β β = = = =
. Therefore, the adaptive function of genetic algorithm could be defined as the formula 6-7.

The individual disobeying constraint condition maybe be produced in initial population and genetic operator process, which is the void solution. At present, three methods are used to deal with the void solution.

(1) Rejection method, that is, the void solution will be discarded directly. The merit of this method is simple. However, the defect of which is that the algorithm is easy to turn into infinite loop for not finding viable solution easily, and not adapts to be used in complicated constraint condition.

(2) Amendatory method, which could change the void solution into a viable one, or design special genetic operator method for specific problem in order not to produce the void solution in genetic algorithm. Nevertheless, on the one hand, this method not only depends on specific problem, but also is difficult to design.

(3) Punishment function method. It decreases the probability of void solutions being inherited to its offspring through reducing its fitness value by using punishment function.

The punishment function not only accepts the void solution properly which could extend the search space in order to avoid infinite loop, but also it increases the probability of viable solution being inherited to its offspring so as to ensure the increment of excellent gene in offspring. Therefore, the punishment function method is used to deal with the constraint condition in this chapter. Therefore, the adaptive function having been modified is as the formula 6-8.

( ) ( ) 1 m f x x f i i i β = ∑ = (6-6) 1 1 ( ) 1 ( ) 1 ( ) 1 m m F x m f x x f i i i β + + = = + + ∑ = (6-7) ( ) ( ) ( ) F x F x p x = - (6-8)
Where the duple punishment function ( ) p x is used in formula 6-8 in order to improve the convergence rate in gene algorithm when the fitness value of inference results is not satisfied with the requirement of viable solution, and it is defined as the formula 6-9.

( )

( ), ( ) ( ), ( ) ( ) 0, ( ) ( ) F x F x c p x F x x F x c f i x F x c f i α η η ⎧ ≤ ⎪ ⎪ = > > ∪∀ ⎨ ⎪ ≤ > ∪ ⎪ ⎩ (6-9)
The individual in each generation of gene algorithm denotes a link performance inference result. If the fitness value of an individual does not meet with the precision requirement of collectivity, that is ( )

F x c

≤ , then let ( ) p x equal to ( ) F x , which means to discard the individual. Otherwise, if the fitness value of individual does not satisfy the precision requirement of each sub-objective function, that is ( )

( ) F x c f x i η > ∪ > , then let ( ) p x equal to ( ) F x
α so as to decrease its fitness value. Moreover, if the fitness value of an individual satisfies the precision requirement of collectivity as well as sub-objective function, then let ( ) p x equal to zero. Since the order of precision requirement is that of collectivity is more priority than that of sub-objective function, the punishment degree is

(1) (2) < , (1)
To satisfy the precision requirement of collectivity, but not of sub-objective function.

(2) Not satisfy the precision requirement of collectivity.

Initial Population

Generally speaking, the initial population should have diversity in order to obtain the optimal solution. Furthermore, if the individual accords with the uniform distribution, more patterns of individual will be produced, and the search efficiency will be improved greatly, which are important to obtain the whole convergence fast in gene algorithm.

Large numbers of satisfying experiment results show that if the scale of initial population is more, the randomness will affect the uniform distribution of individual more little [START_REF] Xavier | Toward a mobility metric for comparable & reproducible results in Ad Hoc networks research[END_REF][START_REF] Gerharz | Link stability in mobile wireless Ad hoc networks[END_REF] . Nevertheless, large scale initial population will lead to increasing the computing scale, which influences the performance of gene algorithm. In order to let individual distributes in the solution space more uniformly and obtain the diversity, the chapter adopts to adjust the small scale initial population. That is, it discards the repeating individual and regulates the probability of each gene appearing in a chromosome. The implementation approach is described in detail as the follow.

Step1:To produce the initial population randomly.

Step2:To compute the hamming distance , H i j between any two individual x i , x j . ( ) , , , 1

N x x H i j i k j k k ∑ = ⊕ = If H i ϑ
< is satisfied, then any one of the two individual will be discarded. Otherwise, they are all kept down.

Step3: To detect the constitution of a chromosome. If the proportion of zero appearing in a gene is more than 50%, then change part of zero to one in order to let its proportion equal to 50% or so. Otherwise, part of one in gene should be selected and changed into zero.

Step4: If the number of individual is less than the requirement of initial population, part of individual will be produced randomly and added to the population, then Go to Step2.

Step5: The initial population is finished.

Genetic Operator

Selection Operator To solve the problem of link performance inference based on multi-objective optimization, the selection operator is used to implement the natural selection operation for each individual so as to let the individual with higher fitness value have more probability to be inherited to its offspring. The traditional gene algorithm often adopts Roulette Wheel Selection, which is easy to lead the premature convergence and search slowness. Therefore, this chapter adopts prime reservation and competition selection policy to implement the selection operator. It inherits the optimal individual to its offspring, but eliminates the one with lower fitness value, and the implementation approach of which is described as follow in detail.

Step1: To arrange each individual x i based on fitness value ( ) F x i in descending order.

Step2: The random selection with no replacement is adopted for the individual which ranks the anterior 80% in descending order of fitness value. individual should be inherited to its offspring based on the descending order of fitness value too.

Crossover Operator The crossover operator requires that the valid pattern of gene could not be damaged and that of new individual will be produced more. The chapter adopts one point crossover method. Firstly, two chromosomes are selected at random from the population based on a certain probability P c . Secondly, one point in a chromosome is selected randomly as the crossover one, if the point is at the anterior of the chromosome, then the frontal part of the chromosome should be changed. Otherwise, the back one should be changed. In order to avoid inbreeding effect, when the hamming distance between two chromosomes is more than a threshold, they have the chance to implement the crossover operator, the algorithm is describes as the follow.

Mutation Operator The mutation operator could replace the old gene with the new one to produce the new chromosome architecture in order to improve the diversity of population, which could restrain the precocious maturation effect. At the same time, if mutation probability P m is more enough, the computing complexity will be augmented greatly. The chapter adopts an adaptive mutation operator. When the chromosome architecture of population tends to be the similar, the mutation probability P m could be increased to produce new gene pattern and avoid the precocious maturation effect, Otherwise it could be decreased. The hamming distance of individual between two generations is denoted as its similarity degree, and the average hamming distance of individual in t generation is defined as the formula 6-11 [START_REF] Wang Yue | Computing Vulnerability of Network Based on Genetic Algorithm[END_REF] , , ( ) 2

( 1)

H i j i j i j M H t M M ∑ ≠ ∧ ∈ = × × - (6-11)
Then the similarity of the t generation is defined as the formula 6-12.

( ) ( ) H t S t N = (6-12) Where N denotes the length of chromosome M. When ( )

S t

tends to zero, it indicates that the current generation has low similarity, which requires to decrease the mutation probability P m . Otherwise, the mutation probability P m should be increased properly.

Parameter Control

The different parameter control methods will directly influence the convergence of gene algorithm, which mainly comprises of the population scale M, the length of coding N, crossover probability P c and mutation probability P m [179,180] . The population scale should accords with the requirement for the special application or problem. If M is more large, although the search space will become large too, it will increase the computing complexity of gene algorithm. Otherwise, the gene algorithm will converge on a local optimal solution. Therefore, the value of M popularly is between 20 and 200. The length of coding N should take a tradeoff between solution precision and computing complexity.

The crossover probability P c is often used to control implementation probability of crossover operator, if it is more large, which will produce big generation gap and increase the search space. Otherwise, it will easily bring precociousness effect for the high similarity between the two generations. Therefore, the value of crossover probability P c often is between 0.4 and 0.99. In the same way, the value of mutation probability P m is usually between 0,0001 and 0.1.

Simulation Result

In link loss rate inference method, the objective function is defined as the reciprocal The packet successful transmission rate and link delay inference results based on multi-objective optimal method and linear analysis model is shown as the table 6-2 respectively. There is a certain error between the inference results based on genetic algorithm and its actual value. The maximal absolute error and mean error of link delay reach 3.85ms and 2.50ms respectively, and that of link loss rate are 2.89% and 1.97%.

The two errors are all more than that of the link performance inference method based on linear analysis model.

Result Analysis

There are many factors which could influence the genetic algorithm precision, such as initial population selection, the design of genetic operators and iteration condition.

O L N M L M M L T M L T M L T N O N M M M T M T M T L N

Convergence Analysis

Since the three genetic operators, such as selection, crossover and mutation operator, are all implemented independently, the new population producing is interrelated with its fore generation and genetic operators concerned. Rudolph G has proved that the simple genetic algorithm based on excellence holding mechanism will converge on 1(or 100%) [START_REF] Rudolph | Convergence analysis of canonical genetic algorithms[END_REF] . Therefore, the genetic algorithm in this chapter has the same convergence as the simple one. Next, the accumulation of excellent gene in its offspring generation will be analyzed.

H i Φ
, the crossover probability is P c , then the genetic probability of pattern H i based on single point crossover could be denoted as the formula 6-18. Therefore, after excellent pattern is operated by selection, crossover and mutation operator, the mean excellent gene in its offspring is as the formula 6-20.

×Φ ⎢ ⎥ × Γ - ∑ = × × Γ × - × ⎢ ⎥ Ψ ∑ ⎣ ⎦ ( ) 1 ( ) ( ) ( , ) ( ) (1 ) (1 ) ( ) Y F H P H c i i P m t H H H i i i m N F H i i ×Φ ⎢ ⎥ × Γ ∑ = × × Γ × - × - ⎢ ⎥ Ψ ∑ ⎣ ⎦ (6-20)
The iterative formula 6-20 shows that the longer the chromosome of individual is, the smaller its distance is, the more the excellent gene in its offspring is, and the higher the fitness value of individual is. Specifically the excellent gene is increased exponentially, which accords with results that pattern theorem describes which is the mathematical base on genetic algorithm.

Conclusion

In the link performance inference method based on linear analysis model, when the rank of routing matrix is not equal to that of its augmented matrix, there is no solution for the non-homogeneous linear equations. In order to solve this problem, the chapter brings forward the use of a simple mathematical transformation to change the problem of link performance inference to a multi-objectives optimal one, and then use genetic algorithms to obtain a sub-optimal solution. The simulation results show that this method could infer link performance inference effectively.

Chapter 7 Summarization and Discussion

Summarization

This manuscript has analyzed and proposed contributions on the following key issues about Ad Hoc network performance measurement based on NT technique.

( (3) The document presents an Ad Hoc network topology dynamic characteristic analysis technique based on measurement sample. When the scene file of mobility model could not be obtained beforehand, this method uses tree system measurement model and active measurement method to obtain end to end path performance sample. Furthermore, the long time of steady period is considered as the measurement window time. Next, the Ad Hoc network topology architecture during measurement window time is inferred based on clustering algorithm according to path performance measurement sample. The simulation verifies the effectiveness and correctness of the methods above.

(4) The document researches deeply on Ad Hoc network link performance inference based on linear analysis model. In the process of Ad Hoc network measurement, how to bring forth an light link performance inference methods is a challenge for its topology dynamic characteristic. The document firstly analyzes the inequality relationship between path and link performance, and it also proves in theory that if the different sub-paths have more longer length of shared links, the communication characteristic of them is more similar, specially for its delay and loss ratio. Next, the document presents and Ad Hoc network link performance inference method based on linear analysis model. In this model, when the rank of routing matrix is equal to that of its augmented matrix, linear algebra theory could be used to obtain the solution space of the non-homogeneous linear equations, and furthermore to infer the network link performance. Otherwise, when the rank of routing matrix is not equal to that of its augmented matrix, there is no solution for the non-homogeneous linear equations. In order to solve this problem, link performance inference problem is transformed to a multi-objectives optimal one through simple mathematical transformation for the non-homogeneous linear equations, and then use genetic algorithms to obtain a sub-optimal solution. The simulation verifies the effectiveness and correctness of the methods above.

Discussion

Wireless network performance measurement based on NT technique is still in its infancy. Although the document have done some exploratory works on Ad Hoc network performance measurement based on NT technique, there are still some open issues need to be studied on.

(1) When we analyze and research on the Ad Hoc network steady period and topology dynamic characteristic, the scene files of mobility models, such as RW, RWP, RPGM, Freeway and Manhattan, and so on, are used as the example. Although the method above has universal property, whether they could be used for other mobile scene of other mobility models still required to be studied.

(2) The Ad Hoc network link performance inference methods mainly focused on delay and loss rate, for other network performance parameters, such as energy, available bandwidth and traffic, are also required for further study in the future.

(3) The characteristic information extraction of Ad Hoc network steady period is only determined by path delay jitter. How to find other characteristic information to improve the accuracy of this algorithm is still need to be further studied on.

(4) The algorithm verification in the document is carried out in the simulation environment, it needs to further verify its effectiveness in the actual Ad Hoc network application environment in the future.

Figure 1 - 1

 11 Figure 1-1 Ad Hoc network plane topology architecture

Figure 1 - 2

 12 Figure 1-2 Ad Hoc network layered topology architecture

  .D. Programs Foundation of Ministry of Education of China(Grant No. 200806990030) , and the Innovative Foundation of Northwestern Polytechnical university in P.R.China(2008KJ02028).

  Network & Service Inc. (ANS) started to implement Surveyor project in 1995. The objective of this project is to build up the network measurement infrastructure in many education organizations and institutes to measure the path delay, loss ratio and routing information defined by the IPPM working group of IETF. It used GPS to provide with the synchronous information so that users and ISP could obtain the link performance and network reliability precisely. National Laboratory for Applied Network Research (NLANR) was established by NSF of U.S.A. in 1996, and in the charge of CAIDA in 2006. The objective of NLANR is to build up a global network measurement and analysis infrastructure to collect and analyze the measurement sample, and to display the analysis results in videotext mode so as to serve for QoS and flow engineering. At present, it focuses on two projects, one is Active Measurement Project (AMP), and the other one is Proactive Measurement Analysis (PMA). They have developed some measurement tool, such as AMPlet, Cichlid and OcxMon, and so on. Specially, in order to overcome the shortcoming of active measurement protocol (i.e., ICMP) and to extend the network measurement scope, NLANR brought forth a new network measurement protocol (i.e., IPMP), and submitted its RFC to IEFT in 2002. Since it is difficult to let IPS to support IPMP for security and incredibility reason, IPMP has been given up in 2004. CAIDA was established in 1997 and tool part in some global network measurement plans. The objective of this organization is to collect and analyze on the measurement data statistically so as to improve internet performance, to optimize network topology architecture and to deploy network resources rationally. It has also developed some tools concerned, such as Cflowd, CoralReef, Cuttlefish, Skitter, and so on. At present CAIDA has deployed 23000 nodes in 17 countries in North America, Europe and Asia. Its research will focus on the following three themes, internet measurement infrastructure, data collection and measurement sample analysis. RIPE NCC is an independent, nonprofit European organization. It has implemented two network measurement projects, one is Test Traffic Measurement (RIPE-TTM), and the other is Routing Information Service(RIPE-RIS). The former adopts TTM Test Box and active measurement method to obtain delay, loss ratio and delay jitter among different IPS. The Test Box has been deployed in 70 nodes in Europe. The latter mainly collects and storages some BGP routing information and provides them for some research institutes and researchers, and has developed some necessary tool, such as BGPPlay, ASInUse and Looking glass, and so on.

  -1(b).

  (a) single-source measurement system model (b) multi-source measurement system model Figure 2-1 Measurement system model In the tree topology measurement model, Let T=(V, L) denotes a reverse tree with the node set V and link set L. V could be finely classified as { , , } V S M R = , where S denotes the set of source nodes, M the set of interior forwarding nodes and R the set of leaf nodes(or receiver nodes). As in figure 2-1(a), {0} S =

Figure 2 - 2

 22 Figure 2-2 NT measurement probes Packet pair probe Nowak Robert et al. brings forth to using packet pair to

Figure 3 - 1 A

 31 Figure 3-1 A holonic model of MANTs There are at least four holonic properties in the holonic model of MANTs as in the figure 3-1. (1) At every level, the nodes are divided into smaller granularity, as we call it sub-holon. As in figure 3-2, at the n+1-th level, all the sensor nodes belong to only one sub-holon. (2) From construction viewpoints, we could use a tuple {L, S}( marked as H(H = {L, S})) to depict a holon simply, where L={l} is the head set of holon. S={s1,

Figure 3 - 2

 32 Figure 3-2 Neighbor relationship diagram

Figure 3 - 3

 33 Figure 3-3 RIO model in MANTs

Figure 3 - 4

 34 Figure 3-4 RIO diagram of the roles played by Sensor nodes in dynamic state During the period of establishing a cluster or sub-cluster, all the sensor nodes are divided into two types based on whether receiving or not, only one or more Invitation message, one is part, the other is multi-part as in figure 3-4. We consider that MANTs are now in dynamic state during these time. Part means that a node only belongs to one set of neighbors. However, multi-part means that a node belongs to more than one sets of neighbors, that is, there is a intersection among different sets of neighbors.

Figure 3 - 5

 35 Figure 3-5 RIO diagram of the roles played by Sensor nodes in steady state After implementing the scheme of "Set dividing rule"(or "Cluster dividing rule"), the sensor nodes in a cluster or sub-cluster are divided into another two types, one is Stand alone, the other is Member as in Figure 3-5. Stand alone means that the sensor nodes are

3 t

 3 , the interval time τ between snapshot time k and choice time 3 t should be computed firstly, then the current position , C j k at snapshot time k could be obtained according to the formula 3-7. The position snapshot of mobile nodes capturing algorithm is described as the follow.

(

  Snapshot time equal to 1.0s

  Snapshot time equal to 0.5s Figure 3-7 Topology dynamic characteristic curve (simulation scene1, RW)

  The snapshot time equal to 1.0s The snapshot time equal to 0.5s Figure3-8 Topology dynamic characteristic curve (simulation scene 2, RWP)

  Link topology variety ratio Topology lifetime (b) Snapshot time equal to 0.25s (Manhattan) Snapshot time equal to 1.0s (RPGM) Link topology variety ratio Topology lifetime (d) Snapshot time equal to 0.25s (RPGM) Figure 3-9 Topology dynamic characteristic curves The Ad Hoc network topology steady and non-steady period are obtained through analyzing on the network topology snapshots. In figure 3-10(a), t i denotes different choice time, and b i the topology steady period during which Ad Hoc network topology keeps invariable, and a i the non-steady period. The start time of each b i is called as the measurement occasion, such as 2 t , 4 t ,……, 1 t k + , and so on. The long time of b i could be considered as the measurement window time based on NT technique. The measurement occasion about RW and RWP in a certain scene is shown as the figure 3-10(b)~(c).

Figure 3 -

 3 Figure 3-10 Measurement occasion choice Therefore, we could safely arrive at the conclusion: The steady and non-steady period appear in turn during all simulation time. At the same time, the number of the steady and non-steady state and the duration time in each state vary with different mobility models and with the different parameters of movement scenes. In order to obtain more measurement sample in a limited time, the long time of topology duration time could be considered as the measurement window time, the start time of which is the measurement occasion of NT measurement on Ad Hoc network.

20 t= s as in the figure 3 Figure 3 -

 2033 11 Probability distribution chart of the number of steady period From the figure 3-11, we could likely arrive at the inconclusive hypothesis that the number of steady state appearing in a certain time approximately follows the poison distribution, and for different time there exists different parameter λ . Next, we will the Fit hypothesis testing method to verify this hypothesis. At first, we put forward the following hypothesis test problem: 0 H : The number of steady state follows the poison distribution.

1 H:

 1 The number of steady state does not follow the poison distribution.

4 . 21 λ=,

 421 when we choose RWP mobility model in a certain mobile scene as our research objective. At the same time, that the number of non-steady sate appearing in 10.0 seconds accords with the

Figure 3 -

 3 Figure 3-13 PDF of non-steady duration time

0H:

  The steady duration time accords with the exponential distribution, that is,

1 H:

 1 The steady duration time does not accord with the exponential distribution.

  equation of formula 3-25, then the following equation 3-27 could be obtained.

.

  If time is set as 4s, 8s and 10s respectively, the experimental probability about state keeping invariable and varying is shown as the figure. 3-14 ,3-15 and 3-16 according to the forecast formula 3-31,3-32 and the warning formula 3-33,3-33, where x axis denotes the parameter of exponential distribution 1 λ , y axis the parameter 2 λ , and z axis denotes the probability value.

Figure 3 -

 3 Figure 3-14 Experimental probability about forecast and warning formula with t=4s

Figure 3 -

 3 Figure 3-15 Experimental probability about forecast and warning formula with t=8s

Figure 3 -

 3 Figure 3-16 Experimental probability about forecast and warning formula with t=10s

  This model points out which nodes are sources or leafs to build up the network measurement topology architecture. This chapter adopts the single source measurement model as the figure 2-1(a) in section 2.3, where the line expresses the connection relation of wireless links. That is, the two mobile nodes on the side of the wireless link have the chance to communicate with each other. The network topology relationship as the measurement model actually denotes the logistic one. In logistic topology relationship, the input or output degree of any mobile nodes is more than 1. If the former is more than one, it shows that the mobile node is the convergence one. If the latter is more than one, it shows that the mobile node is the forficate one.

Figure 4 - 1

 41 Figure 4-1 Ad Hoc network topology steady and non-steady period

  When the leaf nodes receive the probes, the path delay time is computed according to the formula Delay = Tr-Ts, where Tr denotes the time of source node sending the probe, and Ts denotes that of the leaf node receiving the probes. Next the degree of leaf nodes in the network measurement model is computed according to the formula 255 d tt l = -, where the initial value of TTL is set as 255, and ttl denotes the real value of hop number from source node to the receiver. The similarity of probe receiving state If the probe receiving state of node i is denoted as { } k x i , where k is the measurement number. 0 k

Figure 4 - 2

 42 Figure 4-2 The relationship between topology similarity with the number of measurement

Axiom 5 - 1 . 1 l

 511 If the packet loss rule on the link accords with Bernoulli model, the successful transmission rate on path (i.e., ( , ) Path i j ) is equal to the product of that on each link(i.e., k β ), that is denoted as the formula 5-3.In the tree network measurement model as figure2-1(a), if the packet successful transmission rate on each link 0,

  AY r r n = = < , then the solution space is composed of n r -characteristic solutions (i.e., { }(1) i n r i η ≤ ≤ -) for the homogenous linear equations and one special solution (i.e., β ) for the non-homogenous linear equations. Therefore, the solution space of the non-homogeneous linear equations could be denoted as the following formula 5-8.

time. ( 2 )

 2 In measurement window time, single source measurement system model and active measurement are used to implement the end to end Ad Hoc network measurement for many times. (3) According to the end to end network performance measurement sample, network performance inference method based on linear model is used to infer Ad Hoc network link performance distribution. Besides, according to the solution space expression as the formula 5-8, if k i chooses different value, the probability of link performance performance distribution, and the link performance having the maximum value of probability will be chosen as the inference result.

Input:

  path performance { } Y i ,routing matrix A ,measurement number N .

Figure 5 - 3 2 )

 532 Figure 5-3 the link with big loss rate was distributed on different path(2) The different links with loss rate are distributed on the same path. For example, if the theoretical value of packet loss rate for link 1, 2 and 5 are 0.03, 0.05 and 0.08 respectively, that is, when that of link loss rate is small, the inference result is shown as the figure5-4(a). If the theoretical value of packet loss rate for link 1, 2 and 5 are 0.10, 0.20 and 0.30 respectively, that is, when that of link loss rate is big, the inference result is shown as the figure 5-4(b).

Figure 5 - 4

 54 Figure 5-4 The different links with loss rate on the same path

  Figure 5-5 the influence of probe sending speed on inference result

Figure 5 - 6

 56 Figure 5-6 The theory value and inference result of link delay time In measurement window time, inference result of link 2 delay time varies with measurement time according to the measurement sample of different measurement time is shown as the figure 5-7. In figure 5-7, inference result of link delay time will become nearer and nearer to its theoretical value, since the leaf nodes could receive more measurement sample with the measurement time becoming longer and longer.

Figure 5 -

 5 Figure 5-7 the influence of measurement time on inference result

Definition 5 - 2

 52 Correlative degree of link is the meaning number of shared paths for all links and denoted as CS in network measurement model. In formula 5-11, N l denotes the number that link l belonged to different paths, and | | n L = the sum of different link in logical topology. Next we use the binary tree as an example to analyze the parameter CS.

-

  different paths. Then CS could be denoted as the following formula according to the definition 5-6.

(

  0

  as the following formula according to vector norm.

  map relation above, its decoding relation is shown as the formula 6-5.

  (a) To compute the existence number N i of each individual in population according to the formula 6The integral part value of N i is considered as the existence number, and copyN i ∑ ⎢ ⎥⎣ ⎦ individuals to be inherited to its offspring based on the descending order of fitness value ( ) less than the number of population M , the anterior M N i -∑ ⎢ ⎥ ⎣ ⎦

Input:

  crossover probability P c ,population ( ) M t ,individual number N; Output: result ' ( )

  function. The objective function value of the optimal individual and the objective function mean value of individual in each generation is shown as the figure 6-1. When population evolves to 15 generation, the genetic algorithm achieves its convergence, and the link loss rate inference results are shown as table 6-2. When the genetic algorithm is run for 200 times, each time it selects the different initial population at random, then analyzes suboptimal solutions for each run times statistically. The link 5 loss rate inference result is shown as the figure 6-2.

  generation The object function value Object function value of the most optimized individual Object function average value of individuals

Figure 6

 6 Figure 6-1 Objective function evolution process

Figure 6 - 2 Figure 6 - 3

 6263 Figure 6-2 Link 5 loss rate probability distribution In link delay inference method, the objective function value of the optimal individual and the objective function mean value of individual in each generation is shown as the figure 6-3. When population evolves to its 20 generation, the genetic algorithm achieves its convergence, that is, the objective function value of the optimal solution achieves its minimum. The link loss rate inference results are shown as table 6-2. When the genetic algorithm is run for 200 times, each time it selects the different initial population at random, then analyzes suboptimal solutions for each run times statistically. The link 2 delay inference result is as the figure 6-4.

Figure 6 - 4

 64 Figure 6-4 Link 2 delay probability distribution

Definition 6 - 1 Definition 6 - 2 Definition 6 - 3

 616263 Patten H is the any character string of the solution vector space character string set which is constituted by character set {0,1,*} . For example, if the length of character string is six, pattern 000*11 denotes all the character strings the position 1,2,3,5, and 6 of which is "00011" respectively , i.e., {000011,000111} Expansion order Γ is the number of determinate position in a pattern.If the length of pattern H is 15, i.e., "011***100*11001" , then the expansion order ( )H Γis equals to 11 ( ( ) 3 3 5 11 H Γ = + + = ). It is obvious that more higher the expansion order of pattern is, more the number of excellent gene in a pattern is, and less the potential individuals are. Distance is the length between the first excellent gene and the last one of pattern H, which is denoted as ( ) H Φ . For example, the distance of pattern 00**110*11*** is 9 (10-1=9).Next, the accumulation of excellent gene in offspring generation is obtained through analyzing on the influence of three genetic operators on excellent gene.

  Mutation operator. If the probability of one position in a gene being changed is P m , when the excellent pattern H i is operated by mutation operator, then the probability of excellent gene in pattern being reserved could be denoted as the formula 6-19.

)

  The document summarizes and analyzes traditional network measurement technique and wired network measurement method based on NT technique. Then we discuss the newly research about NT technique, such as research contents, measurement model, measurement methods, probes, and link performance inference methods.(2) The document presents an Ad Hoc network topology dynamic characteristic analysis technique based on mobility model. This method is based on the snapshots idea of photography in our daily life. It uses the scene file of mobility model in NS-2 tool as its research objective, and adopts Ad Hoc network topology snapshots capturing method to obtain the topology architecture at any time. Then it analyzes the fore-and-aft two consecutive topology architecture to find Ad Hoc network topology steady and non-steady period. Besides, it adopts the long time of topology steady period as NT measurement occasion, that is, measurement window time. Next, the document uses RWP as an example, and adopts the fit hypothesis testing to obtain the following results safely: that the number of steady period and non-steady one probability distribution in certain time t accords with Poisson distribution, and the duration time probability of steady period and non-period in our simulation time accords with exponential distribution. For the Ad Hoc network topology snapshots with long snapshot time, Markov stochastic process with discrete time and state is used to obtain the state transfer matrix. Under this condition, if the current state of Ad Hoc network topology is know, the probability of its state variability or invariability after n snapshots time could be obtained according to state transfer matrix. Moreover, for the topology snapshots with short snapshot time, Markov stochastic process with consecutive time and discrete state is used to infer the forecast formula of topology state keep invariable and the warning formula of topology state variability, which provides the measurement window time for Ad Hoc network with theory basis. The simulation results verify that the effectiveness of all the methods above has the universal property, and they could be used for all the mobility models in NS-2 tool.

  At present, NS-2 tool supports all the four types of MM above. The storage mode of mobile track is similar to the scene file produced by the Setdest tool. In all the MM supported by NS-2, one or more beelines with different length compose the mobile track of nodes. Although the literature [175] brings forth a Random Circle-movement Mobility

Model (RACMM), node moves around a center one to finish a circle movement. The RACMM uses a polygon to simulate the circle, and thus the curve track is transformed into the many beelines, which adopts the same scene file format to storage the mobile track of nodes too. Therefore, the uniform mathematical model for the four types of mobility model in NS-2 tool could be obtained through analysis on its scene file.

Table 3 -

 3

1

shows the scene file format of mobility model in NS-2 tool. For example, the former three lines set the initial position of the node 0 at 0.0s. the line 4,5,6,7 denote the next position of node 0 at time 1.0s, 2.0s, 3.0s and 4.0s and the velocity from current position to the next one respectively. There are two points to be noted. (1) Without reference to the beeline or curve track of mobile nodes, that in any two successive time is only a beeline.

(2)

The nodes in any two successive time either is immobile or move on a line at an even velocity.

Table 3 -

 3

	time	position
		$node_(0) set X_ 650.005072169252
		$node_(0) set Y_ 705.307983770981
		$node_(0) set Z_ 0.000000000000
	$ns_ at 1.0	"$ node_(0) setdest 20.39 30.78 3.57"
	$ns_ at 2.0	"$ node_ (0) setdest 10.57 20.35 4.73"
	$ns_ at 3.0	"$ node_ (0) setdest 30.13 40.68 5.21"
	$ns_ at 4.0	"$ node_ (0) setdest 10.95 20.77 6.18"

1 Mobile scene file format in NS-2

  the current position of node i at choice time is ,

				x c i j ,
	then after time t Δ , the position	( ) , 1 x t c i j Δ +	and	( ) , 1 y t c i j Δ +

could be denoted as the formula 3-7.

  at snapshot time t and is stored in the bidirectional list List PosSnapshot Simulation time T,snapshot time t Δ , scene file ScenceFile , mobile node set V

	The data structure of bidirectional List chooseInfo -	about the choice state of mobile node
	Output: position snapshot List PosSnapshot -is defined as the follows.
	Process: struct ChooseInfo
	{	1.	Read chooseInfo from ScenceFile and create the List chooseInfo -	for each node i
			int id;	For (each i ∈ V )	//choice time number
		2. 3. float time; float x, y;	N = T ξ ; * ptr List chooseInfo = -Store the part of choose Info at choose time 0 into List PosSnapInfo head -> ; *cur List chooseInfo head = -//choice time -> ; -//current position	;
		4.	For (each k N < float des_x, des_y;	)	//destination position
			float angle;	t k = ×Δ ; ptr=cur ; t	//mobile direction
		5.	float speed;	While( t>ptr-ChooseInfo.time )	//velocity
	}					ptr=ptr->next ;
	6. The data structure of bidirectional List PosSnapshot If ( t-ptr->ChooseInfo<=0.000001 ) -	about the position snapshot of
	cur=ptr ; mobile node is defined as the following.
	7. struct PosSnapInfo Else
	{					ptr=ptr->prev ; cur=ptr ;
		8.	int id;			End If	//snapshot number
			float time;		; //snapshot time
		10. float x, y;		1 x	x v = + ×	c o s (	) 1 angle t × ; 1 y //current position s i n ( y v angle t ) 1 = + × ×
	}	11.			Store i , t , Position snapshots ( 1, 1) x y into List PosSnapshot -
						k + + ;
					End For
				End For
		Return: List PosSnapshot -
						-	from line 8 to
	11. All mobile node ( ) i i V ∈	runs the algorithm above, then the position snapshots of all

j mobile nodes could be obtained. Of course, more detail position snapshots could be obtained through decreasing the snapshot time t Δ . Input: t1=t-ptr->ChooseInfo.time ; x=ptr->ChooseInfo.x ; y=ptr->ChooseInfo.y 9. v=ptr->ChooseInfo.speed ; ptr angle θ = ->

Table 3 -

 3 2 Ad Hoc network dynamic characteristic parameter

	Conception	Definition
	link varying number	The sum of link state having been changed in all topology snapshots
	link meaning duration time	The ratio of the sum of all links duration time to link connection number
	node connection ratio	The number of node neighbor for each network topology snapshot
	node inactive degree	The number of nodes with its velocity equal to zero for each topology snapshot
	node relative velocity	The meaning absolute value of the nodes' relative velocity for all topology snapshots
	link connection ratio	The ratio of the link connection number to sum of links for each topology snapshot
	topology varying ratio	The ratio of link varying number for two consecutive snapshots to the sum of links

Table 3 -

 3 3 Ad Hoc network topology dynamic characteristic parameters

			Simulation scene 1			Simulation scene 2
	parameter	Snapshot time 1.0s	Snapshot time 0.5s	Relative error	Snapshot time 1.0s	Snapshot time 0.5s	Relative error
	Link varying number	2181	2205	1.09%	5820	5842	0.37%
	Link duration time(s)	20.780399	20.473070	1.50%	51.577404	51.442875	0.26%
	Node connec -tion degree	1.016648	1.013948	0.27%	6.789212	6.802554	0.20%
	Node inac -tive degree	0.000000	0.000000	0.00%	47.774696	47.773460	0.003%
	Node relative
	velocity	9.520205	9.518967	0.01%	0.733270	0.734241	0.13%
	(m/s)

Table 3 -

 3 4 Algorithm computing cost

			Algorithm	Statistical	Total
	Simulation scene	runtime (ms)	runtime(ms)	(ms)
		Snapshot time(1.0s)	719	203	922
	Scene 1	Snapshot time(0.5s)	859	375	1234
		Snapshot time(1.0s)	859	204	1063
	Scene 2	Snapshot time(0.5s)	984	391	1375

  If the Ad Hoc network measurement could be finished during its any steady period, it satisfies the precondition of NT measurement on it, which shows that Ad Hoc network link performance inference during its topology steady period is effective. Therefore, the effectiveness of NT measurement on Ad Hoc network is that network topology keeps steady during t Δ which starts from time t , if NT measurement time is no more than

	T t	at time t , t Δ is a time slice, if
	, [ , s s t t t T s T s ] ( ) ( ) ′ ′ ∀ ∈ +Δ ⇒ =

In Ad Hoc network, it is absolute for the nodes' mobility, but network topology varying is relative. For example, there are two cases that could prove that state of links does not vary for the node's mobility.

(1)

if any two nodes move in the same direction at the same velocity, they in practice keep immobile relatively.

(2)

Although any two nodes move in different direction at different velocity, if they are within each other's wireless communication range, it is possible that the state of link between them will keep invariability. Therefore, it is possible that the Ad Hoc network topology architecture will keep invariability during a certain period. Topology architecture invariability or steadiness is that there exists a time t , the Ad Hoc network topology architecture is denoted as ( ) is satisfied, then Ad Hoc network topology has the steady characteristic during the period from t to t t + Δ , and t Δ is also called as the Ad Hoc network duration time or steady period. t Δ , the NT measurement on Ad Hoc network at time t is effective. Thus it can be seen in practical Ad Hoc network application environment, its topology does not vary at any time. The connective state link or path of Ad Hoc network has a certain steady characteristic, it is possible to satisfy a certain QoS

Table 3 -

 3 5 The fit hypothesis testing table about the number of steady period i

											0	1	2	3	4	5	6	7	8
						n p i		1.43	5.93	12.28	16.95	17.54	14.52	10.02	5.93	3.07
						m i			1	4	10	14	23	20	12	5	1
	| m i	-	n p	| i			0.44	1.93	2.28	2.95	5.46	5.48	1.98	0.93	2.07
	(	m i	-	n p	i	)	2	0.13	0.63	0.42	0.51	1.70	2.07	0.39	0.15	1.40
				n p i

  This inequality relation means that the test statistic variable V does not belong to the rejection range, therefore, we have to accept the hypothesis 0 H , and to refuse another hypothesis 1 H . It is reasonable for us to believe that the number of steady sate appearing in 10 seconds follows the poison distribution with

	χ	2 α --= ( 1 1) r	χ	2 0.05	(9 1 1) 14.067 7.40 --= >

Table 3 -

 3 6 2 χ fit hypothesis testing table about steady duration time

Table 3 -

 3 7 Stochastic variable probability distribution parameter

  If the state of Ad Hoc network topology enters i , no matter how long duration of state i is, the probability P ij that changes into another state j is one(or 100%).If the state of Ad Hoc network is i at time t , and during the period from t to t s

						| P z s t z s > +Δ >	)
	during the period from t s
	( P z s	| t z s	)	( P z	)
	The process of Ad Hoc network topology changing dynamically could be considered as
	a Markov stochastic one. At different time , ,..., (0 0 1 t t t n	... ) t n ≤ < < < , the state of Ad Hoc 0 1 t t
	network topology is , , ..., 0 1 i i	E i n ∈ =	{0,1}	in turn. Since the state of Ad Hoc network
	topology is obtained through comparing the two successive snapshots of topology, which
	is independent of its historical snapshots, then formula 3-17 could be obtained.
	According to formula 3-17, the stochastic process of Ad Hoc network topology has the
	Markov attribution, that is, conditional shift probability of Markov stochastic process
	with continuous time is only concerned with the current state, which is irrespective of any
	historical state. The above results could also be denoted as formula 3-18.

+

the state is also i , then the conditional probability could be denoted as ( + to t s t + + Δ , where z denotes the duration of Ad Hoc network topology being state i . Since exponent distribution has the non-memorial attribution, the formula 3-16 could be easily obtained.

Table 3

 3

	-8 Error computing method
	Probability	Computing method
	Maximum error	| Max p p i i | -
	Meaning error	1 | 1 n ∑ -	| i i p p -

Table

Table 3 -

 3 9 Computing error

Table 3 -

 3

10 Probability varies with parameters 1 λ , 2 λ and time t

  Ad Hoc network topology steady or non-steady period t i 。

				x	( ) k	,time interval t
	Process:
	Initial data structure t i according to t Δ
	For ( each t i ) Calculate the average delay varying D i according to	x	( ) k	.
	(a) If (	D	i	ε < ∧	D	i	1 < ε +	)
		Calculate the average delay varying	D i	2
				If ( 2 D i	ε < )
						Unite the t i and	1 t i+ as steady period t i ;
						t i .endtime = t i .startime+ 2 t ×Δ ; t i .state = 0;

Δ

Output:

  In the algorithm of Ad Hoc network topology steady or non-steady period detection t i is a data structure as TopologyInfo to describe the Ad Hoc network topology in steady or non-steady state.

	struct TopologyInfo
	{
	int sate;	//1 denotes the steady state and 0 the non-steady state
	float starttime;	//start time
	float endtime;	//end time
	}
		1 t i+ as steady period t i ;
	t i .endtime = t i .startime+ 2 t ×Δ ; t i .state = 1;	1 = + ; i i
	End for
	Return: t i

Table 4 -

 4 1 Computing cost of steady period detection algorithm

Table 4 -

 4 2 Computing cost of topology identification algorithm

Table 5

 5

	-1 Inference errors

Table 5 -

 5 2 Run time of algorithm

	Network scale	Inference result	Measurement number	Run time (s)
		Loss rate	1050	15.3
	8 nodes
		Delay time	1050	28.4
		Loss rate	1050	73.7
	32 nodes
		Delay time	1050	86.2

  which presents the end to end network performance with measurement errors. The linear analysis model could be transformed as the homogeneous linear equations with a m n

	Chapter 6	Link Performance Inference Based on Multi-objective Optimization
	When network end to end measurement sample ' ( ) i m y i ≤	is known, in order to obtain
	the link performance ( ) i n
			×
	routing matrix A as the formula 6-1.
		107

Table 6 -

 6 1 Initial parameter table

Table 6 -

 6 2 Link performance inference results

  Selection operator. If the number of individual which has the pattern H i in t generation, that is, the population is ( ) M t , is m , which is denoted as ( , )( ) denotes the types of excellent pattern. If the scale of population ( ) M t is Y, then the number of individuals which have the excellent pattern in 1 t+ generation is as the formula 6-16. Crossover operator. The crossover operator could not only produce the new individuals, but also destroy the pattern with excellent gene. If the distance of excellent pattern H i is ( )

	m When excellent gene is implemented by selection operator, the number of excellent t i H i ≤Ψ , ( ) ( , 1) ( , ) ( ) Y F H i m t m t H H i i F H i i ⎢ ⎥ × ∑ + = × ⎢ ⎥ Ψ ∑ ⎣ ⎦ (6-16) individuals is as the formula 6-17 where 1 1 ( ) ( , 1) ( , ) ( ) ( ) Y F H i G t m t H H H i i i F H i i ⎢ ⎥ × ∑ + = × ×Γ ⎢ ⎥ Ψ ∑ ⎣ ⎦ (6-17)

Ψ

Acknowledgements

I am indebted to my French advisor Professor Abderrafiâa Koukam and Associate Professor Vincent Hilaire for their encouragement and support during days in France.

Your patience, research passion, constructive suggestions for the completion of my thesis have played a great help or me. Your rigorous and practical scholarly spirit, and humorous conversation manner, has been an inspiration for me. On the occasion of my Ph.D thesis completion, pay tribute to my advisor Professor Abderrafiâa Koukam and Associate Professor Vincent Hilaire with heartfelt thanks! I would also like to thank my Chinese co-advisor Professor Cai Wandong for his patience and guidance. From the thesis topic, the progress of research work to complete the thesis, Professor Cai has given me the patience and meticulous guidance. His rigorous scholarship, profound knowledge, generous easy-going man, and scholarly wisdom have left me with a profound impact and will benefit me for life. I thank the members of Network and Information Security Laboratory of Li Yongjun, Li Huixian, Zhao Zuo and Zhang Yi, and so on, for the endless discussion we have had, and still have, over the network performance measurement, communication protocol. I thank also of the Ph.D. candidates: Wang Wei, Wang Yue, Tian Guangli, Zhao Tao, Zhao Yu, Fan Na, we created a good working environment with harmonious academic atmosphere.

In particular, I am grateful to my parents. they gave me endless care, support and encouragement. At the same time I would like to thank my wife, for her understanding, encouragement, love and care the day of my dissertation.

I would like to thank the member of jury who reviewed it and their remarks greatly helped me to improve it.

Finally, to all who helped and cared for me to express my sincere thanks!

topology is i , that of the next topology is j . Since the two successive snapshots of Ad Hoc network topology are compared to find that if they have the same topology architecture, that is, the state of next Ad Hoc network topology is only correlative with that of current snapshot, which is not relative with other historical state of Ad Hoc network topology. Therefore, the process of Ad Hoc network topology changing has the characteristic of Markov, and the p ij could be denoted as formula 3-14.

Since the state variety of Ad Hoc network topology is independent of its historical state, if X n denotes the state of Ad Hoc network at time n , stochastic variable { 0} n X n ≥ accords with Markov chain, and its state transfer matrix with one step P could be denoted as the follow.

Where α , β denotes the probability that when the current state Ad Hoc network topology snapshot is steady or non-steady, and that of the next snapshot is also the steady or non-steady one respectively. Since the state transfer matrix with one step P of Markov chain has been defined above, the probability of Ad Hoc network topology variety with m step

If Markov chain theory is used to analyze the process of Ad Hoc network topology changing dynamically, since the time is discrete, if the state of Ad Hoc network topology is i at the initial time 0 t , after m steps , the conditional probability of that being j state at snapshot time 0 m t t + ×Δ when snapshot interval time is t Δ , which could not reflect the dynamic characteristic of Ad Hoc network topology at the continuous time called as the linear analysis model of loss rate. If a long path is considered as the constitution of many sub-paths and links, there exists the following rule as theorem 5-3 which could be easily proved according to theorem 5-1.

Theorem 5-3 If the packet loss rule on the link accords with Bernoulli model, the path (i.e.,

( , )

Path i j ) is comprised of n sub-paths and m links (i.e., , L z w ), then the successful transmission rate on path (i.e., ( , ) Path i j ) could be denoted as the following formula.

The theorem 5-3 shows that the packet successful transmission rate on path has the product relation with that on sub-paths and links. Next the inequality relation of loss rate on path with that on sub-paths and links will be analyzed. In pseudo tree measurement model TP , the path (i.e., ( ,) 1

is any mobile node and satisfies the following rule, 1 S M N ∈ ∪ , R N n ∈ . If the wireless link between node 1 N i-and N i is denoted as l i , the path (i.e., ( ,) 1

, where 2 l and l n is the first and last links on the path ( , ) 1

Path N N n . Supposed that each mobile node has enough buffers in Ad Hoc networks, the packet The best optimal equations of the least squares method is expressed as the formula 6-4 according to the first order prerequisite of solving the optimization problem with no constraint condition.

The equations 6-4 is called as positive definite one. If the rank of routing matrix A is full, that is T A A is positive definite, the unique solution of formula 6-4 could be expressed as the following.

Where

is also called the generalized converse matrices of A , and denoted as A + . Then iteration method, such as conjugate gradient algorithm, could be used to obtain the optimal solution.

Therefore, there are three shortcomings when the least square method is used to solve the multi-objective optimal problem. (1) The unique solution could be only obtained when T A A is a positive definite symmetric matrices, this method could not settle out the problem of no solution for measurement error. (2) Link performance probability distribution, not numerical value, reflects the network performance characteristics in fact.

(3) Although the least square method could satisfy the formula 6-3 to reach its minimal value, it is difficult to guarantee that each equation of formula 6-2 have its minimum. In order to solve the three problems above, this chapter uses the genetic algorithm to solve the multi-objective optimal problem and obtains the network link performance probability distribution.

Link Performance Inference Based on Genetic Algorithm

Genetic Algorithm (GA) is a stochastic search method based on natural selection and genetic evolution, which could achieve and accumulate the knowledge of search space to obtain the optimal or pseudo-optimal solution by controlling its search direction automatically.

The implementation of genetic algorithms mainly involves six factors, that are, the

Gene Algorithm

If the number of evolutionary generation is denotes as t , the number of individual in population (0) M is M.

( ) M t denotes the population of t generation, and the length of chromosome is N, then the network link performance inference algorithm based on multi-objective optimization is described as the following.

Simulation and Validity

In order to validate the effectiveness of the link performance inference method above, this chapter adopts the same simulation scene and measurement model as that in chapter 5-4. NS-2 tool was used to found the simulation scene and Matlab to process measurement data and infer link loss rate and delay based on gene algorithm. The initial parameters are set as the table 6-1 in genetic algorithm.

Input: crossover probability P c , mutation probability P m , the number of generation T, computing times K; Output: the result of link performance ( )

Process: Specially, there are often more than one solution which could satisfy the objective function for a group of path performance, which could be solved by hanging the population scale and distribution, and increasing the run time of genetic algorithm.

In order to increase the inference precision, the statistical data about link performance inference is composed of two parts. One is to analyze statistically the suboptimal solution for the same time ( i.e., delay) or the same period (i.e., loss rate) through running genetic algorithm many times. The other part is that for the different time or periods. At the same time, the different coding of solution space will influence the inference result, which could be solved through effective performance parameter coding and rational selection of initial population.

Temporal Complexity Analysis

The temporal complexity of genetic algorithm for link performance inference mainly comprises of initial population producing and three genetic operators. For example, if the population scale is M , the length of chromosome is N , and iteration time is set as T. The temporal complexity of initial population is mainly comprised of population producing randomly, computing hamming distance and gene locus probability statistics, and its' temporal complexity are ( )

and ( )

O M N × respectively. Therefore, the temporal complexity of initial population is as the formula 6-13