DESC:FORM 2
THE PATENTS ACT 1970
[39 OF 1970]
&
THE PATENTS RULES, 2003

COMPLETE SPECIFICATION
[See section 10; Rule 13]

TITLE: “METHOD AND SYSTEM FOR SELECTING OPTIMAL MULTIPOINT RELAYS (MPR) IN A WIRELESS NETWORK”

Name and Address of the Applicant:
ALPHA DESIGN TECHNOLOGIES PVT. LTD.,
09, Service Road, HAL 2nd Stage, Indiranagar, Bangalore - 560008.

Nationality: India

The following specification particularly describes the invention and the manner in which it is to be performed.
TECHNICAL FIELD
[0001] The present subject matter is, in general, related to ad-hoc wireless networks, but not exclusively, to a method and system for a method and system for selecting optimal Multi-Point Relays (MPRs) in a Mobile Ad-hoc Network (MANET) based on a Quality of Service (QoS) metrics associated with the MPRs.

BACKGROUND
[0002] Mobile Ad-hoc Networks (MANETs) are autonomously self-organized networks that do not have a fixed topology. In such networks, each network node acts as both a router and a host at the same time. All the network nodes are equivalent to each other and can move out or join in the network freely. The mobile nodes that are in a radio range of each other can directly communicate and transfer the necessary information. Also, the network nodes will have a wireless interface to communicate with another node in the range. This kind of a network may be fully distributed and can work at any place without the help of any fixed infrastructure as access points or base stations.

[0003] Further, in the MANET environment of a tactical scenario, the QoS plays an important role in achieving a successful data/voice transfer within the limited radio resources available. Generally, most of the radio resources are scarce and there is no luxury of necessary flooding of messages in the network. The network is autonomous, self-forming, self-maintaining and self-healing in nature.

[0004] At present, in the MANET environment, an Optimized Link State Routing (OLSR) approach is employed for MPR selection. This is the default way of MPR selection, which makes sure that all 2-hop neighbors of the source node are covered by all the selected MPRs for data flooding. However, this default selection does not take into consideration whether the required QoS is fulfilled by the MPR selection criteria.

[0005] Additionally, in military tactical networks, the traditional way of selecting the MPRs is not effective as the nodes are in constant movement and the default way of selecting the MPRs will result in an inefficient way of data flooding. For example, as the nodes are mobile, finding the optimum path just by finding shortest path will not be optimal. So, when the nodes are mobile, other parameters should also be taken into account for finding the optimal path from source to a destination. Hence, there is a need for a method that can select an optimal MPR in tactical networks based on the QoS metrics, and thereby reduce inefficient data flooding in the MANET networks.

[0006] The information disclosed in this background of the disclosure section is only for enhancement of understanding of the general background of the invention and should not be taken as an acknowledgement or any form of suggestion that this information forms the prior art already known to a person skilled in the art.

SUMMARY
[0007] Disclosed herein is a method for selecting optimal Multi-Point Relays (MPRs) in a Mobile Ad-hoc Network (MANET). The method comprises sorting, by a MPR selection unit, each of a plurality of MPRs in the network based on a Quality of Service (QoS) metrics corresponding to each of the plurality of MPSs. Further, the method comprises determining a total number of 2-hop neighboring nodes covered by each of the plurality of MPRs. Finally, the method comprises selecting one or more of the plurality of MPRs as the optimal MPRs based on the QoS metrics and the total number of 2-hop nodes covered by each of the plurality of MPRs

[0008] Further, the present disclosure relates to a Multi-Point Relay (MPR) selection unit for selecting optimal Multi-Point Relays (MPRs) in a Mobile Ad-hoc Network (MANET). The MPR selection unit comprises a processor and a memory. The memory is communicatively coupled to the processor, wherein the memory stores processor-executable instructions, which on execution, cause the processor to sort each of a plurality of MPRs in the network based on a Quality of Service (QoS) metrics corresponding to each of the plurality of MPRs. Further, the instructions cause the processor to determine a total number of 2-hop neighboring nodes covered by each of the plurality of MPRs. Finally, instructions cause the processor to select one or more of the plurality of MPRs as the optimal MPRs based on the QoS metrics and the total number of 2-hop nodes covered by each of the plurality of MPRs.

[0009] The foregoing summary is illustrative only and is not intended to be in any way limiting. In addition to the illustrative aspects, embodiments, and features described above, further aspects, embodiments, and features will become apparent by reference to the drawings and the following detailed description.

BRIEF DESCRIPTION OF THE ACCOMPANYING DRAWINGS
[0010] The accompanying drawings, which are incorporated in and constitute a part of this disclosure, illustrate exemplary embodiments and, together with the description, explain the disclosed principles. In the figures, the left-most digit(s) of a reference number identifies the figure in which the reference number first appears. The same numbers are used throughout the figures to reference like features and components. Some embodiments of system and/or methods in accordance with embodiments of the present subject matter are now described, by way of example only, and regarding the accompanying figures, in which:

[0011] FIGS. 1A–1C illustrate an existing approach of selecting MPRs in tactical networks, in accordance with some embodiments of the present disclosure.

[0012] FIGS. 2A-2B illustrate a method of selecting optimal MPRs based on Quality of Service (QoS) in accordance with some embodiments of the present disclosure.

[0013] FIG. 3 shows a detailed block diagram of a MPR selection unit in accordance with some embodiments of the present disclosure.

[0014] FIG. 4 shows a flowchart illustrating a method of selecting optimal MPRs in a Mobile Ad-hoc Network (MANET) in accordance with some embodiments of the present disclosure.

[0015] It should be appreciated by those skilled in the art that any block diagrams herein represent conceptual views of illustrative systems embodying the principles of the present subject matter. Similarly, it will be appreciated that any flow charts, flow diagrams, state transition diagrams, pseudo code, and the like represent various processes which may be substantially represented in computer readable medium and executed by a computer or processor, whether such computer or processor is explicitly shown.

DETAILED DESCRIPTION
[0016] In the present document, the word "exemplary" is used herein to mean "serving as an example, instance, or illustration." Any embodiment or implementation of the present subject matter described herein as "exemplary" is not necessarily to be construed as preferred or advantageous over other embodiments.
[0017] While the disclosure is susceptible to various modifications and alternative forms, specific embodiment thereof has been shown by way of example in the drawings and will be described in detail below. It should be understood, however that it is not intended to limit the disclosure to the specific forms disclosed, but on the contrary, the disclosure is to cover all modifications, equivalents, and alternative falling within the scope of the disclosure.
[0018] The terms “comprises”, “comprising”, “includes”, or any other variations thereof, are intended to cover a non-exclusive inclusion, such that a setup, device, or method that comprises a list of components or steps does not include only those components or steps but may include other components or steps not expressly listed or inherent to such setup or device or method. In other words, one or more elements in a system or apparatus proceeded by “comprises… a” does not, without more constraints, preclude the existence of other elements or additional elements in the system or method.
[0019] The present disclosure relates to a method and a MPR selection unit for selecting optimal Multi-Point Relays (MPRs) in tactical and Mobile Ad-hoc Networks (MANET) based on the QoS metrics. In an embodiment, the proposed method may comprise extracting a subset of nodes having best QoS metrics from a set of nodes that are at a 1-hop neighboring distance. This may be achieved only when the network continuously keeps sharing the QoS metrics of each node, fully or at least partially, with the other nodes during ‘hello’ message exchange phase. The QoS metrics may be piggybacked into control messages with very minimal overload. In an embodiment, the proposed method may comprise sorting all the 1-hop neighboring nodes according to the order of their QoS metrics and selecting the optimal MPRs from the 1-hop neighboring nodes based on 2-hop coverage criteria in the order of their QoS metrics.
[0020] In the following detailed description of the embodiments of the disclosure, reference is made to the accompanying drawings that form a part hereof, and in which are shown by way of illustration specific embodiments in which the disclosure may be practiced. These embodiments are described in sufficient detail to enable those skilled in the art to practice the disclosure, and it is to be understood that other embodiments may be utilized and that changes may be made without departing from the scope of the present disclosure. The following description is, therefore, not to be taken in a limiting sense.

[0021] FIGS. 1A–1C illustrate an existing/traditional approach of selecting MPRs in tactical networks, in accordance with some embodiments of the present disclosure.

[0022] In an embodiment, suppose FIG. 1A represents a Mobile Ad-hoc Network (MANET) comprising a plurality of nodes, including at least one source node ‘S’ and other destination/secondary nodes. Suppose the nodes which are at a 1-hop distance from the source node ‘S’ are labelled as nodes 1, 2, … 6 and the nodes which are at a 2-hop distance from the source node ‘S’ are marked with labels a, b, … f. Further, the connections between the nodes are indicated by solid lines connecting the nodes. In an embodiment, the network being considered may not be limited to a MANET, but may include any other wireless network such as, for example, a tactical ad-hoc network or a military ad-hoc network. Further, the plurality of nodes in the network may include, without limiting to, edge devices and sensors.

[0023] In an embodiment, suppose the source node ‘S’ needs to select one or more MPRs for carrying out a communication with each of the one or more nodes in the network in such a way that all the 2-hop neighbors of the source node ‘S’ are covered. According to the traditional approach, the MPR selection may be carried out by simply checking if there are any unique 2-hop neighbors connecting to a relay, which is not connected to any other 1-hop neighbors. In the instant example, node 1 may be selected as one of the MPRs, since node ‘a’ is connected to only node 1.

[0024] In the subsequent step, as shown in FIG. 1B, the source node ‘S’ may select the MPRs, which have largest number of uncovered 2-hop neighbors. Accordingly, in the instant example, the source node ‘S’ may select nodes 2, 3 and 4 as the MPRs. Thereafter, the source node ‘S’ may remove the nodes whose neighbors are already covered by the other MPRs in the set. That is, in the instant example, as illustrated in FIG. 1C, node 2 may be removed from the MPR set, since node 2 is connected to node ‘b’, node ‘c’ and node ‘d’, which are reachable from the other MPRs - node 1, node 3 and node 4 respectively. Further, node 3 and node 4 may be selected as the MPRs since both node 3 and node 4 cover at least one node which is not reachable by any other node.

[0025] FIGS. 2A-2B illustrate a method of selecting optimal MPRs based on Quality of Service (QoS) in accordance with some embodiments of the present disclosure.

[0026] In an embodiment, consider a network comprising a source node ‘b’ and a plurality of secondary nodes, namely node a, node b, node c, node d, node e, node f and node g. Here, node a, node c, node f and node g are at a 1-hop distance from the source node ‘b’. Further, node d, node e are at a 2-hop distance from the source node ‘b’. This is illustrated in FIG. 2A of the disclosure.

[0027] In an embodiment, during the QoS metrics based MPR selection, as shown in FIG. 2B, the source node may select the optimal MPRs based on the QoS metrics associated with each of the plurality of MPRs that are in a 1-hop neighbor set. To enable this, the network is configured to continuously share/exchange the QoS metrics of each node, fully or at least partially, with each of the other nodes in the network. This sharing may be completed during the initial handshake procedure of the nodes, for example, when the nodes are in a ‘hello’ message exchange phase. Subsequently, the QoS metrics of each node may be piggybacked into the required control message with a very minimal overload.

[0028] That is, using the QoS metrics based MPR selection, all the 1-hop neighbor nodes of the source may be sorted according to the order of their QoS metrics, and subsequently, the optimal MPRs may be selected based on the regular 2-hop coverage criteria (i.e., by identifying nodes with best coverage), but in the order of the QoS metrics.

[0029] Going back to the example of FIG 2A, if the traditional MPR selection criteria is applied on FIG. 2A, then the node ‘c’ may be selected as the MPR node for the source node ‘b’, since the node ‘c’ covers maximum 2-hop neighbors of the source node ‘b’. However, this selection may not be an optimal selection since the QoS metrics of node ‘c’ is not taken into consideration for selecting it as the optimal MPR.

[0030] However, with the proposed QoS metrics-based selection method, node ‘f’ may be selected as the optimal MPR for the source node ‘b’, since the QoS metrics for the link ‘b-f’ is higher than that of the ‘b-c’ link. That is, during the MPR selection, a link between any two nodes may be dynamically assigned with a QoS metrics, which is a value between 0-10, wherein ‘10’ indicates excellent QoS metrics and ‘0’ indicates very poor QoS metrics. In the example of FIG. 2B, since the QoS metric for the link ‘b-f’ is 8 and greater than the QoS metric for the link ‘b-c’, which is 5, the node ‘f’, having the highest rank, may be selected as the optimal MPR node.

[0031] In an embodiment, the QoS metrics may be calculated and assigned based on various QoS parameters including, without limiting to, a Signal-to-Noise Ratio (SNR) of the network, bandwidth of the network, propagation delay in the network, path loss and packet loss in the network.

[0032] FIG. 3 shows a detailed block diagram of a MPR selection unit in accordance with some embodiments of the present disclosure.

[0033] In some implementations, the MPR selection unit 301 may include an I/O interface 303, a processor 305 and a memory 307. The I/O interface 303 may be communicatively interfaced with a nearest router and/or a network controller for receiving any data, commands or updates to the MPR selection unit 301. The memory 307 may be communicatively coupled to the processor 305 and may store data 309 and one or more modules 311. The processor 305 may be configured to perform one or more functions of the MPR selection unit 301 in selection of optimal MPRs in a Mobile Ad-hoc Network (MANET), using the data 309 and the one or more modules 311. In an embodiment, the MPR selection unit 301 may be implemented in the network, as a part one of the nodes and/or within a network controller, router or modem connecting to the network. The MPR selection unit 301 may be a stand-alone computing device, which may be attached to a MANET network whenever there is a requirement.

[0034] In an embodiment, the data 309 stored in the memory 307 may include, without limitation, QoS parameters 313, QoS metrics 315 and other data 317. In some implementations, the data 309 may be stored within the memory 307 in the form of various data structures. Additionally, the data 309 may be organized using data models, such as relational or hierarchical data models. The other data 317 may include various temporary data and files generated by the one or more modules 311 while performing various functions of the MPR selection unit 301. As an example, the other data 317 may include, without limitation, information related to source nodes in the network and information related to destination nodes in the network and the like.

[0035] In an embodiment, the QoS parameters 313 may include, without limiting to, a Signal-to-Noise Ratio (SNR) of the network, bandwidth of the network, propagation delay in the network, path loss and packet loss in the network. In an embodiment, the QoS parameters 313 may be processed and/or analyzed for determining a QoS metrics 315 for the plurality of MPRs in the network. In an embodiment, the QoS metrics 315 may be computed dynamically in real-time and/or computed during initial handshake between the plurality of MPRs in the network.

[0036] In an embodiment, the data 309 may be processed by the one or more modules 311 of the MPR selection unit 301. In some implementations, the one or more modules 311 may be communicatively coupled to the processor 305 for performing one or more functions of the MPR selection unit 301. In an implementation, the one or more modules 311 may include, without limiting to, a sorting module 319, a determination module 321, a selection module 323 and other modules 325.

[0037] As used herein, the term module may refer to an Application Specific Integrated Circuit (ASIC), an electronic circuit, a hardware processor (shared, dedicated, or group) and memory that execute one or more software or firmware programs, a combinational logic circuit, and/or other suitable components that provide the described functionality. In an implementation, each of the one or more modules 311 may be configured as stand-alone hardware computing units. In an embodiment, the other modules 325 may be used to perform various miscellaneous functionalities of the MPR selection unit 301. It will be appreciated that such one or more modules 311 may be represented as a single module or a combination of different modules.

[0038] In an embodiment, the sorting module 319 may be configured for sorting the plurality of MPRs in the network according to the QoS metrics value associated with each of the plurality of MPRs. In an embodiment, the sorting may be performed to identify the MPRs with best or highest QoS metrics among the plurality of MPRs.

[0039] In an embodiment, the determination module 321 may be configured for determining a total number of 2-hop neighboring nodes covered by each of the plurality of MPRs. Here, the number of 2-hop neighboring nodes covered is a crucial factor to ensure whether the selected set of MPRs establish a connectivity with each of the other nodes in the network.

[0040] In an embodiment, the selection module may be configured for selecting one or more of the plurality of MPRs as the optimal MPRs based on the QoS metrics and the total number of 2-hop neighbors covered by the plurality of MPRs. In other words, the MPRs having a highest QoS metrics and having a coverage to most number of unique nodes may be selected as the optimal MPRs for the network.

[0041] FIG. 4 shows a flowchart illustrating a method of selecting optimal MPRs in a Mobile Ad-hoc Network (MANET) in accordance with some embodiments of the present disclosure.

[0042] As illustrated in FIG. 4, the method 400 may include one or more blocks illustrating a method of selecting optimal MPRs in a MANET using a MPR selection unit 300 illustrated in FIG. 3. The method 400 may be described in the general context of computer executable instructions. Generally, computer executable instructions can include routines, programs, objects, components, data structures, procedures, modules, and functions, which perform specific functions or implement specific abstract data types.

[0043] The order in which the method 400 is described is not intended to be construed as a limitation, and any number of the described method blocks can be combined in any order to implement the method. Additionally, individual blocks may be deleted from the methods without departing from the scope of the subject matter described herein. Furthermore, the method can be implemented in any suitable hardware, software, firmware, or combination thereof.

[0044] At block 401, the method 400 includes sorting, by the MPR selection unit 301, each of a plurality of MPRs in the network based on a Quality of Service (QoS) metrics corresponding to each of the plurality of MPRs. In an embodiment, the QoS metrics may be determined based on one or more QoS parameters comprising at least one of a Signal-to-Noise Ratio (SNR) of the network, bandwidth of the network, propagation delay in the network, path loss and packet loss in the network. In an implementation, the QoS metrics may be determined during an initial handshake between the plurality of MPRs.

[0045] At block 403, the method 400 includes determining, by the MPR selection unit 301, a total number of 2-hop neighboring nodes covered by each of the plurality of MPRs. In an embodiment, the 2-hop neighboring nodes may be the nodes can reach a source node through an intermediate node directly connected to the source node. Here, the intermediate node may be 1-hop neighboring node of the source node.

[0046] At block 405, the method 400 includes selecting, by the MPR selection unit 301, one or more of the plurality of MPRs as the optimal MPRs based on the QoS metrics and the total number of 2-hop nodes covered by each of the plurality of MPRs. Thus, the method 400 determines the optimal MPRs using a combination of both the QoS metrics and the neighboring coverage of the MPRs.

[0047] In an embodiment, one or more computer-readable storage media may be utilized in implementing embodiments consistent with the present invention. A computer-readable storage medium refers to any type of physical memory on which information or data readable by a processor may be stored. Thus, a computer-readable storage medium may store instructions for execution by one or more processors, including instructions for causing the processor(s) to perform steps or stages consistent with the embodiments described herein. The term “computer-readable medium” should be understood to include tangible items and exclude carrier waves and transient signals, i.e., non-transitory. Examples include Random Access Memory (RAM), Read-Only Memory (ROM), volatile memory, nonvolatile memory, hard drives, Compact Disc (CD) ROMs, Digital Video Disc (DVDs), flash drives, disks, and any other known physical storage media.

[0048] Advantages of the embodiments of the present disclosure are illustrated herein.
[0049] In an embodiment, the present disclosure provides a secure and efficient routing and situational awareness-based sharing service for mobile tactical edge networks.

[0050] In an embodiment, the present disclosure helps in selecting optimal MPRs based on the QoS metrics and eliminates inefficient way of data flooding in the tactical edge networks and MANETs.

[0051] As stated above, it shall be noted that the method and the MPR selection unit of the present disclosure may be used to overcome various technical problems related to data transmission in MANET or tactical wireless networks. That is, the aforesaid technical advancements and practical applications of the proposed method may be attributed to the aspects of selecting one or more of the plurality of MPRs as the optimal MPRs based on both the QoS metrics and the total number of 2-hop nodes covered by each of the plurality of MPRs, as disclosed in steps 3 of the independent claims 1 and 4 of the present disclosure.

[0052] In light of the technical advancements provided by the disclosed method and the MPR selection unit, the claimed steps, as discussed above, are not routine, conventional, or well-known aspects in the art, as the claimed steps provide the aforesaid solutions to the technical problems existing in the conventional technologies. Further, the claimed steps clearly bring an improvement in the functioning of the system itself, as the claimed steps provide a technical solution to a technical problem.

[0053] The terms "an embodiment", "embodiment", "embodiments", "the embodiment", "the embodiments", "one or more embodiments", "some embodiments", and "one embodiment" mean "one or more (but not all) embodiments of the invention(s)" unless expressly specified otherwise.

[0054] The terms "including", "comprising", “having” and variations thereof mean "including but not limited to", unless expressly specified otherwise.

[0055] The enumerated listing of items does not imply that any or all the items are mutually exclusive, unless expressly specified otherwise. The terms "a", "an" and "the" mean "one or more", unless expressly specified otherwise.

[0056] A description of an embodiment with several components in communication with each other does not imply that all such components are required. On the contrary, a variety of optional components are described to illustrate the wide variety of possible embodiments of the invention.

[0057] When a single device or article is described herein, it will be clear that more than one device/article (whether they cooperate) may be used in place of a single device/article. Similarly, where more than one device/article is described herein (whether they cooperate), it will be clear that a single device/article may be used in place of the more than one device/article or a different number of devices/articles may be used instead of the shown number of devices or programs. The functionality and/or features of a device may be alternatively embodied by one or more other devices which are not explicitly described as having such functionality/features. Thus, other embodiments of invention need not include the device itself.

[0058] Finally, the language used in the specification has been principally selected for readability and instructional purposes, and it may not have been selected to delineate or circumscribe the inventive subject matter. It is therefore intended that the scope of the invention be limited not by this detailed description, but rather by any claims that issue on an application based here on. Accordingly, the embodiments of the present invention are intended to be illustrative, but not limiting, of the scope of the invention, which is set forth in the following claims.

[0059] While various aspects and embodiments have been disclosed herein, other aspects and embodiments will be apparent to those skilled in the art. The various aspects and embodiments disclosed herein are for purposes of illustration and are not intended to be limiting, with the true scope and spirit being indicated by the following claims.

Referral Numerals:
Reference Number Description
301 MPR selection unit
303 I/O Interface
305 Processor
307 Memory
309 Data
311 Modules
313 QoS parameters
315 QoS metrics
317 Other data
319 Sorting module
321 Determination module
323 Selection module
325 Other modules

,CLAIMS:WE CLAIM:
1. A method for selecting optimal Multi-Point Relays (MPRs) in a Mobile Ad-hoc Network (MANET), the method comprising:
sorting, by a MPR selection unit, each of a plurality of MPRs in the network based on a Quality of Service (QoS) metrics corresponding to each of the plurality of MPRs;
determining, by the MPR selection unit, a total number of 2-hop neighboring nodes covered by each of the plurality of MPRs; and
selecting, by the MPR selection unit, one or more of the plurality of MPRs as the optimal MPRs based on the QoS metrics and the total number of 2-hop nodes covered by each of the plurality of MPRs.

2. The method as claimed in claim 1, wherein the QoS metrics is determined based on one or more QoS parameters comprising at least one of a Signal-to-Noise Ratio (SNR) of the network, bandwidth of the network, propagation delay in the network, path loss and packet loss in the network.

3. The method as claimed in claim 1, wherein the QoS metrics is determined during an initial handshake between the plurality of MPRs.

4. A Multi-Point Relay (MPR) selection unit for selecting optimal Multi-Point Relays (MPRs) in a Mobile Ad-hoc Network (MANET), the MPR selection unit comprising:
a processor; and
a memory, communicatively coupled to the processor, wherein the memory stores processor-executable instructions, which on execution, cause the processor to:
sort each of a plurality of MPRs in the network based on a Quality of Service (QoS) metrics corresponding to each of the plurality of MPRs;
determine a total number of 2-hop neighboring nodes covered by each of the plurality of MPRs; and
select one or more of the plurality of MPRs as the optimal MPRs based on the QoS metrics and the total number of 2-hop nodes covered by each of the plurality of MPRs.

5. The MPR selection unit as claimed in claim 5, wherein the QoS metrics is determined based on one or more QoS parameters comprising at least one of a Signal-to-Noise Ratio (SNR) of the network, bandwidth of the network, propagation delay in the network, path loss and packet loss in the network.

6. The MPR selection unit as claimed in claim 5, wherein the QoS metrics is determined during an initial handshake between the plurality of MPRs.

Dated this 18th Day of April, 2022
SANDEEP N P
ATTORNEY FOR THE APPLICANT
IN/PA - 2851