Fuzzy-Rule-Based Object Identification Methodology for NAVI System

We present an object identification methodology applied in a navigation assistance for visually impaired (NAVI) system. The NAVI has a single board processing system (SBPS), a digital video camera mounted headgear, and a pair of stereo earphones. The captured image from the camera is processed by the SBPS to generate a specially structured stereo sound suitable for vision impaired people in understanding the presence of objects/obstacles in front of them. The image processing stage is designed to identify the objects in the captured image. Edge detection and edge-linking procedures are applied in the processing of image. A concept of object preference is included in the image processing scheme and this concept is realized using a fuzzy-rule base. The blind users are trained with the stereo sound produced by NAVI for achieving a collision-free autonomous navigation.

INTRODUCTION
The World Health Organization estimated that around 180 million people worldwide are visually disabled. Of those, between 40 and 45 million people are blind [1]. Blind people's navigation is restricted and sometime hazardous because they do not receive enough information on the objects or obstacles in their environment. Electronic travel aids (ETAs) are electronic devices designed to aid the navigation of blind people. ETAs design depends highly on the type of sensor used in the system, the method of conveying information to the blind, and also the system hardware. Most of the early ETAs use ultrasonic, infrared, or laser sensors for obstacle detection [2]. Since 1991, the development of vision substitution system using optical devices has become eminent.
The vOICe, Vuphonics and Optophone are the only most important earlier ETAs that use optical sensors as input devices. The vOICe was developed by Meijer in 1991 [3]. The working concept of The vOICe is based on "image-to-sound" conversion wherein the system captures images in front of the blind user and the image properties are transformed into sound patterns. The image is resized to 64×64 pixels and grey-scaled into 16 levels. The sound pattern is generated using sine wave; the loudness depends on the intensity value of each pixel in the image. Another similar invention is the Vuphonics, which is developed by Dewhurst [4]. This system attempts to convey the feature of visual image through coded sound effect and their tactile equivalent. Efforts are made to realize features such as the colour, texture, distance, as well as the entities from the captured image. The Optophone developed by Picton and Capp is another device that attempts to map image to sound [5].
Navigation assistance for visually impaired (NAVI) is a vision substitution system that is also based on image-tosound concept. This system has been developed to identify objects or obstacles in indoor environment such as inside the building and along a corridor. One of the main differences between NAVI and the other vision sensor-based aids is that the implementation of image processing methodology in NAVI facilitates more importance to the properties of objects rather than the background. The captured image from the vision sensor was resized to 32 × 32 pixels and quantized into four grey levels. Objects were identified with grey values. The identified objects were then enhanced and the background was suppressed using a clustering algorithm [6]. The processed image was mapped into stereo sound patterns; the amplitude of the sound was a function on the grey intensity of the image. The NAVI system was tested on blind volunteers to get the response as well as the suggestions regarding the pleasantness and logical meaning of the sound produced.
The objective of this paper is to improve the image processing methodology in the NAVI system. In the earlier image processing, the objects in the captured image were identified with their grey values. Due to lighting effects, a single object may have more than one grey level. Hence, there were possibilities that objects in the image were not highlighted compared to background. Noise elimination procedure was not undertaken in the earlier version. Furthermore, the grey-level quantitization in the processing would result in a reduction of information in the image. This information is inevitable for object identification.
This paper highlights how these drawbacks have been eliminated in the new design of image processing methodology. In the proposed procedure, a noise elimination stage is also incorporated. A concept of object preference is included so that the blind can identify the presence of nearest object for a collision-free navigation.

HARDWARE OF NAVI
NAVI system developed for vision substitution has a headgear mounted with the vision sensor, a pair of stereo earphones, a single board processing system (SBPS), and a specially designed vest for housing the SBPS. The SPBS selected for this system is a PCM-9550F version with an Embedded Intel low-power Pentium MMX 266 MHz processor, 128 MB SDRAM, 2.5-inch lightweight hard disk, two universal serial buses, and an RTL 8139 sound device chipset, all assembled in a microbox PC-300 chassis. The weight of SBPS is 0.7 kg. Constant 5 V and 12 V supply for SBPS are provided from the batteries placed in the front packets of the vest. The weight of battery is approximately 0.2 kg. Vision sensor selected for this application is a digital video camera, Kodak DVC325 [6]. Figure 1 shows a blind individual carrying the headgear and the processing system in the vest.

IMAGE PROCESSING METHODOLOGY
The image captured by the digital vision sensor has to be processed in real time and transformed into an acoustic pattern to the earphones of the blind user. Since the processing is done in real time, the time factor consideration is critical. Real time, we mean here, is the continuous sampling and processing of the images of the scene and converting as sound patterns to the earphones at a specific rate. In the developed prototype equipment, a rate of 1 (or 2) image frame per second is employed. The rate of sampling depends on the duration of image acquisition, image transfer to processing system, image processing, sound generation, sonic transfer to earphones, and the duration of acoustic information heard through earphones for each image. However, the sampling rate mostly depends on time duration of acoustic information heard though earphones for each image. Initially, during training phase of the blind, the duration of acoustic information is set longer for each image. As the blind becomes familiar with the sound generated from the equipment, the duration of the acoustic information for each image and hence the time gap between each sampling can be reduced. At the training stage, the sampling time is fixed to approximately 1 second. Then the computational time of the processing module has to be much less than 1 second so that the blind has sufficient time to hear and understand the sound [6].
Most of the earlier works on image-to-sound-based system for the blind in the literature do not consider any suitable image processing procedures. In these works, information from the unprocessed image is fed to the auditory system of blind person. This excessive information causes a difficulty to the blind people in understanding the feature of objects in the image. In this proposed work of NAVI, the amount of information to be delivered to the auditory system is reduced so that only the required information regarding the features of objects is given to the blind.
In the case of an industrial vision, the object location and its features can be easily identified since the object models lighting, and other parameters are known a priori. In vision substitution system such data cannot be known a priori due to highly changing environment in front of the blind.
In Figure 2, the block diagram of the proposed image processing methodology is shown. The captured colour image is resized to 32 × 32 [6]. The reason for selecting 32 × 32 size is mainly to achieve the smallest real-time image processing without compromising the quality of objects in the image plane. This selection of resizing is also important in restricting the amount of information that human ear can assimilate per second. Canny edge detector is used to detect edge locations in three-colour components in RGB image and the results are combined to give overall edges of the image. A method of edge-linking is proposed to combine the broken edges and the edges at the boundary of images. Unnecessary edges are removed using a noise removal procedure. Region inside the closed edges are considered as objects. Fuzzy rules are applied to assign a preference to the identified objects. Each of these processing steps is discussed in detail in the following sections.

Edge detection
Edge detection is one of the most important human vision properties. Often human identifies the object with its boundaries and shape. The goal of edge extraction is to provide useful structural information about object boundaries. From the edges, the object properties such as area, perimeter, and shape can be measured for object identification [7]. Laplacian, Roberts, Sobel, and Prewitt are some of the edge detector operators [8]. These operators can detect edges by using convolution masks that represent the "ideal" edge step in various directions. The main disadvantages of these operators are their scale dependence and noise sensitivity. Canny edge detector is one of the optimum edge detecting methods for step edges corrupted by white noise [9]. Canny edge detector has better performance in edge detection than the other methods. In the earlier image processing methodology of NAVI system, the boundary of objects is detected using a neural network-based Canny edge operator. The size of the filter, threshold, and the ratio of threshold are derived by applying a feed-forward neural network. In some cases, the edge detectors applied to greyscale image do not provide enough information in identifying a meaningful object. Many researchers have extended their attention to colour image processing since more edge information can be extracted from colour images [10,11].
In this work, an attempt is made to use colour information for edge detection in NAVI system. Generally the edge detection method on colour images can be classified into three categories. First, the edges are detected in each colour channel (e.g., R, G, and B components), respectively. The results are then combined. Second, edges are detected in the luminance channel only. Third, edges are detected based on the gradient in the three-channel image field [12]. More recently, Wesolkowski et al. examined a comparison of colour edge detection performance in several colour spaces [13]. In this paper, the edge detection is employed in RGB colour space. The colour image is separated into red component, green component, and blue component. Canny  desired edges, they are combined using an "OR" operator. The implemented Canny edge detector has been found adequate for NAVI application. However, it is realized that edge detection alone is not enough to extract the object from the image. Further processing is undertaken to identify and connect the broken edges to form meaningful objects.

Edge-linking
Images of real scene naturally contain objects, which are incomplete or distorted by various factors such as the lighting effects and the positioning of the object. Due to these factors, edges in the real images seldom form the closed and connected boundaries that are required for the object extraction. An edge-linking process is required to assemble these edges into meaningful edges. Based on the analysis performed in several experiments, the combined edges produce gaps of less than three pixels in the image. As a solution, an edge-linking algorithm is undertaken to connect broken edges with two gaps. The combined edge has to be thinned for preprocessing. This is to provide an edge width of one pixel. Each edge is then analyzed in 3 × 5 neighbourhoods for horizontal direction and 5 × 3 neighbourhoods for vertical direction. This candidate edge must smoothly connect the broken edges. Figure 3 illustrates the candidate edges for horizontal and vertical directions.
In the experimentation, it is also noted that the edge detector fails to track edges at the border of image. In vision substitution system, all objects regardless of their positions must be considered. Some of the objects may be located at the border of the image and so it is not in complete form. Thus the next approach in edge-linking aims to connect the broken edges at the border of image. Most of the important edges will be missing in the top and bottom row as well as in the first and last column of the image. The edge-linking is  done for each border to form edges at this border. For the top border, edges in the second row of the image are scanned. If broken edges are found, pixels above the scanned edges are set as foreground. The same method applies for other three borders of the image. After the necessary edge is formed at the border of the image, edges present at the border are connected so that a complete object boundary is formed. All edges in the image are labelled to ensure that only edges with the same label will be connected. Once the edges are labelled, each edge in the image border matrix is scanned. Starting at the first scanned edge, the next edge is located and identified as the end edge if it has the same label with the first edge. Each pixel between the two scanned edges is presumed to belong to a straight edge segment and this pixel is set to foreground. If there are more than two edges with the same label present at the border, the process is omitted.

Noise removal
The goal of noise removal is to remove the extraneous edges present in the image without affecting the desired objects. Some basic morphological operations are used in this stage. Morphology is a technique for extracting image components, which are useful for region shape representation. In the morphological operation, a pixel that has value 0 (off pixel) is considered as background and a pixel that has value other than 0 (on pixel) is considered as foreground. Object is located as a set of on pixels in an image that form a connected group [14,15]. Region inside the closed edge is identified as an object. Therefore, this region has to be set to foreground. Dilation and erosion operations are undertaken to smooth the object images. A disk structuring element with the size of one pixel is created. This structuring element is used in erosion operation to remove one pixel from around the boundary of all objects. As a result, the extraneous edges present in the image will be eliminated and the objects will shrink. To restore the objects to their original size, dilation operation is applied to the eroded objects using the same structuring element.

Fuzzy-rule-based object preference
The fundamental task involves in this stage the determination of the object of interest in the enhanced image. Usually in the industrial machine vision, objects of interest are found by evaluating certain object features such as size, colour,

Outside iris area region
Iris area region Figure 4: The "iris area" and the "outside iris area" of the image.
texture, and position. The object of interest and its features information are known and specified before the recognition task can be performed [16]. On the other hand, the selection of object of interest for a blind navigation application is uncertain and time varying. This is due to the constant shifting of the headgear-mounted camera orientation by the blind people. Significant difficulties arise as the features of objects in their environment keep on changing as the blind person moves and thus it is not possible to identify the object of interest by evaluating the fixed object feature. To resolve these uncertainties, certain properties are taken into consideration. One of the considerations is the creation of a new parameter for objects in the enhanced image. The parameter chosen here is the preference of the object. The object preference acts as a guidance to blind people to determine object of interest in the image. Moreover, by having different preferences, the blind user can easily discriminate the object properties in the environment. To simplify the recognition task as well as to avoid confusion to the blind user, the preference levels to be assigned to objects in the image should be in small number. In this work, three preferences are set: the high preference, the medium preference, and the low preference. The high preference level indicates that the object is highly preferred and it is the object of interest in the image. Object with the medium or small preference level indicates that the object is less preferred than the object of interest but still has importance for navigation purposes. To compute the preferences of object, fuzzy-rule-based system is employed. Since many of the basic concepts in recognition task are ambiguous in nature and cannot be defined precisely, the fuzzy-rule-based system appears to be a good choice to deal with such uncertainty issues.
The designed fuzzy-rule-based system has three input features namely object size I 1 , pixel distribution outside iris area I 2 , and pixel distribution inside iris area I 3 . The object size is the total pixels within the object in the image. Since the size of image is 32 × 32 pixels, the maximum total pixel that an object can take is 1024. In this paper, the term "iris area" is used to indicate the central (8 × 8)-pixel area of the image. The pixel distribution outside the iris area is defined as the total object pixels which are not located at the central area of the image. The pixel distribution inside iris area is defined as the total object pixels that are located at the central area of the image. Figure 4 illustrates the image used in this paper and the region of iris area and the region outside iris area. Each input feature is expressed using three membership functions namely small, medium, and big. The membership functions such as small and big are expressed using trapezoidal curve. For medium membership, a triangular curve is used. The output, object preference O, has three triangular curve memberships. Table 1 shows the inputs and the output of the fuzzy-rule-based system. The defuzzification is performed using centroid method.
A total of 27 rules are derived for this system. The rules are based on certain observations such as human visual consideration and also from the experience with the blind person. Since NAVI system is to be used by human blind, it is necessary to consider human preference regarding the selection of object of interest in the image. The first property is that if human concentrates on a particular object, other objects that surround the object of interest has less preference. The background goes a little out of concentration and hence is less focused. If there is only one object in the scene, the object would be detected as high-preference object regardless of the size and the position of that object. The objects can be detected before the object features are extracted. For this condition also, it is not important to evaluate the attributes of object features. Thus this condition can be directly evaluated without using the fuzzy-rule-based system.
The second property is based on the fact that the image in the real world usually contains more than one object. For this property, the fuzzy-rule-based system is essential to evaluate the attributes of object features. To provide a collisionfree navigation system, the size and the location of object are considered as important features. In this case, a bigger object is more important than a smaller object. Apart from that, the object which is located at the centre of sight is considered more important than objects which are located away from the centre of sight. Another important note is that as the blind person gets nearer to any object, the size of object gradually becomes larger. All the above discussed conditions are taken into consideration while developing the fuzzy rules. Some of the fuzzy rules are given as follows.
(i) Rule 1. If I 1 is small, I 2 is small, and I 3 is small, then O is low. (ii) Rule 3. If I 1 is small, I 2 is small, and I 3 is big, then O is high. (iii) Rule 10. If I 1 is medium, I 2 is small, and I 3 is small, then O is low. (iv) Rule 11. If I 1 is medium, I 2 is small, and I 3 is medium, then O is medium. (v) Rule 19. If I 1 is big, I 2 is small, and I 3 is small, then O is medium. (vi) Rule 21. If I 1 is big, I 2 is small, and I 3 is big, then O is high.

Intensity assignment
The result of the fuzzy-rule-based system produces three outputs which are low, medium, and high preferences. These outputs are referred for assigning the objects with different grey intensities. Dark grey intensity is assigned for a lowpreference object. A medium-preference object is shaded into light grey intensity and a high preference into white intensity.

Testing
In experimentation, 200 colour images have been tested to evaluate the proposed methodology. The testing is done offline and online. The result of each proposed stage in image processing methodology is shown in Figure 5. Figures 5a  and 5b show the results of proposed methodology for indoor images. In Figure 5a, four objects with different sizes are shown. The respective fuzzy output images are shown in the sixth column. From the output, one object is highlighted with high intensity and others with low intensity. Figure 5b shows another indoor image. In this figure, three objects can be detected and object in the centre of image has high preference. Other objects have low preferences. Figures 5c and 5d illustrate the results of proposed methodology using outdoor images. In Figure 5c, only one object is detected and its edges are shown in third column. Using the edge detection, the line on the floor is also detected. By eliminating the extra edges and enhancing the object region, the output image shows only the object and the background. Since only one object is detected, this object is highlighted with high-level intensity. In Figure 5d, there is one object in the centre of image and the other at the left side of the image. The edge image produces complex edges due to the colour pattern on the floor. However by eliminating edges and enhancing the object region, the shape and size of the objects can be inferred. Using the fuzzy rules, the object in the centre of image is given a high preference and the other a lesser preference.

STEREO ACOUSTIC TRANSFORMATION
The final processed image matrix I p has to be transformed into sound patterns. The frequency or pitch of the human  audible range is from 20 Hz-20 kHz. It is reported, however, that the human auditory is more sensitive in frequency range of 20 Hz-4000 Hz [17]. Since the human auditory system is more sensitive for discrimination in the low-frequency range rather than the high-frequency range, the frequency band is selected to be in the lower side of the frequency range. The vertical position of the image pixel is inversely related to pitch and the pixel intensity is converted into loudness of the sound. The frequency variations in the vertical position are designed to be audibly differentiable. The range of frequency for the sine wave sound generator is set at F L = 150 Hz and F H = 4000 Hz. This range and increment of frequency are selected by one of the blind volunteers so that he/she is comfortable with the repeated sound without the deterrence of the environmental sounds. Such specification seems to be fitting to other volunteers as well. Let (i) f 0 be the fundamental frequency of the sound generator, (ii) G a constant gain, (iii) F D the frequency difference between the adjacent pixels in vertical direction.
The changes in frequency corresponding to (i, j)th pixel in the 32 × 32 image matrix is given by where "i" is the row number = 1, 2, 3, . . . , 32. f i is the frequency of the sine wave for pixels in row "i" and is represented by In the proposed system, the frequency is linearly varied by maintaining F D as a constant. The generated sound pattern is hence given by where (i) S( j) is the sound pattern for column j of the image, (ii) t = 0, . . . , D, where D depends on the total duration of the acoustic information for each column of the image, (iii) ω(i) = 2π f i , where f i is the frequency corresponding to row, i.
The range {i = 1, 2, 3, . . . , 32; j = 1, 2, . . . , 16} indicates one half of the image. The sound patterns created from the left half side of the image is given to the left earphone and sound patterns of the right half side to the right earphone simultaneously thus creating a stereo acoustic transformation. The scanning is performed from leftmost columns towards the centre and from rightmost columns towards the centre. High-frequency band of sound signals for circle in the right earphone with lower amplitude. High-amplitude low-frequency signals for bottom rectangle in both the earphones for full duration.

TRAINING
The developed scheme of stereo acoustic transform was tested on a visually handicapped volunteer. The sound patterns from the real-time images are initially complex to understand and to categorize. For example, in learning Braille codes, the blind individuals have to undergo intensive and systematic courses. In a similar way, to start with the training of sound from the NAVI, it would be appropriate to first train the blind user with simulated images. The training procedure should create an interest and involvement in the blind volunteers. They should feel more and more confident as they put in more attention towards using the system. As a systematic procedure, the blind volunteer is first trained with the sound produced by the simulated images developed in Microsoft Windows paint. Initial training is started with the shapes like square, triangle, circle placed in different horizontal and vertical orientations in the image frame. The blind volunteer was asked to carefully listen to the sound. The logical meaning such as the shape of objects and their orientation in the image frame were explained to them in each training session. Figure 6 shows some simple simulated images with corresponding sound descriptions used in the initial stages of training. Figure 7 shows a set of test images with corresponding sound descriptions used for later stages of training. After a good level of training, the blind volunteers were able to identify complex simulated images, the objects in indoor environment and the objects in simple outdoor environment. The volunteers were able to walk along the corridor with restricting obstacles. Slowly moving objects and their directions of motion were also inferred by the blind with the sound produced from the NAVI system. For understanding complex outdoor environments from routine life, the blind need continuous training and a long experience with the system. The efficiency of the blind in perceiving the objects is found to be increasing with continuous training. In this research, information regarding depth of the object is not considered, and it can be developed using stereo cameras. However in the single camera NAVI, by comparing the sound patterns from relative distances between the blind person and the object, information regarding distance of objects can be manipulated by the blind person with experience.  Figure 7: Examples of real-life images and the description of their sound patterns. (a) A band of medium-to-low frequency of sound with low amplitude from the left earphone, followed with a band of high-frequency sound with lower amplitude. A band of high-tomedium frequency sound with low amplitude from right earphone, followed with a band of medium-to-low frequency band with high amplitude. A band of high-frequency sound signal with low amplitude is inferred in the second half of time duration. (b) A band of high-to-medium frequency sound signals in the left earphone with lower amplitude in the first half of time duration. This is followed with a band of low-frequency sound signal with high amplitude until the end of time duration. A band of high-to-medium frequency with high amplitude sound signals in the right earphones in the second half of the time duration.

CONCLUSION
The main objective of this paper is to identify objects in a captured image. Objects are identified by their closed boundaries. Several approaches of object extraction involved in this paper include the edge detection, the edge-linking, and the noise removal. Once the objects are extracted, a fuzzy rule base is implemented for object identification. In human vision system, often the object of interest is located at the centre of the sight. The proposed fuzzy-rule-based methodology provides a preference to each object in the image. The processed image is sonified using a stereo sound procedure.
The developed sonification procedure was tested on visually handicapped volunteers. With continuous training, the blind user can identify the location of objects through the sound pattern produced from the processed image.


extfieldsofstudy: Biology Physics Medicine

text:
Statistics of infections with diversity in the pathogenicity

The statistics of outbreaks in a model for the propagation of meningococcal diseases is analyzed, taking into account the possibility that the population is fragmented into weakly connected patches. It is shown that, depending on the size of of the sample studied, the ratio between the variance and the mean of infected cases can vary from one (Poisson statistics) to the inverse of the infection rate.

Introduction.
The meningococcus is a major cause of meningitis and septicaemia. Despite this, infection with the meningococcus is mostly harmless and only rarely leads to disease. Transmission of the disease is almost exclusively through asymptomatic carriers of the disease. A predominant feature of the epidemiology of meningococcal disease are outbreaks of variable scale and duration. The meningococcal population is genetically highly diverse. We have shown, using a mathematical model, that heritable diversity with respect to pathogenic potential can lead to disease outbreaks [1,2,3].
Meningococcal disease is a a notifiable disease in many countries. Therefore there exist extensive data sets on the incidence of meningococcal disease. The analysis of meningococcal disease data is problematic because the number of asymptomatic carriers at any time, the variable that is probably of most interest, is normally not known because transmission of the pathogen takes place almost exclusively through asymptomatic carriers. Therefore key epidemiological parameters are difficult to estimate and methods that are standard in epidemiology, such as outbreak reconstruction through contact tracing, can not easily be applied. For this reason outbreaks of meningococcal disease are difficult to reconstruct and to detect.
In this paper we will investigate the statistical structure of an epidemiological model to infer the underlying disease process from data on the number of cases of disease. Such insights have been applied in the analysis of meningococcal disease data [3]. Here we will investigate the validity of the assumptions made for these inferences and study how the variance in the number of cases of disease depends on the structure of the population.

The SIRYX model.
We study the SIRYX model, considered in [1,2,3]. The model is an extension of the SIR model [4]. There are two types of infected individuals, I and Y . The Y 's are generated by mutation from the I's at rate µβ. For simplicity we assume that the back mutation rate Y → I is nil. The Y population can develop disease at rate ǫβ. The parameter ǫ is the pathogenicity: the probability to develop disease upon infection. We define the number of individuals which suffer the disease X. We further simplify the model by assuming that these individuals are removed from the population. The mean field equations are: The only difference with respect to the model studied in [1,3] is the introduction of a the rate δ at which the X individuals are removed from the population (see below). This rate implies, that, in the long run, the only stationary situation is the conversion of all individuals into the X type, and their eventual disappearance. We will study here quasisatationary situations which arise when δ, ǫ ≪ 1.
Following [1], we consider that the system is near its stable point when µ = 0 and Y = 0. The remaining parameters at the fixed point are: Assuming that the fixed point values for S and I do not change much for small µ, we can define a simple birth-death model for the variables Y and X. We define p(Y, t) = ∞ X=0 p(Y, X, t), as the probability of finding the value Y at time t. This function satisfies: where we have defined the death rate, a = γ, birth rate, b = β(1 − ǫ)S * /N p and rate of creation of a new individuals by mutation, c = βµ(S * /N p )I * .
We generalize this equation to the case of a system divided into M patches.
The main difference is that the birth probability has to be divided into the probability that the contagion is to another individual within the same patch, which we still define as b, and the probability that the contagion leads to a new individual of type Y in another patch, b ′ . The total infection rate remains Note that in this equation c is the mutation rate within one patch. The total mutation rate is Mc. When b = b ′ we recover the limit of a well mixed population, while for b ′ = 0 the patches are decoupled.
From eq.(4) we can calculate the ensemble means of different quantities. The details of the calculations are given in the Appendix. The results are: All these quantities vanish when the mutation rate is zero, c = 0.
The net growth rate is aǫ The number of infected cases appear with rate X ′ i = aǫY i .
We now calculate the number of infected individuals, X i . We study first the case of a single population and a single variable X. The infected individuals are generated from the Y 's at rate aa − b − (M − 1)b ′ . In order to calculate X in a single population, we use as unit of time a −1 , and assume that the death rate of the X's is δ. We write the mutation rate c = aγ. then, we can write: where we have used as the unit of time a −1 , ǫ is now the rate of conversion from Y into X, δ is the death rate of the X's, and γ = c/a is the mutation rate from I into Y . Using the techniques described in the Appendix, we can write: In a stationary state the right hand side of these equations is equal to zero, and we find: We substitute the first and third of these equations into the second, so that: From eq.(6) we also obtain Y = γ/ǫ. Inserting this result into eq.(9), we have: This equation relates the variance and the average of X. When the mortality rate is very high, δ ≫ ǫ, we have: The ratio approaches a constant of order unity, and the process seems to have Poisson statistics. This is reasonable, because there is an approximately constant reservoir of Y individuals which can lead to an X individual which disappears quickly, and the distribution of X cases is not influenced by the fluctuations of Y .
A more interesting regime arises if δ ≪ ǫ and ǫ ≪ 1. Then, the r.h.s. in eq.(10) is dominated by the third term, because ( Y 2 − Y 2 )/ Y ∼ ǫ −1 . We find in this case: This result is the basis of the following section. Note that when δ = 0 the value of X i increases linearly with time.

Size effects.
Using the results in the Appendix and eq.(12) we find (for M ≥ 2): On the other hand, for the entire system we obtain: The linear relationship between the variance and the mean is discussed in detail in [3]. For isolated patches, b ′ = 0 and b/a = 1 − ǫ. As expected, the local and global values, eq.(13) and eq.(14) coincide, giving a ratio equal to 1/ǫ.
In a well mixed population, we have b ′ = b, the total birth rate is b tot = Mb, and (Mb)/a = 1 − ǫ. Then, we find: For a small subsystem of a well mixed population (M ≫ 1/ǫ), we have VarX i / X i ≈ 1. This ratio would imply that the process is due to random mutations with Poisson statistics. An analysis of the total variance, however, gives a rather different result. For large (but artificial) subdivisions of the well mixed system, Mǫ ≪ 1, and VarX i / X i ≈ 1/(Mǫ).
It is interesting to analyze the situation in which populations of size N below some size N * are part of a well mixed population of size N * , while larger populations can be considered as isolated. made up of smaller, decoupled populations of size N * . Then, for populations N ≤ N * we can use eq.(15) with M = N * /N = X / X * ( X * is the value of the mean of a population of size N * ), while when N ≥ N * we can use eq.(16). The variance can be written as: . Eq.(17) interpolates between a Poisson like regime for N ≪ N * to a 1/ǫ ratio between the variance and the mean for N ≥ N * . A sketch of the results is shown in Fig.[1]. used here imply that the coupling between different parts of the 5 Acknowledgements.
One of us (FG) is thankful to the Royal Society for a travel grant, and to the Royal Holloway for hospitality. F. G. also acknowledges financial support from grant MAT2002-0495-C02-01, MCyT (Spain). V. A. A. J. and N. S. acknowledge financial support from The Wellcome Trust Grant 063143. From eq.(4) one finds the equations: where K is a constant determined by the initial conditions. We define: These quantities satisfy: At long times, we find:


A Review Of Internet Gateway Discovery Approaches For Mobile Adhoc Networks

A mobile ad hoc network (MANET) consists of wireless mobile nodes without having a fixed infrastructure. The communication between these mobile nodes is carried out without any centralized control. The communication among the nodes within the infrastructure less networks is done through some routing protocol. But whenever any mobile node want to communicate a node in a network that is outside the ad hoc network such as internet, there should be an appropriate mechanism for establishing this connection. Gateway discovery is a fundamental process in connecting MANET with the internet. A mobile node can connect to the internet by discovery of some specialized nodes called as gateway nodes These Gateway nodes act as a bridge between the mobile ad hoc networks and the internet. The basic aim of the gateway discovery approach is to modify the route discovery process so that it is not only used for discovery of destination mobile nodes but also the gateways. In this paper we are going to present a review of various gateway discovery approaches which are used for establishing the interconnection of mobile ad hoc networks and internet.

INTRODUCTION
A mobile ad hoc network [1] is organized as the collection of various mobile nodes. It is formed spontaneously in the areas where establishing an infrastructure network causes delay in the work as well as enhances the cost. These areas include flooded areas, earthquake affected areas, etc. As the nodes are mobile there is not any fixed infrastructure of MANET. The mobile ad hoc network is composed of portable nodes, notebooks and palmtops. This portability brings a significant issue of mobility. This is a key challenge in ad-hoc networks. The nodes in the mobile ad hoc networks are constrained to use limited resources. They have low battery power, limited user interface and low quality display. The nodes in the mobile ad hoc networks can communicate with one-another through the use of some routing protocol which decides which way to route the information from source to destination. This communication among the mobile nodes occurs for retrieving the essential information they need. When a mobile node wants any information outside the mobile ad hoc network in which they are present, they have to use some mechanism other than routing protocol. The communication between mobile ad hoc networks and the internet occurs through some special approach called as gateway discovery. The gateway [2] acts as an interface between the mobile ad hoc network and the internet. As the nodes are mobile the topology of the MANET changes frequently. Therefore managing permanent connection to the internet is a critical issue in mobile ad hoc networks. Gateway eliminates this difficulty by taking over all the communication between MANET nodes and the internet. All the incoming and outgoing traffic between the MANET and internet passes through the gateway that forwards it to the appropriate destination. Different mechanisms have been proposed to integrate MANETs and the Internet. The communication between MANET and internet is shown in figure1.

Protocol Stack
Whenever any node in the MANET wants to send the traffic towards an internet node then it must be transmitted via the gateway. So the gateway has to translate between these two different protocols and must understand both. Therefore, it needs to implement both the MANET protocol stack and the TCP/IP suite [22]. The protocol stack for the MANET-INTERNET integration is as following.

Gateway Forwarding
Internet gateway forwarding [33] is used to forward traffic within the MANET, out of the MANET to the Internet, or from the Internet to the MANET. It can be categorized into inter-MANET and intra-MANET forwarding strategies. The inter-MANET forwarding strategies uses two main methods, default routes and tunneling.
Default routes [34] are used by the default next-hop to send packets to those nodes which do not have any explicit entry in their routing table. Usually, the default route is used to forwards packets towards an IGW, where packets are further forwarded towards the destination in the Internet.
Tunneling [35] is the IP-in-IP encapsulation technique which is used to get traffic into and out of the MANET. The outer IP header is for the tunneling connection between the source MANET node and the IGW, while the inner IP header is for the connection between the source MANET node and the destination.

Handoff In Manet-Internet Connectivity
A node performs a handoff if it changes its IGW while communicating with a correspondent node (CN) in the Internet [36]. In conventional mobile networks, e.g., WLANs, the quality of the wireless link between a mobile node and the neighboring access points (APs) determines to perform handoff from one AP to another. The performance of these types of handoffs depends on the mobility management protocol in the access network. In MANETs, on the other hand the situation is quite complex because some of the nodes do not have a direct wireless link to an AP, but they are connected via other intermediate nodes. Thus, they cannot initiate handoffs that are based on the link quality to the AP. Rather, the complete multi-hop path to the AP, which serves the current IGW, must be taken into consideration. A handoff can occur only if an ad-hoc node itself or any intermediate ad hoc node moves and breaks the active path. In general, if the path between an ad-hoc node and the IGW breaks and there is no other path to the same IGW, the ad-hoc node has to perform IGW discovery to establish a new path to another IGW.
Multi-hop handoff schemes can be classified into forced handoff and route optimization-based hand off [37].Forced handoff occurs when the path between the source or destination mobile node and the IGW is during data transmission due to the movement of the MANET node. So, a new path to the internet has to be set up. Route optimization-based hand-off is a handoff that results from route optimization. If the source or target MANET node observes that a shorter path to the internet becomes available while communicating with a corresponding node, the active path will be optimized. In case the shorter path goes via a different IGW, a route optimization-based handoff occurs.

TAXONOMY OF GATEWAY DIS-COVERY APPROACHES
There have been several approaches for gateway discovery. One such classification is given as following [3].

Proactive Gateway Discovery Scheme
This scheme [4] makes use of a special message called as gateway advertisement [5]. The Gateway discovery is initiated by the gateway itself. The Gateway broadcasts a gateway advertisement message which is rebroadcasted after a certain time interval called as advertisement interval. The time between two intervals is chosen in such a way that the network is not overwhelmed by the traffic. The nodes which are in the range of the gateway receive the advertisement message. On receiving the message the nodes which don"t have route to gateway create a route entry for it in their routing table. Those nodes which have a route to gateway update their routing information.

Reactive Gateway Discovery Scheme
In reactive gateway discovery [9] scheme the nodes demand route to the gateway reactively. Whenever any node wants to fetch some information from the internet, it broadcasts a Route Request message (RREQ) to the IP address of a group of all gateways in the mobile ad hoc networks using ALL_MANET_GW_MULTICAST address. This message is received and replied only by the gateways. The intermediate nodes do not to reply to this message on receiving such message they just rebroadcast them. The advantage of this approach is that control messages are generated only when a mobile node needs information about reachable gateways. On receiving RREQ message gateways reply source node with the corresponding route reply (RREP) messages by uni-casting them. After that mobile nodes can access the internet easily as the connection has been established.

Hybrid Gateway Discovery Scheme
The hybrid gateway discovery scheme [13] is the combination of both proactive and the reactive approaches. Firstly the gateway broadcasts the Gateway Advertisement message proactively to an area confined to a limited number of hops which is called as the TTL value of the message. The TTL is set to advertisement zone so that the advertisement message can be forwarded only up to this maximal number of hops through the ad hoc network. This area is called as the proactive zone. The nodes that are outside the proactive zone establish connection to the gateway reactively. The format of gateway advertisement message is as following.

Adaptive Gateway Discovery Scheme
Information is easily provided by the gateway only if it is routing those data grams that it would receive anyway. Adaptive gateway discovery algorithm is based on this idea. In this approach number of hops of its active source location is maintained.

CURRENT PROPOSALS
In this section we present a summary of various gateway discovery proposals which have been proposed by various researchers.  [8] proposed a protocol in which each mobile host maintains a routing table that stores the number of hops, and the sequence number for all the destinations. The routing table updates may be timedriven or event-driven. The interval between the two updates is known as the periodic route update interval. In DSDV the low packet delivery ratio is because of usage of stale routes due to broken links. The existence of stale route does not imply that there is no valid path to the destination. The packets can be forwarded through other neighbors who may have routes to the destination. When an intermediate link from the host say "S" to the destination say "D" breaks, the Effective DSDV protocol creates a temporary link through a neighbor which has a valid route to the desired destination. The temporary link is created by sending one hop ROUTE-REQUEST and ROUTE-ACK messages..
In this section we briefly describe the scheme of K.Palani et al. [17] based on the maximal source coverage algorithm. Initially, the gateways do not send control advertisements (GC REP) periodically. When a node needs a route to the Internet, it issues a GC REQ message which is flooded throughout the network. The gateways present in the MANET receive the GC REQ and send a GC REP message in unicast to the originator. It contains the subnet prefix which is later on used by the node to auto-configure its global IP address. Reverse routes to the node are created as the GC REQ message is being forwarded, and routes to the gateway when the GC REP is sent back. So, the ad hoc node can start sending data traffic to the internet after configuring its global address. Data packets addressed to nodes in the internet pass through a gateway. Thus, it can collect the number of hops from itself to every source. The TTL of the GC REP messages which are periodically flooded is set to the distance to the farthest source. The motivation behind this is that active sources are covered by the proactive sending of control messages, and therefore we can avoid the reactive route discovery when the route to the Internet is lost, which is very expensive in terms of control overhead.
Khaleel Ur Rahman Khan, et. al. [6] proposed eDSDV or extended DSDV protocol which is based on dynamic buffer management strategy instead of the fixed size buffer technique. With this approach the chances of discarding the packets are very low. In case of broken links the RREQ packets are broadcasted with a hop count of two rather than one. Performance of the conventional DSDV algorithm fades because of increase in the network size and the rates of mobility. This algorithm improves various performance metrics of the DSDV protocol such as packet delivery ratio, end-to-end delay and the number of dropped packets. When a next hop link from the source to the destination breaks, the proposed protocol creates a provisional link through a neighbor which has a valid route to the desired destination [7]. The provisional link is created by sending two hop route-request and route-acknowledgement messages. This mechanism is explained in figure 5.
Harpreet Kaur Sandhu et al. [10] proposed AODV+, an enhanced version of the AODV protocol. In the traditional AODV protocol the mobile node initiates the route discovery process by broadcasting the route request message (RREQ) with its own IP address as the source IP address and destination IP address of an internet host. When an intermediate node receives the RREQ packet, it searches its routing table for a route on the way to the destination i.e. the internet host.  [11] is useful because if one of the path fails the data can be routed through another path .It consists of two phases. One is the request phase and the other one is the reply phase. In request phase the source node broadcasts a route request (RREQ) packet to its neighbors and it is broadcasted until it reaches for the destined node. In the Reply phase the route reply (RREP) is sent to the source by the destination. This way the route cutoff problem is solved.
In MANET, nodes move at random speed and direction that result in a dynamic topology. Safdar Hussain Bouk et. al. [14] proposed a gateway discovery scheme in which movement of each node is considered as a sequence of random length intervals called epochs during which a node moves in a direction θ at a constant speed v. In this situation the link availability period between two nodes is varying at different time intervals and the path availability period between two nodes that are not immediate neighbors of each other, is equal to the minimum link availability period between intermediate nodes in that path. Li represents the minimum link availability period and lu is the link availability period between two neighboring intermediate nodes in a path from a source MANET node (S) to the gateway node and Li=min{lu}. Almost all protocols just compute the traffic load of a gateway node and based on that information they select gateway. The residual load capacity of a path is the minimum available load capacity at any node, including intermediate nodes and the gateway node, in that path. The overall residual load capacity Ci of path i is computed as Ci=min{cj} where cj denotes the residual capacity of the intermediate nodes in the route including gateway node. Latency is the propagation delay plus processing time of a packet from one node to another node..

Fig 6: Zone Division in Hybrid MANET
The figure indicates that zone is divided through the propagation of gateway advertisement (GWADV) messages.
Lee et al. [53] proposed a hybrid gateway discovery protocol that requires a source routing protocol in the Ad Hoc network. A gateway sends out new advertisements only when it detects any topology change in the Ad Hoc network. Moreover, advertisements are only forwarded to nodes that are either connected to the Internet or that have actually moved. Advertisements are only generated if the ratio between the number of Internet joining nodes and the number of advertisement forwarding nodes exceeds a threshold. The traditional advertisements are broadcasted with a relatively long time interval. They rely on a source based routing protocol, that obstructs the application to particular type of routing protocol.
Lin Zhuang et al. [15] proposed a hybrid gateway discovery approach. An Internet gateway periodically broadcasts a GWADV. The nodes that receive GWADV create or update reverse route entries for the IGW and maintain such routes as default entries in their routing tables. MNs that cannot receive GWADV issue Route Request for IGW packets (RREQ_I) to discover gateway reactively. To avoid unidirectional links and meanwhile to relieve broadcast storm, Shen improves the original hybrid gateway discovery scheme by extending AODV hello messages with local connectivity information. Each MN maintains a Neighbor Node List (NNL) to record its set of neighbors (i.e., all nodes from which it can hear hello message) and it then appends this set in its coming HELLOs. When a node receives a hello message from a neighbor, it will add it into its NNL and if it is not present in the neighbors set in this hello message, the node can conclude that it is the sink of a unidirectional link between them and mark this neighbor as asymmetric neighbor in NNL. Otherwise the neighbor will be marked as symmetric neighbor.
Wakikawa et al. [20] proposed an approach to global Internet connectivity over the IPv6 MANET environment, where mobile nodes in the Ad Hoc network are configured with new globally routable IP addresses based on the neighbor discovery protocol (NDP) of IPv6. The gateway advertisement message contains the global IPv6 address of the gateway, the network prefix advertised by the gateway, the prefix length and the life time associated with this information. They specify a stateless auto-configuration mechanism, which is based on network prefixes advertised by Internet gateways. The nodes concatenate an interface identifier to one of those prefixes in order to generate the IP address.
Mari Carmen Domingo et al. [16] proposed an adaptive gateway discovery approach that has been mainly designed to reduce congestion problems in an ad hoc network and that helps real-time applications to maintain their QoS parameters even in the presence of high traffic. This approach defines a transmission range where the gateways periodically send advertisement messages and they are propagated around a limited zone (a certain number of hops away from the gateway). If a mobile node wants Internet connectivity and it is outside the gateways transmission range and the propagation zone of the gateways advertisements, it should broadcast a message to the group of gateways in the ad hoc network. The gateways should respond sending back a reply and the routing protocol of the mobile node selects the reply of the gateway which offers the best route towards internet in terms of number of hops accordingly to the normal functioning of the AODV routing protocol.
Broch et al. [19] proposed a solution for the integration of MANET with Mobile IP using a source routing protocol. It contains a border router, which has two interfaces. The communication within the ad hoc network is done through the DSR protocol. While its interface connected to the Internet is configured to use normal IP routing mechanisms. Mobile nodes in an Ad Hoc network are assigned home addresses from a single network. The nodes within range of the foreign agent act as gateways between the Ad Hoc network and the Internet. As a reactive approach, foreign agent discovery is only done when required. Traditional IP routing is used on the Internet side while within MANET DSR protocol is used. Foreign agents are responsible for connecting the Ad Hoc network with the Internet.
In [38] F. D. Trujillo et al. proposed an adaptive gateway discovery scheme. In the proposals of proactive gateway discovery schemes, the interval of emission of MRA messages (Modified Router Advertisement) is fixed to a constant value T. This interval is dynamically configured in this approach. The optimal value of T depends on the network conditions such as the load, the node mobility, the number of traffic sources. Here, the gateway adjusts the T taking into account the number of received MRA messages which are retransmitted by the gateway"s neighbors. When the gateway receives various MRA messages from its , it means that all these nodes have updated the routing entry to the gateway accordingly. Additionally, when the number of neighbors is high, we may assume that most routes to external hosts are composed of few number of hops. It causes the routes to have a longer lifetime .In this situation, the T could be incremented. However, when the gateway receives few MRA packets from its neighbors, it must decrease the T to ensure that nodes keep a valid route to the gateway when they require to be connected to internet.
In [39] Rosenschon et al. proposed a proactive gateway discovery scheme which makes use of hello messages to connect the MANET node to the internet. The ad hoc routing protocol such as AODV uses HELLO messages for neighborhood management. The gateway will send two types of packets periodically which are advertisements and HELLO messages. Here, every node sends HELLO messages periodically with a time to live (TTL) of 1. The idea of this gateway discovery algorithm is that if a gateway uses HELLO packets for neighborhood discovery it does not need to send advertisements with a TTL of one additional to the HELLO messages. The advertisements can then be neglected and they may be substituted by special HELLO messages. Therefore, a flag was introduced to indicate that a special HELLO message was initiated by a gateway node and not a normal node. This flag was called the I-flag and thus, the modified HELLO messages are called HELLO-I messages. Since the HELLO messages were derived from RREPs there are empty fields in the header that can be used for the additional purpose for this kind of gateway discovery.
In this section we describe an adaptive gateway discovery mechanism proposed by Pedro M. Ruiz et al. [40] being that is able to dynamically change its proactiveness or reactiveness and can reduce the overhead of the gateway discovery. Here we describe a new adaptive gateway discovery approach based on the dynamic adjustment of the TTL of GWADV messages. In this approach the TTL of the GWADV messages is used as the parameter to adjust depending on the network conditions. The higher the TTL value, the higher the overhead due to the periodic advertisement and the lower the overhead associated to the reactive discovery of the Internet gateways. That is, the higher the TTL the higher the proactiveness of the approach. When TTL is NIL then it corresponds to a totally reactive approach. While, when TTL is equal to NETWORK DIAMETER it corresponds to a completely proactive scheme.
Md. Asif Iqbal et al. [41] has proposed a hybrid gateway discovery scheme for internet gateway discovery. When a mobile node in the MANET wants to access the Internet, then it has to find a gateway. So, mobile node in this gateway discovery scheme looks in its routing table to find a default route i.e. a route to a gateway. If the mobile node finds a default route, it uses the route to send packets to the gateway i.e. to the Internet. However, if the mobile node does not find a route to a gateway in its routing table, it starts a gateway discovery process by broadcasting a gateway discovery w w w . i j c t o n l i n e . c o m (GWDSC) message in the MANET. While broadcasting the GWDSC message, the requesting mobile node sets an initial time to live (TTL) value for the message and starts a timer to wait for the reception of the gateway advertisement message from the gateways. When an intermediate node receives the GWDSC message it creates a reverse route entry for the requesting mobile node in its routing table and forwards the GWDSC message to its neighbors. In this way, a GWDSC message reaches one or more internet gateways in the network. The Gateway broadcasts a GWADV message when it receives the GWDSC message. The TTL value of the GWADV message is set equal to the distance of the gateway from the requesting mobile node. Robert Brannstrom et al. [42] proposed a proactive gateway discovery scheme that is used to connect multi hop ad hoc networks with the internet. This approach reduces the delay in the gateway discovery process. As the advertisements may arrive to a mobile host through multiple paths, it is important to keep track of the best path to each gateway. Here the Running Variance Metric (RVM) and Relative Network Load (RNL) are used as performance metrics to classify the traffic load of gateways in wireless access networks. RVM and RNL can be efficiently used for infrastructure networks and ad hoc networks. In this scheme the Mobile IP is extended to enable mobile nodes to support multiple care of addresses simultaneously. The extension improves the network connectivity by enabling the mobile host, the home agent and correspondent hosts to evaluate and select the best connection. This extension is to Mobile-IP is called as multi-homed IP.
Sun et al. [43] has proposed the integration of the Ad Hoc On-Demand Distance Vector (AODV) routing protocol and Mobile IP . It gives a technique for activating nodes within an ad Hoc network to acquire internet connectivity when one or more nodes is in direct transmission range of a foreign agent or an Internet Gateway Router. In this approach, an Ad Hoc network is connected to a foreign agent, which exhibits the similar working as an Internet gateway (IGW). Internet Gateway assigns a global prefix for the Ad Hoc network, which makes it possible for mobile nodes in Ad Hoc network to communicate with Internet. In integrating MANET and INTERNET AODV is used for route discovery and maintenance within MANET, while Mobile IP gives a way for mobile nodes to get care-of addresses.
Hamidian et al. [44] proposed an approach which provides internet connectivity to Ad Hoc networks by modifying the AODV routing protocol. An "I" flag is added as an extension to AODV, RREQ and RREP to locate the fixed node. If after one network-wide search without receiving any corresponding route replies, the mobile node assumes that the destination is a fixed node, which is located in the internet and thus delivers the packets through a gateway. All the three methods of gateway discovery for a mobile node to access the internet are based on the number of physical hops to gateway as the metric for the gateway selection.
Hossam El-Moshrify et al. [45] proposed a solution in which mobile nodes can access the internet via a stationary gateway node or access point. The impact of the mobile terminals speed and the number of gateways on the network performance are compared in this approach. In this proposal the mobile node uses no load balancing approach to efficiently discover an internet gateway.
C. Jelger et al. [46] proposed a proactive gateway discovery approach in which internet gateways periodically advertise their presence by flooding information (GW_INFO) messages. This proposal uses a restricted flooding scheme, to limit the overhead of the proactive gateway discovery. The prefix continuity ensures that every node shares the same prefix and each gateway only receives IPv6 data packets belonging to its prefix. A mobile node chooses one of the GW_INFO messages according to some metrics. Then the node configures an IPv6 address based on the advertised prefix and sends only the GW_INFO message including the selected prefix. However, if the approach is unified with a reactive routing protocol, then a node in the network must discover a route otherwise it causes a break of the connection because of the property of the reactive routing protocol. It uses a stateless auto-configuration mechanism, which is based on network prefixes advertised by gateways. The nodes concatenate interface identifier to one of those prefixes to generate the IP address. A mobile node selects the optimal route towards the gateway using one of the metrics such as distance, stability, or delay from all the gateway information messages received.
Bin et al. [47] proposed an adaptive gateway discovery scheme that can dynamically adjust the TTL value of GWADV messages. This protocol provides internet access to MANET mobile nodes using mobile IP .The protocol uses foreign agents to track and forward packets to and from mobile nodes. Foreign agent periodically calculates the average hops by RREQ_I message or registration request sent by mobile nodes requesting internet connectivity. So the transmission range of GWADV can be adjusted dynamically according to real time applications demand.
In this section we describe an adaptive gateway discovery protocol proposed by Alicia Trivino Cabrera et al. [48] The aim of this proposal is to adapt the interval of emission of MRA messages to the mobility and traffic conditions of the mobile ad hoc network. So lower overhead is obtained while the losses do not increase. This scheme is based on the number of Modified Router Solicitation (MRS) messages generated by the mobile nodes in an interval of time called the MRS_COUNT_INTERVAL. The number of received MRS messages indicates the mobility and the necessity of updating the routes to the Internet. In this scheme, they observed the expected behavior of mobile nodes when the mobile nodes send the MRS messages to predict how many requests are expected to be received by the Internet Gateway in the next interval. This decision is taken based on the information about how the network is behaving at the present time and how it has behaved in past. w w w . i j c t o n l i n e . c o m Bok-Nyong Park et al. [49] proposed an adaptive gateway discovery approach for ubiquitous connectivity of ad hoc network with internet. This approach improves the load-balancing feature. After the routes are discovered to gateways, ad hoc mobile nodes should be able to select one Internet gateway providing the best internet connection. In the Internet gateway selection, this approach uses method to distribute data packets into different gateways while keeping low offered load.
Jonsson et al. [50] proposed a method, called MIPMANET based on AODV. It provides internet access by using tunneling and Mobile IP with foreign agent care-of addresses. Mobile nodes that want internet access register with a foreign agent and tunnel all packets destined for the Internet to the registered foreign agent. The packets destined for the internet are tunneled to the foreign agents, which in turn forward the packets to the destination in the internet. The hosts that do not want to access internet see the Ad Hoc network as a standalone network. The tunneling approach also enables MIPMANET to include the default route concept into on-demand routing. The Ad Hoc on demand distance vector routing protocol AODV is used within the mobile Ad Hoc network and delivers packets between mobile nodes and foreign agents. MIPMANET allows a visiting node to switch from its current foreign agent to a new one, a phenomenon known as handoff, only if it is at least two hops closer to the new one. It utilizes a new algorithm, called MIPMANET Cell Switching (MMCS), to determine when mobile nodes in the Ad Hoc network should register with a new foreign agent. In this solution, it is assumed that a mobile node that wants access to inernet has been assigned a home address that is valid on the Internet.
Ratanchandani et al. [51] proposed a hybrid gateway discovery approach to discover gateways that limits the effects of broadcast overhead. In this approach AODV and two Mobile IP foreign agents are used to interconnect MANET and the Internet. However, the TTL of the foreign agent"s advertisements is limited to only a few hops. Thus, only mobile nodes that are close to one of the foreign agents receive the agent advertisements. Nodes that are further away have to solicit advertisements reactively. Intermediate nodes are allowed to reply on a solicitation with agent advertisements and to eavesdrop and cache agent advertisement information that is sent by unicast to the requesting mobile node. The performance of this approach depends on the Time-To-Live (TTL) value, which is set for a particular scenario and network condition under considerations. In order to switch between foreign agents, the MIPMANET Cell Switching algorithm is used.
Ghassemian et al. [52] proposed an approach in which the scalability of both proactive and reactive is compared with respect to the number of Internet Gateways. The fixed access network together with the Ad Hoc network creates a multi hop access network. The hybrid Internet gateway discovery approach is also compared that shows the average packet delay and the packet delivery ratio. This approach is beneficial because the packet delivery ratio is higher and the signaling overhead is also lesser for more number of gateways.
In [18], Ammari et al. proposed a mobile gateway based on three-layer approach using both Mobile IP protocol and DSDV Ad Hoc routing protocol. The first layer contains Mobile IP foreign agents; the second layer includes mobile gateways and mobile internet nodes, which are one-hop away from Mobile IP foreign agents; the third layer has all MANET nodes and visiting mobile internet nodes that are at least one-hop away from mobile gateways. The second layer is to provide internet connectivity to MANET nodes and, thus to help establish interaction between MANET nodes and the Internet. Mobile gateways are powerful MANET nodes and are designed in a way to use both Mobile IP protocol when they communicate with the Internet. The DSDV protocol is used for routing within the MANET. The integration framework considers using some border MANET nodes to connect the rest of MANET nodes to the Internet. These MANET nodes are referred as mobile gateways.

COMPARISON AMONG EXISTING INTEGRATION APPROACHES
In this section we present a comparative analysis of various protocols discussed above.

CONCLUSION AND FUTURE SCOPE
The aim of gateway discovery is to provide the mobile nodes connectivity to the internet. Various protocols have been proposed for this purpose. Each of them tries to improve the efficiency of the internet access through the gateway node. The protocol which should be chosen for gateway discovery should improve the packet delivery ratio and should minimize the latency of data transmission from internet to mobile ad hoc networks and vice-versa. The most popular gateway discovery protocol which is being used now a days is the adaptive gateway discovery protocol. In near future various enhancements to this approach will arrive. We are working to improve the efficiency of gateway discovery process to improve the network throughput and reduce congestion.

LATEST RESEARCH TRENDS
Gateway discovery is a new and emerging area in the field of mobile ad hoc network. Various new protocols on gateway discovery are being proposed in every shorter span of time. Here we give a list of technologies which are popular now a days. w w w . i j c t o n l i n e . c o m


© 2005 Science Publications Measuring the Function Points for Migration Project: A Case Study

In this study, we extend the study of Function Point Analysis (FPA) for the measurement of source code based migration project using the migration tooling options. FPA is an objective and structured technique to measure software size by quantifying its functionality provided to the user, based on the requirements and logical design. It is noticed that the procedure for the above measurement is not fully described in FPA method. Hence, the same estimation concept has been applied to an in-house project on an experimental basis at a leading software development organization. The yielded results are compared with FPA for the re-engineering project.

INTRODUCTION
One of the most important activities in the early stages of software development is estimation. Size of the software [1] , be it Function Points or Lines of Code, plays a pivotal role in this process and forms the base for deriving a number of metrics to measure various aspects of the software throughout the development cycle. Hence, measuring the size of the software becomes critical though many other sizing measures such as objects, classes, modules, screens, programs and so on. Accurately predicting the size of the software has always troubled the software industry over the years. Function Points are becoming widely accepted as the standard metric for measuring software size.
We sketch briefly for existing software systems [2] and in particular legacy systems, where the functional documentation is often missing or obsolete. Hence, the standard Function Point Analysis (FPA) is not applicable for the sizing of enhancement projects (the implementation of change requests) as back firing is not applicable either it only refers to the complete software system and its precision is not sufficient to size individual enhancement projects. A method to perform FPA based on the source code is proposed. This method is instantiated for COBOL and JCL (Job Control Language). It can be integrated into the maintenance process such that each change request is defined in terms of the objects from the Function Point (FP) conceptual model. In this way, the sizing of a change request is obtained for free.
It is demonstrated that simplified way of the IFPUG (International Function Point Users Group) function points based on the simplification ideas suggested by NESMA (Netherlands Software Metrics Association) to estimate the size of management information systems [3] . He analyzed nearly twenty web applications using the simplified method, whose result were very close to the ones using the IFPUG detailed method. The simplified method is based on assigned low complexity to all the data and transactional functions. Thus, when data and transactional functions are identified, their complexity is determined automatically for Web based applications [4] .

Function points analysis:
Function Point Analysis is a well-known method to estimate the size of software systems and software projects [5] . This technique breaks the system into smaller components so that they can be better understood and analyzed. Function Point count can be applied to development projects, enhancement projects and existing applications as well. Function Point Analysis is expected to obtain the following objectives [6] : * Determine the type of Function Point count. * Determine the application boundary * Identify and rate transactional function types to calculate their contribution to the Unadjusted Function Point count (UFP). * Identify and rate the data function types to calculate their contribution to the UFP. * Determine the Value Adjustment Factor (VAF) by using General System Characteristics (GSCs). * Finally, calculate the adjusted Function Point count.
There are 5 major components of Function Point Analysis which capture the functionality of the application. These are External Inputs (EIs), External Outputs (EOs), External Inquiries (EQs), Internal Logical Files (ILFs) and External Interface Files (EIFs). First three are treated as Transactional Function Types and the last two are called Data Function Types. Each of the components of Function Point Analysis is explained in brief in the following sub-sections [6][7][8] .

External input (EI):
External Input is an elementary process in which data crosses the boundary from outside to inside. This data may come from a data input screen or another application. The data may be used to maintain one or more internal logical files. The data can be either control information or business information.

External output (EO):
External Output is an elementary process in which derived data passes through the boundary from inside to outside. Additionally, an EO may update an internal logical file. The data creates reports or output files sent to other applications. These reports and files are created from information contained in one or more internal logical files and external interface files. The derived data is processed beyond direct retrieval and editing of information from internal logical files or external interface files.

External inquiry (EQ):
External Inquiry is an elementary process with both input and output components that results in data retrieval from one or more internal logical files and external interface files. The input process does not update or maintain any FTRs (Internal Logical Files or External Interface Files) and the output side does not contain derived data.

Internal logical file (ILF):
Internal Logical File is a user identifiable group of logically related data that resides entirely within the application boundary and is maintained through External Inputs. Even though it is not a rule, at least one external output and/or external inquiry should include the ILF as an FTR.

External interface file (EIF):
External Interface File is a user identifiable group of logically related data that is used for reference purposes only. The data resides entirely outside the application boundary and is maintained by external inputs of another application. In other words, the external interface file is an internal logical file for another application. At least one transaction, external input, external output or external inquiry should include the EIF as a File Type Referenced.
This FPA model, developed by Albrecht [9,10] is widely used in software industry. The model estimates software size by counting "function points". This is done using three steps [11] : Step 1: Computing an Unadjusted Function Count (UFC): Using the above five type of components (EI, EO, EQ,ILF and EIF), the number of items in the system is counted and the level of complexity is determined (distinguishing between simple, medium and complex). Thus the total number of items are 5 components multiply with 3 level of complexity. Each level has a weight (provided by the model). The UFC is computed as follows [9][10][11] : Step Once all the GSCs have been rated, Total Degrees of Influence (TDI) is obtained by summing up all the ratings [11] .
Where, F i is the weight of attribute I Now, Value Adjustment Factor is calculated using the formula [10] : Step 3: After determining the Unadjusted Function Point count (UFP) out of transactional and data function types and calculating the Value Adjustment Factor (VAF) by rating the general system characteristics, the final Function Point count can be calculated using the formula [ To use this model, the software development organization has to maintain a database of its projects, including duration, cost, manpower effort and function points (FE). Based on this database, the cost (in terms of time and money) of one FP can be computed. Henceforth, the FP of any new project can be computed as described above and the cost estimates derived.

Re-engineering case study:
To measure the Function Point for re-engineering application, we apply the FPA method for the in-house re-engineering project at one of the leading software organization. Identity is not disclosed honouring the industry sentiments.

About the project:
The Project is an application namely Resource Requirement Form (RRF) which is basically developed for associates who are working for the organisation. The Project has the following features: * Each request form has a unique ID, which is used for tracking and status viewing. * It automates all functions of the workflow pertaining to hardware and software installation processing. * Generates automatic mail between users to draw their attention. * Approving Authorities name, time and data is endorsed from the terminal. * When the form is accepted /submitted by higher authorities, the associate receives feedback on email with date and time of the approval of the request. * E-mail notification is sent at every transition of the flow of the process. The Project was developed in VB, ASP with SQL server environment and is being used successfully by the associates. Over the period, the higher authorities decided to redesign and redevelop this in .Net environment with some additional requirements. We measured the FP as per given requirements documents. Detail is given in Table 1.
We also estimate the FP count for the same project which was developed using Migration Model for Legacy Source (MM LC ) [12] . Using this model, the legacy source codes are loaded into .Net migration tool. The tool converts 45 % of source code into target environment successfully. A migration tool cannot resolve the remaining compatibility issue and the developer need to fix the issues [13] . The developer needs to pay attention to the following activities in this regard.
1. The development team will have to rewrite the code before using the migration tool as and when the target environment does not support certain features [14] . 2. The duplicate code removal, implementing coding standards, upgrading the problematic syntax and controls should be done [15] . 3. Once the migration tool is loaded, the development team needs to take care of certain editing like syntax changes, changes in control object models, unsupported functions requiring complete redesign, etc [16] . FP = UFC * VAF 4. Another important factor is knowledge transfer related to Focus on Future Re-engineering (FFR). In this stage, the developer, should share knowledge and train the co-developers for transparency leading to be better understanding and accurate and fast achievement of the desired objectives of the project. The FP count as per MM LC is given in Table 2.

DISCUSSION
Variances of Functional Count of normal reengineering process and in using migration model were very less. To be advantageous for the customer Function Points can be used to help specify to a vendor the key deliverables, so as to ensure that appropriate levels of functionality will be delivered and to develop objective measures of cost-effectiveness and quality. They are most effectively used with fixed price contracts as a means of specifying exactly what will be delivered. From a vendor perspective, successful management of fixed price contracts depends absolutely on accurate representations of effort. Function Points offer a vast number of benefits by capturing the size of the software from its functionality standpoint. FPA does have some disadvantages as follows, Kitchenham [17] Developer's experience: Implementation of a specific logic differs based on the level of experience of the developer. Hence, the number of lines of code differs from person to person. An experienced developer may implement certain functionality in fewer lines of code than another developer of relatively less experience does, though they use the same language.

Advent of GUI tools:
With the advent of GUI-based languages/tools such as Visual Basic, much of the development work is done by drag-and-drops and a few mouse clicks, where most of the time the programmer virtually writes no piece of code. It is not possible to account for the code that is automatically generated in this case. This difference invites huge variations in productivity and other metrics with respect to different languages, making the lines of code more and more irrelevant in the context of GUI-based languages/tools, which are prominent in the present software development arena.

CONCLUSION
This study has taken the critical view of Function point estimation issues with migration tool related to reengineering software perspective. The estimated result is close to normal FPA estimation process, but it specifies a particular migration tool. This method must be validated by applying a number of re-engineering applications with a known FPA model. The results have to be discussed with the team of software engineers for further enhancement.