Method and apparatus for scale-free topology generation in relay based wireless networks

BACKGROUND OF THE INVENTION

00011. Field of the Invention

0002The present invention relates to a wireless-fixed relay network, and more particularly, to a method of placing fixed relays in the hybrid network and updating a connectivity map after placing new fixed relays in the network.

00032. Description of the Related Art

0004Traditional cellular networks include base stations or access points that are controlled by a Mobile Switching Center, wherein communications is performed over single hop wireless links between base stations and mobile stations. To provide additional services to mobile subscribers, to extend the range and coverage of the mobile services provided and to enhance network performance and system efficiencies, overlay fixed relay network with no infrastructure may be deployed. Fixed relays, for example Wireless LAN access points, can be used to connect mobile nodes that are not covered by any base stations, to the Internet at a low cost and to relay traffic on-demand. Fixed relays also provide an overlay access technology that may co-exist and inter-operate with cellular access networks. In addition to coverage extension, fixed relays provide robustness and traffic management features to existing networks. For example, when a base station fails or is congested, the traffic destined to the base station may be forwarded to other base stations via fixed relays.

0005Despite the advantages of overlaying fixed relay networks over traditional cellular networks, the scalability of a hybrid network which combines a cellular network and ad hoc wireless network(s), especially relay-based wireless networks, has not been studied. Most of the previous works on wireless network studied ad hoc wireless networks that include nodes, such as mobile nodes, that are placed randomly in the network and these works tried to achieve scalable routing protocols for such networks. Some well known ad hoc routing protocols that aim to reduce delays across the network, i.e., the number of hops between the source and destination nodes, include what one knows as hierarchical state routing and zone routing protocols.

0006Hierarchical state routing protocol includes multi-level clustering and partitioning of mobile nodes, wherein each mobile node knows the state-information within its cluster and the cluster-heads exchange state information through gateways. In the zone routing protocol, a zone that includes nodes within a specified number of hops is defined for each node. Within the zone, a proactive table-driven routing scheme is used, whereas between the zones a reactive routing scheme is used. Both the hierarchical state routing and the zone routing protocols try to achieve a scalable routing protocol for a randomly generated network topology.

0007In addition, a small-world network model and a scale-free network model have been proposed to achieve a small average path length in complex networks, such as the Internet. Small-world and scale-free network models try to achieve a network where each node can reach every other node in the network with a minimum number of hops, independent of the number of nodes in the network. Basically, in the small-world network model, the average path length is small, i.e., most nodes are a few hops away from each other, and the clustering coefficient is high. The clustering coefficient is defined as the average fraction of pairs of neighbors of a node that are also neighbors of each other calculated over the whole network. To form the small-world network model, a current method interpolated between a regular lattice and a random graph. By randomly re-wiring a few edges, this current method reduced the average distance between nodes, but it had little effect on the clustering coefficient. When forming the small-world model, the number of nodes in the network is kept fixed and the re-wired edges are randomly picked. Thus, the small-world model has shown that by introducing some randomness/shortcuts while forming the links between the nodes, the average path length in the network may be significantly reduced while the clustering coefficient is kept high.

0008In scale-free networks, on the other hand, the degree distribution of the nodes is in power-law form, i.e., most nodes have very few connections and few nodes called hubs have many connections. The scale-free network model, in one current approach, is formed by starting with a small number of (m₀) nodes, and at each time step, adding a new node with m (<=m₀) edges that will be connected to the nodes already present in the system. When choosing the nodes to which the new node is to connect, it is assumed that the probability that a new node will be connected to a node depends on the connectivity/degree of that node. The degree of a node is defined as the total number of connections/links to the node and the average of the degrees of all nodes in the network is known as the average degree. Thus, the larger the degree, the “more important” the node is in the network.

0009A recent approach applies the small-world model to ad hoc wireless networks by randomly rewiring some links, using physical wires. It has been shown that randomly rewiring some links with physical wires provides for different node distribution in the network, thus small-world model effects can be obtained in ad hoc wireless networks. Information is used to find contacts/shortcuts in the network to be used for resource discovery and savings in terms of the amount of overhead. In this approach, the selection of contacts in the network is not performed randomly. There are some similarities between this approach and the zone routing protocol, wherein every node in this approach has its own view of the network, also called a zone, and the size of the zone is limited by a given number of hops. To communicate with out-of-zone nodes, a node will need contacts, where contacts are located r hops away and r is a design parameter. In this approach, protocols for contact selection and location are introduced. However, it should be noted that rewiring links using physical wires is an unrealistic solution in wireless networks.

0010There are no current solutions for achieving scalable routing protocols for such hybrid cellular-fixed relay networks. When fixed relays are being overlaid in a hybrid network, the problem on where to place fixed relays in order to achieve scalability in the “next generation”, multi-hop, relay-based wireless networks while, on average, simultaneously minimizing the number of hops or latency must be solved. Specifically, the placement of fixed relays must be performed such that any new relays are within a range of at least one previously deployed relay or base station.

SUMMARY OF THE INVENTION

0011The present invention, in one embodiment, is directed to a method of placing nodes in an area that requires coverage. The method includes the step of creating a network topology such that the average path length is kept to a minimum number of hops at the time of placement of a new node, wherein a limit is placed on a number of neighbors at the time of placement of the new node, the number being a parameter that impacts the average path length, resiliency and capital investment. The new node is connected to at least one node in the network. Optionally the invention may be further directed to a method of updating a multi-hop connectivity map and to a method of routing traffic between nodes according to a predetermined routing criterion.

0012Another embodiment of the invention is directed to an apparatus for placing nodes in an area that requires coverage. The apparatus includes a creating unit for creating a network topology such that the average path length is kept to a minimum number of hops at the time of placement of a new node, wherein a limit is placed on a number of neighbors at the time of placement of the new node. The new node is connected to at least one node in the network. Optionally the invention may be further directed to a method of updating a multi-hop connectivity map and to a method of routing traffic between nodes according to a predetermined routing criterion.

0013Yet another embodiment of the invention is directed to an apparatus that includes creating means for creating a network topology such that the average path length is kept to a minimum number of hops at the time of placement of a new node, wherein a limit is placed on a number of neighbors at the time of placement of the new node. The new node is connected to at least one node in the network. Optionally the invention may be further directed to a method of updating a multi-hop connectivity map and to a method of routing traffic between nodes according to a predetermined routing criterion.

0014Yet another embodiment of the invention is directed to a computer program product embodied on a computer readable means. The computer program product is configured to perform the step of creating a network topology such that the average path length is kept to a minimum number of hops at the time of placement of a new node, wherein a limit is placed on a number of neighbors at the time of placement of the new node. The new node is connected to at least one node in the network.

0015The limited number of neighbors, for a new node to be placed, is a parameter that impacts the average path length, resiliency and capital investment.

BRIEF DESCRIPTION OF THE DRAWINGS

0016The accompanying drawings, which are included to provide a further understanding of the invention and are incorporated in and constitute a part of this specification, illustrate embodiments of the invention that together with the description serve to explain the principles of the invention, wherein:

0017<figref idref="DRAWINGS">FIG. 1</figref> illustrates an embodiment of a hybrid cellular and relay-based wireless overlay network for implementing the present invention;

0018<figref idref="DRAWINGS">FIG. 2</figref><i>a </i>illustrates an embodiment of the invention wherein disjoint clusters are connected through a wired backbone;

0019<figref idref="DRAWINGS">FIG. 2</figref><i>b </i>illustrates an embodiment of the invention wherein disjoint clusters are connected through a high capacity high power (HCHP) fixed relay station; and

0020<figref idref="DRAWINGS">FIG. 3</figref> illustrates a combined algorithm that generates fixed relays and base stations locations/topology and a connectivity map incrementally, after the addition of each fixed relay.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

0021Reference will now be made to preferred embodiments of the present invention, examples of which are illustrated in the accompanying drawings. The present invention achieves a scalable network by applying a small-world network model and a scale-free network model to a joint cellular and fixed relay network that is envisioned for the next generation of wireless networks. As implemented in the present invention, each fixed relay in the network can reach at least one base station in a geographical coverage area through a minimum number of hops. In an embodiment of the present invention, a node is defined as a fixed relay or base station.

0022It should be noted that a fixed relay network is a form of a multi-hop ad hoc wireless network that is controlled by service providers, for example through base stations. In the fixed relay network, the traffic of many mobile users are forwarded through the fixed relays, possibly through multiple hops according to a routing protocol, but preferentially directly to the nearest base station, if the base station is operating under a preset loading threshold. Thus, the scalability of the fixed relay network is a major concern to be able to meet quality of service requirements, such as delay and bandwidth for both real time and non-real time traffic. Range limitations associated with fixed relays, due to power and interference concerns, add a new constraint that is not present in wired networks, thus, making it harder to arrive at an optimal topology. From the service provider's point of view, it is desirable to cover a geographical area with as few relays as possible, thereby keeping the overlap areas to a minimum. However, by doing so, the number of neighbors of each fixed relay is decreased and hence the average path length, i.e., the average number of hops, in the network is increased, making it more difficult to fulfil the quality of service requirements.

0023<figref idref="DRAWINGS">FIG. 1</figref> illustrates an embodiment of a hybrid cellular and relay-based wireless overlay network for implementing the present invention. The network of <figref idref="DRAWINGS">FIG. 1</figref> includes multiple network infrastructure <b>102</b><i>a</i>-<b>102</b><i>x</i>, multiple fixed relays <b>104</b><i>a</i>-<b>104</b><i>x </i>multiple mobile nodes <b>106</b><i>a</i>-<b>106</b><i>x. </i>The present invention extends the coverage of base stations <b>103</b><i>a</i>-<b>103</b><i>x </i>of network infrastructure <b>102</b><i>a</i>-<b>102</b><i>x </i>via fixed relays <b>104</b><i>a</i>-<b>104</b><i>x </i>that are strategically located in a geographical area by a controlling node, for example controller <b>105</b> in base station <b>103</b>. In an embodiment of the invention, a number of base stations <b>103</b> are placed such that the coverage area of base stations <b>103</b> slightly overlaps. New fixed relays <b>104</b> are placed to cover the geographical area with the fewest number of fixed relays <b>104</b> and also to have a small average path length so that fixed relays <b>104</b> can reach at least one base station with a small number of hops. Each fixed relays <b>104</b> basically receive signals from various mobile users <b>106</b> and other fixed relays <b>104</b>, within their range, and transmit the received data to the next fixed relay <b>104</b> or base station <b>103</b> in a route. In an embodiment of the invention, fixed relays <b>104</b> do not have any infrastructure, i.e., they communicate through air interfaces and the range of fixed relays <b>104</b> is limited due to the concerns of, for example, power and interference. As is apparent to one skilled in the art, a geographical area has a number of base stations <b>103</b>, thus one fixed relay <b>104</b> is placed at a time at strategic locations, thereby growing the network continuously.

0024Instead of finding a routing protocol for a randomly generated network of mobile nodes, the present invention creates a wireless network connectivity topology using the scale-free network criteria such that the average path length is small. The present invention also provides a method for locating fixed relays <b>104</b> in the network. Because the small-world and scale-free network models are not readily applicable to wireless networks, due to range limitations associated with fixed relays <b>104</b>, to place fixed relays <b>104</b>, an embodiment of the present invention implements a decision metric. Specifically, instead of placing a newly added fixed relay near highly connected fixed relays <b>104</b> in the network or connecting some of fixed relays <b>104</b> with wires, as currently proposed, the present invention puts a limit on the number of neighbors at the time of placement of each fixed relay <b>104</b>. This limit on the number of neighbors at the time of placement of each fixed relay <b>104</b> is a design parameter that determines the extent of coverage that can be achieved by a given number of fixed relays and the average path length that is achievable between fixed relays <b>104</b> and base stations <b>103</b>.

0025Once fixed relays <b>104</b> are placed in a geographical area, an embodiment of the present invention generates a multi-hop connectivity map at the radio/MAC layer and routes the traffic between fixed relays <b>104</b>. The routing criteria can be, for example, to minimize the number of hops, the number of congested links, to minimize delays and to maximize network throughput. Thus, in this respect, the location, selection and number of fixed relays <b>104</b> are important design parameters. In an embodiment of the present invention, the routing scheme achieves high system utilization by efficient use of network resources, such as bandwidth.

0026Specifically, in an embodiment of the invention, a load balancing based routing scheme is used to pick a route with the fewest number of hops to the least loaded base station, for example <b>103</b><i>b. </i>Since the least loaded base station <b>103</b><i>b </i>may not be the one that can be reached by the minimum number of hops, a joint performance metric is used to determine an optimum path. Furthermore, when load balancing is performed, the type of traffic, both real-time traffic and non real-time traffic, is taken into account. While the different types of traffic can be put in separate queues when the network is started, the packets that are re-routed to the less loaded base station <b>103</b><i>b </i>are chosen such that the delay experienced by these packets fall in line with the quality of service requirements. Thus, the real-time packets may be routed to use the shortest path to achieve a smaller delay, whereas the non real-time packets can be re-routed through, possibly longer, alternative routes to achieve load balancing.

0027When a new node/fixed relay <b>104</b> is added to the connectivity map, it can be connected preferentially to existing nodes with large number of wireless connections while retaining a previously generated connectivity map. Because each fixed relay <b>104</b> in the present invention can reach at least one base station <b>103</b> with a minimum number of hops, some fixed relays <b>104</b> may possibly not reach each other. When fixed relays <b>104</b> are clustered around base stations, this may result in disjoint clusters and could lead to poor load balancing performance. To overcome the disjoint clusters problem, the present invention uses high capacity, high power (HCHP) relay stations in between the disjoint clusters, so that the excess traffic of the congested base station, for example base station <b>103</b><i>x, </i>can be forwarded to other non-congested base stations, for example base station <b>103</b><i>b, </i>in the network.

0028<figref idref="DRAWINGS">FIG. 2</figref><i>a </i>illustrates an embodiment of the invention wherein disjoint infrastructures (clusters) are connected through a wired backbone. In <figref idref="DRAWINGS">FIG. 2</figref><i>a</i>, base stations <b>202</b> of wireless infrastructure <b>204</b> are connected by wired backbone <b>206</b>. <figref idref="DRAWINGS">FIG. 2</figref><i>a </i>also shows that disjoint clusters <b>208</b> are connected through wired backbone <b>206</b>.

0029<figref idref="DRAWINGS">FIG. 2</figref><i>b </i>illustrates an embodiment of the invention wherein disjoint clusters are connected through a HCHP fixed relay. In <figref idref="DRAWINGS">FIG. 2</figref><i>b</i>, disjoint clusters <b>210</b> are connected through HCHP fixed relay <b>212</b>. The location and the number of the HCHP fixed relays <b>212</b> can be determined according to a predetermined algorithm. For example, because the locations of the regular fixed relays <b>104</b> are known, the present invention may find the center of gravity of disjoint clusters <b>210</b>, as illustrated in <figref idref="DRAWINGS">FIG. 2</figref><i>b</i>. Once the center of clusters <b>210</b> are found, a HCHP fixed relay <b>212</b> may be placed in the center of the line connecting the clusters' centers. If the coverage of HCHP fixed relay <b>212</b> is not sufficient to connect disjoint clusters <b>210</b>, additional fixed relay(s) <b>104</b> can be placed along the line connecting the cluster centers. More efficient algorithms that minimize the number of additional HCHP fixed relays <b>212</b> also may be used to obtain the benefits of the present invention.

0030<figref idref="DRAWINGS">FIG. 3</figref> illustrates a combined algorithm that generates the fixed relays and base stations locations/topology and a connectivity map incrementally, after the addition of each fixed relay <b>104</b>. The first portion of <figref idref="DRAWINGS">FIG. 3</figref>, block <b>3</b><i>a, </i>illustrates a flow diagram for generating a topology of base stations and fixed relays. In step <b>3010</b>, the access point coordinates are initialized. In Step <b>3020</b>, a random location of a relay node is generated. In Step <b>3030</b>, a check is performed to determine if the location is in a designated sub-block. If the check of step <b>3030</b> is negative, the algorithm returns to step <b>3020</b>. If the check is positive, in Step <b>3040</b>, another check is performed to determine if the number of neighbors within range of the randomly placed node <b>104</b> is less than or equal to a maximum allowed number of neighbors. If the check of step <b>3040</b> is negative, the algorithm returns to step <b>3020</b>. If the check of step <b>3040</b> is positive, the algorithm goes to block <b>3</b><i>b </i>for generating a connectivity update map after a new fixed relay has been placed, as illustrated in step <b>3045</b>.

0031In Step <b>3050</b> of block <b>3</b><i>b, </i>neighboring nodes, i.e., fixed relays and base stations, are located within the range of the most recently placed node <b>104</b>, call it r<b>0</b>, and the update of the connectivity map is started. During this update process, connections to neighboring nodes are established from the recently placed node (r<b>0</b>) based on connection probability and the interference levels to its neighboring nodes. A limit is placed on the maximum number of connections the most recently placed fixed relay r<b>0</b> can have to its neighboring nodes.

0032In Step <b>3060</b>, a call is placed to neighboring nodes r<b>1</b>, r<b>2</b> . . . r<b>1</b> and the probability (pi) is calculated that node r<b>0</b> will be connected to node rj (j=1 . . . I). Because the degree of node rj is known as kj, pi=kj/Σkj(for all j). In Step <b>3070</b>, the neighboring node with the highest probability is selected. In Step <b>3080</b>, a check is performed to determine if interference with the selected node is acceptable. If the determination of step <b>3080</b> is unsuccessful, it is determined in step <b>3085</b> if all possible connections to the neighboring nodes have been checked. If this is the case, the algorithm jumps to step <b>3110</b> in order to check if all given nodes are placed (step <b>3110</b> is described later in more detail). If the result of Step <b>3085</b> is that not all possible connections to neighboring nodes were checked yet, the algorithm continues with Step <b>3090</b> where the neighboring node with the next lower probability is selected and the algorithm returns to step <b>3080</b>. If the determination of step <b>3080</b> is successful, the connectivity map is updated in Step <b>3095</b> with the connection between the recently placed node and the selected neighboring node, and it is checked in Step <b>3100</b>, if the number of wireless links to the neighboring nodes is less than a maximum preset value. If the determination of step <b>3100</b> is successful, the algorithm returns to step <b>3085</b>. If the determination of step <b>3100</b> is unsuccessful, the algorithm determines, in Step <b>3110</b>, if all given nodes have been placed. If the determination of step <b>3110</b> is successful, the algorithm ends, otherwise the algorithm returns to step <b>3020</b> to place the next access node <b>104</b>.

0033In previous solutions of achieving a scalable hybrid network, the focus was on achieving a scalable routing protocol for a given randomly generated network. However, real networks are not purely random as they have some structure. In an embodiment of the present invention, fixed relays <b>104</b> are not randomly placed in the geographical area; on the contrary, the fixed relays <b>104</b> need to reach at least one base station <b>103</b> in the network to provide services to the mobile nodes <b>106</b> within their coverage area. Therefore, instead of randomly placing fixed relays <b>104</b> and then trying to find a scalable routing protocol to connect these fixed relays, as previously proposed, an embodiment of the present invention provides a novel method of placing fixed relays such that the network is scalable, i.e., fixed relays <b>104</b> can reach to base stations <b>103</b> with a small number of hops, independent of the number of fixed relays in the network. In the present invention, once the topology is fixed and their (mesh) connectivity at the radio/MAC layer optimised, a load-balancing “scale-free” routing protocol may be designed to meet key quality of service requirements, such as delay, bandwidth, and throughput. In addition, although the present invention is illustrated above in a hybrid network of base stations and fixed relays, the present invention may also be applied to pure ad hoc wireless networks and sensor networks.

0034It should be appreciated by one skilled in art, that the present invention may be utilized in any device that implements the hybrid network described above. The foregoing description has been directed to specific embodiments of this invention. It will be apparent, however, that other variations and modifications may be made to the described embodiments, with the attainment of some or all of their advantages. Therefore, it is the object of the appended claims to cover all such variations and modifications as come within the true spirit and scope of the invention.