{'fraction_non_alphanumeric': 0.019907925842976234, 'fraction_numerical': 0.005474679606818465, 'mean_word_length': 5.082103670071888, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
How to model wireless mesh networks topology

The specification of network connectivity model or topology is the beginning of design and analysis in Computer Network researches. Wireless Mesh Networks is an autonomic network that is dynamically self-organised, self-configured while the mesh nodes establish automatic connectivity with the adjacent nodes in the relay network of wireless backbone routers. Researches in Wireless Mesh Networks range from node deployment to internetworking issues with sensor, Internet and cellular networks. These researches require modelling of relationships and interactions among nodes including technical characteristics of the links while satisfying the architectural requirements of the physical network. However, the existing topology generators model geographic topologies which constitute different architectures, thus may not be suitable in Wireless Mesh Networks scenarios. The existing methods of topology generation are explored, analysed and parameters for their characterisation are identified. Furthermore, an algorithm for the design of Wireless Mesh Networks topology based on square grid model is proposed in this paper. The performance of the topology generated is also evaluated. This research is particularly important in the generation of a close-to-real topology for ensuring relevance of design to the intended network and validity of results obtained in Wireless Mesh Networks researches.


Introduction
The growing demand for Wireless Mesh Networks (WMN) is majorly motivated by its provision of low cost broadband access, facilitating real-time web-based applications for mobile users. WMN is a self-healing, self-configuring and self-organised communication network with fixed wireless Mesh Routers (MR) and static or mobile Mesh Clients (MC). And being an infrastructure wireless ad hoc, it has the capability of service delivery coordinated by an important node referred to as Internet gateway (IGW). With IGW, WMN is able to internetwork with other networks such as Internet, Cellular and Sensor networks [1]. MC can generate and serve as sink for traffic in the network, while MR is only responsible for multihop relaying of traffic in the backbone of WMN. The multihop provided by the MR extends connection beyond the adjacent nodes while IGW provides the bridge between WMN and outside network as shown in figure 1. MC is usually an IP enabled devices like PDAs, mobile phones, laptops and desktops.
WMN offers low deployment cost for mobile Internet users, hence an indispensable access network for delivery of multimedia applications such as e-learning, games, disaster recovery operation and teleconferencing. Consequently, WMN researches are motivated by the need to design efficient  protocols for the delivery of these applications which are based on certain algorithm design objectives and constraints. An important starting point in the design of such network protocols is the network topology design for modelling of the simulated scenario to capture the network components characteristics and interactions for design. Furthermore, topology design marks the template for the evaluation of new protocol via simulation. However, the validity of simulation highly depends on the simulation model employed [2]. Topology generation is the design of representation of the network characteristics and connectivity which are important basic research task to be accomplished in the development and/or analysis of networks and protocols. Node connectivity in WMN is typically ensured among adjacent nodes especially if the nodes are within the transmission range of one another. Apart from 1-hop connectivity, nodes also connect via intermediate relay network, however, with a bound on the number of hop possible without signal level degeneration.
Graph theory is usually the basic tool used in modelling the network topology, thus several graph models have been proposed. Furthermore, a significant parameter in selecting or designing topology generators is the quantification of its adherence or conformity to the technical characteristics of nodes interactions and existence of links between nodes while satisfying the architecture requirements of the physical network. The importance of generating close to real network topology is identified [3] - [5]. Pure random models, Waxman model and its variants are usually implemented at the core of random, hierarchical and degree-related synthetic topology generators such as GT-ITM, Inet, BRITE and Tiers [6]. However, these synthetic topology generators based on geographic mathematical models of certain probability may not adequately capture the inherent topological properties of multihop infrastructure ad hoc like WMN [2]. And topology generation of a close to real network characteristics ensures relevance of the proposed protocol and validity of evaluation results obtained in such researches [7].
In this paper, an algorithm based on mathematical and interference model (protocol model) is proposed for the generation of WMN topology based on grid structure to serve as the starting point in the design of network protocols researches for WMN. The proposed algorithm models the node placements, link establishments and node distribution with a view to obtaining realistic network connectivity model as a premise to the validity of proposed protocols and its observed performance. The remaining sections of the paper is organised as follows. Section 2 is a review of existing synthetic topology models and generators. The algorithm for the design of the proposed WMN network topology generation is described in Section 3. Section 4 is the performance evaluation of the proposed algorithm while Section 5 concludes the paper.

Related works
Multihop network design consists of node, deployment and mobility, radio, wireless signal propagation and traffic pattern model designs [2]. Two of the sub models (wireless signal propagation and traffic pattern) are handled by measurement. However, most research efforts in the design of node models are not verified by real measurement, furthermore, they are not motivated by the structure of real networks. In uniform node placement model, the placement area L 2 and number of nodes n are selected with a placement probability of n/L 2 . The chain node placement model implements equidistant internodes distances among the network nodes placed on a line. The grid node placement model uses the intersection points of cells as the node location points, in this case, the basic node degree are typically 2, or 3 or 4 depending on the location in the rectangular or square grid structure.
In the existing topology designs, node placements and interactions are based on random model which establishes links between randomly placed nodes based on certain probability. The probability of link between the nodes and maximum distance between any two nodes are expresses in [8] as: where 0<α, β≤1 are Waxman parameters, d is the Euclidean distance between nodes u and v and L is the maximum distance between any two nodes. In addition randomly generated number in the range between 0 and L replaces d in one of the variants of Waxman model. Another variation includes specification of average node degree requirements by the introduction of a scaling factor kԑ/n on P(u,v) for controlling the number of edges placed between nodes. Also [3] employs the probability: Three hierarchical design levels of Internet topology -LAN, MAN (by minimum spanning tree) and WAN are presented in [9]. The initial connected random graph generated is a transit domain, while each of the transit domains is connected with stubs. The backbone / access hierarchical topology of transit and stub domains is generated in GT-ITM [10].
Inet [11] is another synthetic Internet topology generator based on random network generation. It builds spanning tree for all nodes with node degree greater than 1 with uniform probability of d/D for node degree d and the sum of node degrees of other nodes with at least one free degree, D. Node connectivity process is based on some heuristics. Inet topology generators still fall short in capturing some properties of Internet such as maximum clique size and clustering coefficient. Even in cases of uniform node placement, [12] - [13] achieved 10.8 and 13.78 average node degree respectively at connectivity probability of 0.99, however, high node degree implies connected network with many links for all pairs, hence certain impacting factors cannot be studied in such networks. The poor performance and lack of robustness to failure of some synthetic topology generators are highlighted in [14]. In [4], the tasks of human designer in a network topology design are simulated in the design of IGen, additionally, the procedures are automated to produce IGen topology based on certain heuristics and hence it is not based on probabilistic method. IGen groups the nodes into different clusters based on their different Euclidean distances and/or traffic demand however, node connectivity model and determination of existence or otherwise of link or edges are not considered; and further researches are also required on link capacity assignment.
BRITE [15] implements preferential attachment based on Waxman or incremental node growth model while in NPART [2], the node placement/ topology design algorithm permits the network to grow, thus the placement area is not predefined. Link-level topology generator that captures both the subnet and degree distributions of the measured network is proposed in [7]. The node centric model assumes predefined node degree in the topology generation, and then the links are merged to obtain the required subnet distribution. Furthermore, in the subnet approach, the nodes in different subnet generated are combined in such a way to satisfy the node degree specification. However the work did not address network parameters such as the average node shortest path and graph density.
From the foregoing, the topology generation of GT-ITM, NPART and BRITE considers only graph properties, while the consideration of technical and economic constraints are also important as random, hierarchical, degree-related and other graph properties as proposed in the design of network topologies [4].

Motivation
The main motivation for the proposed topology generator in this paper is the connectivity issue in WMN which arose when Waxman model of random graph is simulated for WMN. The topology obtained is as shown in figure 2. However, the existing topology generators based on Waxman model depicts a geographic and probability based topology which may not to be suitable in this case, given the following observations from figure 2:  Waxman model creates links with far away nodes while the nearest nodes are left unconnected.  The topology generated by Waxman may contain unconnected nodes however, connectivity cannot be taken for granted, and it has to be ensured.  The topology generated by Waxman may contain unconnected nodes however, connectivity cannot be taken for granted, and it has to be ensured.   The fan-out of the mesh node should form the upper bound of the node degree and maximum hop count in WMN.  Inter node placement distance should reflect close to real router placement, thus too close/far nodes may not be realistic. Furthermore, for network connectivity, [16] highlights that probability of each node communicating with another node is informed by their geometric distance, however, this is usually a function of nodes transmission range, multipath fading or shadowing. Moreover, NPART topology generator is based on similar focus however link establishment model differs. Hence the topology design problem in WMN addressed in this paper is to design placement of nodes on a network area such that the characteristics of WMN which determines the nature of inter node communication is simulated given that a connected topology is guaranteed.

Algorithm description and operation
The following assumptions are made:  l should be less than T r so as to isolate unrealistic node degree and cases when connectivity is difficult to achieve.  l should be a factor of L in order to obtain equal square sections in the square grid structure  All wireless nodes have same transmission power hence equal T r  To ensure connectivity, each node has at least one adjacent node The algorithm generates random nodes on a square grid placement area to simulate WMN topology. The topology model proposed is represented mathematically with predetermined placement area and the establishment of links is achieved based on the interference model (protocol model) [17]. The protocol model states that a packet transmitted by a node at location X i is received by another node placed at For every node placed at location X k , with a simultaneous transmission in the same channel and where is the guard zone between adjacent nodes to prevent interference for nodes within each other's T r . The randomly generated nodes are independently and uniformly distributed over given network area. 1-hop nodes neighbour list (adjacent nodes) is generated based on the parameter relations specified in the protocol model using the transmission range of wireless nodes, thus the connectivity matrices is created with 0 for no link and 1 if link exists between the two nodes (figure 3) .The following is the procedure implemented for the random node placement and node connectivity based on the protocol model for WMN topology design: 1. Input L, l, and T r 2. Initialise all variables 3. Compute the network topology of N number of squares for WMN radio placement area 4. Create network grid for the total number of vertical v k and horizontal h k lines contributing to the number of square sections in the area. 5. Compute number of nodes r, as a function of predefined area as r = ŋ N where ŋ is the percentage of the total network square sections to be assigned a WMN radio node 6. Generate vector of random integers to depict nodes' positions and adjacent nodes list given the protocol model. 7. Generate connectivity matrix 8. Generate node degree for the topology and check the connectivity status of the network

Results and discussions
The wide difference in the average diameter of PROTOPO and Leipzig is a reflection of existence of bridge nodes and delay in transmission in Leipzig (figure 4).   Table 1 shows the analysis of PROTOPO and Leipzig based on 11 topology samples ranging from 143 to 177 nodes, with bridge nodes inclusive while the number of generations of samples in PROTOPO achieves 95% level of confidence. The number of adjacent nodes in Leipzig samples is lower than that observed in PROTOPO due to the emphasis placed on the connectivity in the model of PROTOPO ( figure 5).  Figure 5. Comparison of node degree distributions The average share of disconnected nodes is 14.27% in Leipzig, PROTOPO could not capture this parameter because the algorithm usually test the topology generated for connectivity however, and its adjacent list can consists of a single link. Thus PROTOPO makes provisions to avoid scenarios of disconnected networks which in reality may be the ideal except if such nodes exist to serve as connecting hub for new joins.

Conclusion and future works
The extent of practical and realistic objectives and constraints considered by network topology designers determines the extent of acceptability and validity of design and evaluation of protocols based on these topology models. Thus, a practical flexible network topology model based on the protocol model depicting the criteria for existence or otherwise of network links among the communicating nodes and the generation of connected networks is presented. This tool can serve as the basis for path planning optimisation in real time for multicast routing, route for autonomous system and gathering information from data servers at varying locations. At present, only topology characteristics can be sampled, further research work is also required to optimise PROTOPO.