Method For Enhancing Lifetime And Throughput In A Distributed Wireless Network And System Thereof
Abstract:
A system and method for enhancing lifetime and throughput in a distributed wireless network is disclosed herein. The method of the present invention enables a signed-graph based self-optimization technique with a multi-time scale convergence approach in the distributed wireless networks. The proposed method solves the constraint based optimization problems in wireless networks using a graph-theoretic mechanism. The proposed technique is a distributed, multi-time scale self-optimization approach, which can be implemented using cross-layer techniques in wireless networks and are less complex as compared to optimal solutions disclosed in the art.
FIG.2B
Get Free WhatsApp Updates!
Notices, Deadlines & Correspondence
NIRMAL BUILDING, 9TH FLOOR, NARIMAN POINT, MUMBAI 400021, MAHARASHTRA, INDIA.
Inventors
1. RATH, HEMANT KUMAR
TATA CONSULTANCY SERVICES, ABHILASH BLDG PLOT NO 96 EPIP INDUSTRIAL AREA, WHITEFIELD, BANGALORE 560066, KARNATAKA, INDIA
2. BHATTACHAR, RAJAN MINDIGAL ALASINGARA
TATA CONSULTANCY SERVICES, ABHILASH BLDG PLOT NO 96 EPIP INDUSTRIAL AREA, WHITEFIELD, BANGALORE 560066, KARNATAKA, INDIA
3. SIMHA, ANANTHA
TATA CONSULTANCY SERVICES, ABHILASH BLDG PLOT NO 96 EPIP INDUSTRIAL AREA, WHITEFIELD, BANGALORE 560066, KARNATAKA, INDIA
4. PURUSHOTHAMAN, BALAMURALIDHAR
TATA CONSULTANCY SERVICES, ABHILASH BLDG PLOT NO 96 EPIP INDUSTRIAL AREA, WHITEFIELD, BANGALORE 560066, KARNATAKA, INDIA
Specification
FORM 2
THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENT RULES, 2003
COMPLETE SPECIFICATION
(See Section 10 and Rule 13)
Title of invention:
A SYSTEM AND METHOD FOR ENHANCING LIFETIME AND THROUGHPUT IN A
DISTRIBUTED WIRELESS NETWORK
Applicant:
Tata Consultancy Services Limited A company Incorporated in India under The Companies Act, 1956
Having address:
Nirmal Building, 9th Floor.
Nariman Point Mumbai 400021,
Maharashtra, India
The following specification particularly describes the invention and the manner in which it is to be performed.
FIELD OF THE INVENTION
The invention generally relates to the field of signal processing and optimization in distributed wireless networking. More particularly, the invention relates to a system and method for enhancing lifetime and throughput of a distributed wireless network by self-optimization of the network.
BACKGROUND OF THE INVENTION
With the advent of digital communication, wireless networks have been effectively adopted worldwide for facilitating the support to execute various networking applications. For example, the wireless communication has become the de-facto communication medium at homes, work locations, malls, airports, stadiums, colleges, and other necessary mediums. Further, due to gradual growth in miniaturization technology, the dimensions of the battery operated handheld devices, or more specifically, the nodes in general of the wireless network have been drastically reduced in order to serve variety of applications by means of these handheld devices.
In general, for facilitating support to execute the applications by means of wireless communication these nodes require high rate of transmission. Additionally, these nodes need to support long periods of use between battery charges. Thus, the lifetime of the nodes becomes crucial and therefore these nodes require enhanced lifetime and higher rate of communication. In order to facilitate the higher transmission rate and enhance the lifetime of the wireless network, optimal techniques are required.
In the present scenario, maximization of lifetime and throughput requires frequent exchange of control messages between nodes. However, since wireless networks are broadcasting networks, such control message exchanges not only reduce the effective rate of transmission between nodes, but also impact the overall lifetime of the nodes. This is because, wireless nodes are mainly battery powered and processing of a packet/frame or message for transmission or reception requires energy consumption. Therefore, while optimal techniques are important they also consume resources in terms of battery and throughput.
Wireless networks in general are of two types: centralized network and distributed network. In a centralized network, each wireless node communicates with a central node or base station for
usual communication. However, in a distributed network, each wireless node communicates with other nodes or its neighbors for computing, communication, storage and other services in a distributed fashion. Therefore, in order to transmit at its optimal rate each node requires control messages to communicate with its neighboring node. Since the wireless network is broadcasting in nature, inter node communications not only hampers the effective rate or throughput of the network, but also reduces the lifetime of the network. In addition to this, the complexity of communication protocols and computation also reduce the lifetime of the network. More specifically, the optimization techniques used in the background requires message passing between the individual nodes. In other terms, each node requires adequate information regarding the power available in the neighboring nodes, interference in other nodes, and maximum capacity, etc. Further, in order to share this information with the nodes, it is evident that more resources in terms of battery power and throughput are required. Finding an optimal solution for the above problem in a real time is very difficult and often ends up with an iterated solution. Therefore it demands more computing power. Thus, as these methods consume more battery power, hence they are not feasible for optimization of the wireless networks.
Thus, the existing practices of achieving enhancement in lifetime and throughput are complex and difficult to implement. Most of the existing approaches require message passing which is resource consuming and hence are non-scalable. Further, in the existing optimal approaches, each node requires detailed information about the other nodes in the network. Such detail information includes placement of each node in the network, power available, detailed QoS requirement, etc.
Therefore, in view of the above, there is a long-felt need in the art for a method and system that enables enhancement of lifetime and throughput of wireless network that is scalable, resource-saving, less complex and easy to deploy at each node. More specifically, there is a need for a method and system that enables to avoid passing of control messages amongst the individual nodes in the network and thereby facilitating the self-optimization of the network.
OBJECTIVES OF THE INVENTION
The principal objective of the present invention is to enable enhancement of throughput and lifetime of a distributed wireless network by self-optimizing the said network.
Yet another objective of the present invention is to provide a system and method for enabling the individual nodes to sense the parameters of the neighboring nodes in the distributed wireless network using self-learning mechanism.
Yet another objective of the present invention is to enable a system and method for generating a signed-graph to perform self-optimization using parameters of the individual nodes and the sensed parameters of the neighboring nodes.
Yet another objective of the present invention is to provide a system and method enabling self-optimization using parameters of the individual nodes at different time-scales until a convergence is achieved in the network.
Still another objective of the present invention is to provide a system and method for implementing a cross-layer based approach to facilitate inter-layer updates amongst the individual protocol layers due to said self-optimization of the parameters at the individual nodes of the network.
SUMMARY OF THE INVENTION
Before the present methods, systems, and hardware enablement are described, it is to be understood that this invention is not limited to the particular systems, and methodologies described, as there can be multiple possible embodiments of the present invention which are not expressly illustrated in the present disclosure. It is also to be understood that the terminology used in the description is for the purpose of describing the particular versions or embodiments only, and is not intended to limit the scope of the present invention.
In one of the embodiment, the present invention enables a method for enhancement of throughput and lifetime of a wireless distributed communication network. The method of the present invention enables self-optimizing of the network using a signed-graph based technique. According to this embodiment, each individual node is configured to sense different parameters of neighboring nodes in the network. The individual nodes based on the sensed parameters are configured to update their parameters by self-optimization technique. In this embodiment, the self-optimization is achieved by (i) generating a multi-time scale signed graph and (ii) iteratively updating individual parameters until convergence is achieved by the network. According to the
method of the present invention, the updates are carried out using parameter sensing and cross-layer interactions.
In one of the embodiment, the system of the present invention enables self-optimization of the wireless network by implementing a self-optimization engine on each individual node of the network. The said self-optimization engine is adapted to sense multiple parameters of the neighboring nodes in the network to self-optimize the parameters of the individual nodes by updating the individual parameters at multiple time scales until convergence is achieved using a signed graph technique. Further, the optimization engine enables a tuning layer software patch that facilitates inter-layer updates amongst the individual layers of the protocol stacks due to updating of parameters of the individual nodes at different time scales in the network.
Thus, the method and system of the present invention enables a self-optimization of the network without requiring any control message passing amongst the individual nodes. This enables power saving at each individual nodes thereby facilitating maximization of throughput and lifetime of each node in the network. Further, the system adopted for self-optimization is less complex and easy to deploy without requiring any other additional infrastructure cost. The self-optimization of the network is such that it is equivalent with the optimal solutions.
BRIEF DESCRIPTION OF DRAWINGS
The foregoing summary, as well as the following detailed description of embodiments, is better understood when read in conjunction with the appended drawings. For the purpose of illustrating the invention, there is shown in the drawings example constructions of the invention; however, the invention is not limited to the specific methods and architecture disclosed in the drawings:
Figure 1 is a distributed wireless network (100) illustrating a resource allocation problem among individual nodes in the said network according to an exemplary embodiment of the invention.
Figures 2 (a) and 2(b) illustrates posing of said resource allocation problem as a multi-time scale allocation problem solved by implementing a signed graph based self optimization according to an exemplary embodiment of the invention.
Figure 3 illustrates a cross-layer framework (300) implementing inter-layer updates at multi-time scales according to an exemplary embodiment of the invention.
Figure 4 illustrates a working example (400) of self-optimization enabling joint congestion and power control by generating a monotonic signed graph according to an exemplary embodiment of the invention.
Figures 5(a). 5(b), 6(a) and 6(b) collectively illustrate another working example of self-optimization for joint routing and lifetime maximization according to an exemplary embodiment of the invention.
DETAILED DESCRIPTION:
Some embodiments of this invention, illustrating all its features, will now be discussed in detail. The words "comprising," "having," "containing," and "including," and other forms thereof, are intended to be equivalent in meaning and be open ended in that an item or items following any one of these words is not meant to be an exhaustive listing of such item or items, or meant to be limited to only the listed item or items. It must also be noted that as used herein and in the appended claims, the singular forms "a," "an," and "the" include plural references unless the context clearly dictates otherwise. Although any systems and methods similar or equivalent to those described herein can be used in the practice or testing of embodiments of the present invention, the exemplary, systems and methods are now described. The disclosed embodiments are merely exemplary of the invention, which may be embodied in various forms.
Various modifications to the embodiment will be readily apparent to those skilled in the art and the generic principles herein may be applied to other embodiments. For example, although the present invention will be described in the context of a system and method for estimating efforts in an application outsourcing, one of ordinary skill in the art will readily recognize that the method and system can be utilized in any situation where a customer is impelled to estimate the efforts in terms of monetary value, resources utilized, hours shelled out for support services etc. Thus, the present invention is not intended to be limited to the embodiments illustrated, but is to be accorded the widest scope consistent with the principles and features described herein. Various embodiments of the present invention will now be described with the help of appended figures. The present invention proposes how to pose a resource allocation problem in the wireless networks as a multi-time scale allocation problem. Further, the present invention proposes how to model the multi-time scale allocation problem as a signed-graph problem. Therefore, the first step
in achieving self-optimization is to identify a resource allocation problem in the network and enable to pose the identified problem as a multi-time scale allocation problem that can be solved by implementing signed- graph technique.
Figure 1 is a distributed wireless network (100) illustrating a resource allocation problem among individual nodes in the said network according to an exemplary embodiment of the invention. As illustrated in figure 1. the distributed wireless networks comprises of both wireless ad-hoc networks and wireless sensor networks. The individual nodes are placed in a distributed manner and each node of the network is transmitting packets to the gateway. As shown in the figure 1. multiple paths exist between the source node and the gateway. In an exemplary embodiment, each of the wireless nodes is battery powered having a specific maximum power value (PMax), and is capable of transmitting at a variable power.
Referring to figure 1, in an exemplary embodiment, each of the nodes is capable of choosing a suitable modulation scheme for transmission. Further, according to the present invention, there exists reciprocity in the wireless channel, i.e. the wireless channel between individual nodes is identical in both directions. Further, the model proposed considers log-normal fading and path-loss due to distance. However, in an alternative embodiment, multipath loss model like Rayleigh loss model also can be incorporated in formulation without any loss of generality.
In this exemplary embodiment, each node executes various network applications which generate packets. The nodes while transmitting their own data are also configured to relay the data of other nodes in the network. More specifically, the nodes do not distinguish between self generated data and forwarding data packets. Further, each node is capable of finding its optimal shortest path route to reach a destination node. The applications running at different nodes require Quality of Services (QoS) in terms of maximum/average delay, minimum/average throughput, etc. The applications in turn may use TCP or UDP as the Transport layer protocol. With TCP as the transport layer protocol, the transmission is controlled end-to-end. Apart from this, TCP also employs congestion control/avoidance protocols to control the rate of transmission. TCP updates its rate of transmission using an Adaptive Window Management technique by changing the congestion window (cwnd) of a flow; increase with every successful reception of acknowledgement and decrease with every timeouts and multiple duplicate acknowledgements -dupacks (triple Dupacks). In TCP, guarantee of reception is more important than delay in
reception. UDP, unlike TCP does not control the rate of transmission. Instead, the applications using UDP require hard end-to-end delay bound, failing which the packets get dropped. To provide delay guarantee in-terms of average/maximum delay, an average throughput at the Transport layer is need to be maintained. Since Transport protocols operate on end-to-end mechanism, changes in parameters such as average delay/ maximum delay, cwnd size etc., get reflected only after one Round Trip Time (RTT).
In an exemplary embodiment, unlike transport layer, network layer does not operate on an end-to-end basis. However, routing table generation and updating requires global information (or a cached version of previous global information) for route computation and hence frequent changes of route at node is a costly affair. In practice, the time duration of change of route at a node depends not only on the state of the concerned node (in wireless networks the battery availability at node and the link capacity associated with the link), but also depends on the state of other nodes. However, to provide transparent end-to-end services at the transport layer, period of route computation should be more than the updating period of transport layer. In other words, route change should not be triggered before one RTT and so on. This not only provides transparent services to transport layer protocols, but also saves battery power at a node level and hence the lifetime of the network. Similar to network layer and transport layer updates, MAC as well as PHY layer also updates their power transmission, modulation index at an appropriate time scale such that the effect of interference, channel condition, etc., are mitigated.
In an exemplary embodiment, as illustrated in figure 1, there may be multiple paths available between nodes; however, a bottleneck may arise between flows while selecting a particular path. For example, as illustrated in figure 1, bypassing the central node "C" may lead to select a longer path viz. J-A-B-E-D-Gateway instead of J-C-F-Gateway. Thus, resource allocation becomes a problem and hence needs to be mitigated by enabling self-optimization.
In an exemplary embodiment, considering the wireless network illustrated in figure 1, let Xi (t) is the instantaneous transmission rate of node at time t, where; I is the set of nodes. Each node attempts to maximize its instantaneous rate. Let, Ri (t) be the routing matrix associated with node i at time t. According to this exemplary embodiment, consider yi (t) defined as the corresponding rate of transmission at Transport Layer, which is either the congestion window size (cwnd) for TCP or average rate of transmission for UDP. Let b, (t) be the battery power available at time t in
node i; bj (t) Max = P MAX- Let pi (t) and mi (t) be the transmission power and modulation index of node 'i' at time t respectively. Consider lifetime of node 'i' defined as z\ (t) representing the duration for which the node can actively participate in the network: transmit-receive-sense etc. Let Ii (t) and IOj (t) be the inference observed at node i and node j respectively at time t. In wireless networks, increase in transmission power at any node i results in increase of interference in other neighboring node j. In this exemplary embodiment, though the parameters such as instantaneous transmission rate, routing index, battery availability, transmission power, transport layer rate, etc., are time indexed (at different time scales), they are not reference with time index t. According to this invention, the optimization problem posed is therefore needed to be solved to allocate various resources referring the equation (1) as below:
Where, Ui (xi) is the utility associated with Xi, qi is the cost associated with the transmission of x, and Zi is the lifetime associated with the node i. The tdi and tdth are the current delay associated with the transmission of HoL (Head of Line) packet of node i and tdth is the maximum delay tolerable by the application at node i respectively (real time packets are dropped if the delay condition is violated). The shape/nature of the utility function U,- (x,) depends upon the transport layer protocols used and application requirements, For example, it is observed that Ui (Xi) is convex and double differentiable for TCP, whereas it may not be convex and double differentiable in the case of UDP. UDP can be modeled using approximation techniques. In that case the solution obtained from (1) may not be unique.
The term cost qi is similar to packet drops in wired/wireless network due to buffer overflow or due to packet error. It also includes the battery consumption due to transmission or relaying. Cost due to battery consumption increases as the node reduces its battery power. Therefore, to increase lifetime, nodes should minimize the transmission. With these observations, it is apparent that the objective functions presented in equation (1) are conflicting in nature; the first maximization (utility) results in higher transmission rate whereas the second maximization (lifetime) results in reducing its transmission rate.
Therefore, the present invention enables a self-optimization of each node in the network and thereby facilitating the optimization of the entire network. The present invention poses the optimization problem observed in equation (1) at different time instances and is modeled as multi-time scale signed-graph problem according to an exemplary embodiment. Each node of the network is adapted to solve equation (1) to obtain optimal solution in-terms of transmission power, modulation index, route and transmission rate, etc. More particularly, each node in the wireless network (100) as illustrated in figure 1 attempt to obtain the optimal transmission power, modulation index, route and transmission rate to solve the equation (1). In this exemplary embodiment of the invention, each node senses its neighboring information such as interference, routing table (from periodic broadcasts), and congestion through packet acknowledgements etc.. thereby obtaining the optimal transmission power and transmission rate using self-optimization. Therefore, each individual node is configured to sense the data from the neighboring nodes using self-learning mechanism and hence does not require message passing thereby enabling power saving and increasing lifetime of each node in the network.
Figures 2 (a) and 2(b) illustrates posing of the resource allocation problem or an optimization problem as a multi-time scale allocation problem solved by implementing a signed-graph based self optimization according to an exemplary embodiment of the invention.
In an exemplary embodiment, the present invention proposes a simple, iterative and fair convergence rate signed graph approach enabling a near optimal solution for the optimization of the network. The self-optimization based on signed graph approach is on par with the traditional approaches and can be implemented in any distributed system. Further, this approach enables solving optimized power control for reducing TCP congestion and increasing rate
In an exemplary embodiment, a signed graph G(Vv,£,r)is a directed graph, where V is set of nodes
and E is the subset of Cartesian product of V x V and τE(i,j) →{+1,-1}. A signed graph is strongly connected graph (SCG), if there is a path between every pair of nodes. If there exists a path between any two nodes of a signed graph, path sign can be computed. A path sign of a path between two nodes is the product of signs of sequential edges associated along the path between them. A signed graph is balanced, if all the cycles of the graph have even number of negative signed edges. From dynamic system perspective, parameters/variables of it are represented as
nodes. The interaction between parameters is represented by edges. The edges are labeled as positive or negative, if a parameter activates or inhibits another parameter respectively. In this exemplary embodiment, any dynamic system that attains equilibrium is bounded by several properties as follows:
■ The system attains the equilibrium in the process of converging to optimal solution if and if only if it is monotonic.
■ If a dynamic system represented by a signed graph is balanced, then it attains equilibrium.
■ If a graph is a SCG, then its adjacency matrix is irreducible.
■ If a dynamic system is irreducible, it is strongly monotonic.
■ A strongly monotonic system attains equilibrium.
■ Feasible optimal solutions exist, if and only if the corresponding signed graph of a dynamic system is balanced.
Referring to figure 2(b), the present invention proposes one such method of signed-graph based self-optimization. This method implements a multi time scale approach, in which the optimization involves sub-optimization at different time scales. In an exemplary embodiment, each of the nodes in the network implements a self-optimization engine that is adapted to apply a signed-graph based self-optimization for enabling the optimization of the entire network. One such self-optimization engine (202) implemented on one of the node in the network is illustrated in figure 2(b). Figure 2(b) illustrates sub-optimization at different time scales T1, T2 and T3 respectively for node 'i' The optimization at different scales is illustrated in figure 2(a).
In an exemplary embodiment, referring to figure 2(b), the influence between the variables or parameters is represented as a Weighted Signed Graph (WSG). These parameters include instantaneous power, modulation index, rate change, congestion window, and routing table etc. Each of the edges of the graph is assigned with a signed weight component having a real value: τ:E(i,j)->{x∫xεR}. Note that the WSG is generalization of signed graph, The notion of balancing, equilibrium, irreducibility, SCG, monotonic properties are also eligible for WSG. As illustrated in figure 2(b), the WSG proposed has four different goal variables: x,, y, z, and ή ( rate of transmission - PHY layer capacity, Transport Layer transmission rate - congestion window-in TCP, lifetime and overall throughput).. These goal variables are maximized in different time
scales in T1, T2 and T3 as shown in the figure 2 (b). Control variable Pi (transmission power) is updated at each node, whereas the other control variable Ii (interference) is updated by interference it receives from other nodes at a network level, i.e. by sensing various parameters from neighboring nodes in the network, . Sensed parameters includes from a group consisting of but not limited to interference, routing table, congestion and combinations thereof. Further, referring figure 2(b) goal variables are also affected by the self-optimization engine (202) which controls the control variable along with the routing updates. In addition to this, present value of the goal and state variable of a node also impact the goal and state variable of neighboring nodes (204).
In an exemplary embodiment, the self-optimization engine (202) at one of the individual nodes in the network (100) enables solving the self-optimization problem by solving the equation (1) in a distributed manner. The self-optimization engine (202) solves the problem by iteratively optimizing the individual parameters at the node until convergence is achieved. For example, consider T1, T2 and T3 are the time scales for each node for each iteration that are varied dynamically such that T1