# US 7,613,165 B2 · Method for selecting broadcast routing path using genetic algorithm in Ad-hoc network

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 7,613,165 B2
- Document ID: US7613165B2
- Status: Granted
- Kind: B2
- Application number: 11/633,826
- Filed: 2006-12-05
- Published: 2007-06-14
- Granted: 2009-11-03
- Earliest claimed: 2005-12-05
- Assignees: Electronics and Telecommunications Research Institute
- Inventors: Hyun Soon Shin; Hyun Moon Shin
- Web page: https://patentgrep.com/patent/US7613165B2

## CPC

- H04L 45/08: {Learning-based routing, e.g. using neural networks or artificial intelligence}
- H04L 45/16: Multipoint routing
- H04W 52/46: in multi-hop networks, e.g. wireless relay networks
- H04W 4/06: Selective distribution of broadcast services, e.g. multimedia broadcast multicast service [MBMS]; Services to user groups; One-way selective calling services
- H04W 4/18: Information format or content conversion, e.g. adaptation by the network of the transmitted or received information for the purpose of wireless delivery to users or terminals
- H04W 40/10: based on available power or energy
- H04W 52/0219: {where the power saving management affects multiple terminals}
- H04W 52/143: {Downlink power control}
- H04W 84/18: Self-organising networks, e.g. ad-hoc networks or sensor networks
- H04W 88/04: adapted for relaying to or from another terminal or user
- Y02D 30/70: in wireless communication networks
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72)
- Y02D: CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE

## Abstract

Provided is a method for selecting a broadcast routing path using a genetic algorithm in an Ad-hoc network. In the method, a plurality of nodes of the Ad-hoc network is defined as one chromosome, and the chromosome is represented with pairs of {order, power} in each node. Child nodes are created by performing an order based crossover and a power based crossover with respect to parent nodes neighboring to a source node. A mutation operation is performed with respect to the parent nodes and the child nodes. Relay nodes are determined by converting order and power information of each node of the chromosome into routing tree information. Power of the relay nodes is determined. A broadcast routing path is selected using the number and power of the relay nodes.

## Claims

### Claim 1

A method for selecting a broadcast routing path using a genetic algorithm in an Ad-hoc network having a plurality of nodes, comprising the steps of:
a) defining a plurality of nodes of the Ad-hoc network as one chromosome, and representing the chromosome with pairs of {order, power} in each node;
b) creating child nodes by performing an order based crossover and a power based crossover with respect to parent nodes neighboring to a source node;
c) performing a mutation operation with respect to the parent nodes and the child nodes;
d) determining relay nodes by converting order and power information of each node of the chromosome into routing tree information, and determining power of the relay nodes; and
e) selecting a broadcast routing path using the number and power of the relay nodes.

### Claim 2 (depends on 1)

The method according to claim 1, wherein the step a) further comprises the steps of:
connecting the nodes of the network to the source node directly or through the relay nodes in order for the broadcast routing; and
setting a connection order of the nodes and power for data transmission.

### Claim 3 (depends on 1)

The method according to claim 1, wherein the connection order is to connecting the nodes to the source node directly or through the relay nodes.

### Claim 4 (depends on 1)

The method according to claim 1, wherein the power is energy that is necessary to receive data and transmit the received data in each of the nodes.

### Claim 5 (depends on 1)

The method according to claim 1, wherein the step b) comprises the steps of:
b1) comparing transmission powers of first and second parent nodes neighboring to the source node, and selecting one parent node having a lower transmission power;
b2) comparing transmission powers of third and fourth parent nodes neighboring to the source node, and selecting one parent node having a lower transmission power; and
b3) creating first and second child nodes by mutation of the selected parent nodes.

### Claim 6 (depends on 5)

The method according to claim 5, further comprising the steps of:
when transmission power of the first child node is lower than or equal to transmission powers of the first and second parent nodes, determining the parent node having a lower transmission power and the first child node as a next generation pool of the parent nodes;
when the transmission power of the first child node is greater than the transmission powers of the first and second parent nodes, determining the first and second parent nodes as a next generation pool;
when transmission power of the second child node is lower than or equal to transmission powers of the third and fourth parent nodes, determining the parent node having a lower transmission power and the second child node as a next generation pool; and
when the transmission power of the second child node is greater than the transmission powers of the third and fourth parent nodes, determining the third and fourth parent nodes as a next generation pool.

### Claim 7 (depends on 5)

The method according to claim 5, wherein the step b3) comprises the steps of:
generating a value ranging from 0 to 1; and
when the generated value is less than a preset first reference value (R_ORDERCROSSOVER(0.5)), performing an order-based partially matched crossover (PMX) on the two parent nodes to determine an order value of the first and second child nodes.

### Claim 8 (depends on 5)

The method according to claim 5, wherein the step b3) comprises the steps of:
generating a value ranging from 0 to 1; and
when the generated value is less than a preset second reference value (R_POWERCROSSOVER(0.5)), performing a power-based blend crossover (BLX) on the two parent nodes to determine a power value of the first and second child nodes.

### Claim 9 (depends on 1)

The method according to claim 1, wherein the step c) comprises the steps of:
c1) changing an order by selecting a pair of nodes from the one chromosome; and
c2) changing a real number generated from [0, maximum power value] into a power of the node by selecting one node from the one chromosome.

### Claim 10 (depends on 9)

The method according to claim 9, wherein the steps c1) and c2) are performed independently.

### Claim 11 (depends on 9)

The method according to claim 9, wherein the step c1) comprises the steps of:
generating a value ranging from 0 to 1; and
when the generated value is less than a preset third reference value (R_ORDERMUTATION(0.001)), performing an order based mutation operation on the parent nodes and the child nodes.

### Claim 12 (depends on 9)

The method according to claim 9, wherein the step c2) comprises the steps of:
generating a value ranging from 0 to 1; and
when the generated value is less than a preset fourth reference value (R_POWERMUTATION(0.5)), performing a power based mutation operation on the parent nodes and the child nodes.

### Claim 13 (depends on 1)

The method according to claim 1, wherein the step d) comprises the steps of:
d1) sorting the nodes contained in a set (C) of the nodes covered by power of the source node in ascending order;
d2) when there are nodes that are not covered among neighbor nodes of the nodes, determining the corresponding nodes as relay nodes;
d3) adding nodes covered by a relay operation of the determined relay nodes to the set (C); and
repeating the steps d1) to d3) until all of the nodes of the chromosome are covered.

### Claim 14 (depends on 1)

The method according to claim 1, wherein the step e) comprises the steps of:
e1) calculating number of the relay nodes and power consumption thereof according to the broadcast routing path; and
selecting a broadcast routing path in which the number of the relay nodes and the power consumption thereof are minimum.