Method to establish and organize an ad-hoc wireless peer to peer network

[Background of invention]

[Field of invention]

The present invention relates to an ad hoc wireless network for communication in a mobile environment. More specifically, the present invention relates to establishing and maintaining an ad hoc wireless network between mobile devices in order to achieve communication almost instantly.

[Related application]

This application is related to US Patent Provisional Application No. 60 / 643,373 filed on January 11, 2005 and claims its priority.

[Description of related technology]

Whether it's a wireless home network, a wireless office network, a so-called "hotspot" network in a local cafe, fast food chain or hotel, or even implementing WiFi technology throughout the city, wireless technology is a part of today's life. It has become widespread in every aspect. The purpose of promoting wireless in this way in society is to make information more accessible and to further increase the productivity that society as a whole has enjoyed by widely accepting and using computer networks, especially the Internet. Wireless networking technologies like 802.11a / b / g allow WiFi-enabled devices to connect to each other as if they were in a standard wired network, without the constraints of communication lines. become. Within the network communication area, people are free to stay connected to the network, regardless of their physical location.

To this end, several cities have sought to build wireless networks for them. For example, on July 29, 2004, Grand Haven, Michigan, became the "first WiFi city in the United States" by building a city-wide wireless network covering a city of 6 square miles and extending 15 miles to Lake Michigan. Claimed the honor of being. Many city officials see WiFi as an essential infrastructure to attract and maintain businesses, as well as sewage, electricity, telephone and transportation. Benefits of such a system for city officials range from providing a means of communication between city officials to providing administrative service announcements, warnings and other useful information to the entire population.

In the process of improving wireless connectivity, one area of daily life is lagging behind. American roads and highways remain largely untouched when it comes to wireless technologies other than satellite positioning systems and mobile phone systems. However, implementing wireless network technology on American roads has a number of advantages. Most notable are traffic information, amber alerts, weather alerts, etc., which can be immediately relayed to all affected vehicles.

In addition, networking vehicles with each other allows vehicle information that affects other vehicles nearby to be relayed. For example, a car may suddenly brake. This action can be instantly reported to all vehicles behind the braking vehicle so that the drivers of other vehicles can take the necessary steps before they fall into an imminent situation. become able to. It is clear that this feature is meaningful for alleviating traffic accidents and congestion. This type of wireless networking can manifest itself in many aspects of vehicle safety applications, including, but not limited to, emergency road obstacle warnings, intersection coordination, hidden roadway warnings, lane change or merging assistance. is there.

Vehicle safety communication (VSC) can be broadly divided into vehicle-to-vehicle communication and vehicle communication via infrastructure. In vehicle-to-vehicle communication, vehicles communicate with each other without the support of a fixed infrastructure. Vehicles communicate with each other when they are within radio range of each other or when multi-hop relay is possible through other vehicles. In vehicle communication via infrastructure, vehicles communicate with each other with the support of infrastructure such as roadside wireless access points. In this case, the vehicle can also communicate only with the infrastructure.

Important VSC performance requirements are low latency (about 100 ms) and maintaining throughput (in other words, close) to assist various VSC applications such as collision avoidance. Includes the percentage of successful vehicles receiving the warning message).

Simply attaching a wireless antenna to a moving vehicle and then communicating uncoordinated will not meet these requirements. Specifically, since the radio bandwidth is limited, transmission of data without coordination will cause the communication radio waves to overflow with a plurality of messages, resulting in radio wave interference.

In that case, these vehicles would interfere with each other's transmission and compete with each other for radio bandwidth for transmission. Furthermore, all messages will propagate in all directions without considering the desired transmission direction.

Moreover, each vehicle will not be consistent with the network configuration of the other vehicles.

Due to the high mobility and lack of unique relationships, it is difficult to pre-configure vehicles as a vehicle group (ie, no vehicle knows anything about vehicles in its vicinity in advance). All information required to establish inter-vehicle safety communication must be exchanged between vehicles in near real time, and vehicles in the group should configure themselves in approximately real time to perform safety communication. Must be able to. High mobility of uncoordinated vehicles means that nearby vehicles and vehicle groups change frequently, making it difficult to use support servers (for mobility, address, name, media session) within the vehicle group. It means that. Due to these significant differences, existing ad hoc networking technologies cannot be applied directly to vehicle groups for secure communications.

Using WiFi methods used elsewhere, such as hotspots, is impractical due to communication area, data traffic volume, and latency issues. Normal rush hour commuting in big cities can result in a vehicle density of as many as 600 vehicles per 1200 meters long on a three-lane highway. In addition, all of these vehicles pass through individual communication areas at speeds of 30-60 mph. Most wireless systems are not capable of handling such large rates of change within the network.

Specifically, when a vehicle enters the communication area, it needs to be identified by a wireless access point or router and receive a configuration command. When a vehicle leaves the communication area, the wireless access point or router needs to update the record and remove the vehicle from the network. Therefore, the speed at which a vehicle passes through a particular communication area determines the frequency of information updates, that is, the handshaking requirements that are transmitted by wireless access points and routers and should be responded to by all vehicles within that range. If all these vehicles send information at the same time, they quickly exceed the capacity of the system.

Several attempts have been made to establish a vehicle-to-vehicle communication network. For example, FleetNet and CarTalk2000 both build vehicle-to-vehicle communication networks. Both of these systems use GPS systems within each vehicle to obtain location information. FleetNet uses both fixed and mobile nodes as the infrastructure for "ad hoc" networks. Fixed nodes serve as server routers, gateway routers, and client-server routers. With multiple fixed nodes in this way, significant financial and overhead costs are incurred to install, maintain, and manage the infrastructure. In addition, the FleetNet system uses location-based routing and location recognition. Specifically, location data plays a decisive role as an important element for those systems in the communication protocols implemented.

CarTalk2000 also uses a location-based protocol. Each vehicle participating in the CarTalk 2000 inter-vehicle inter-vehicle system must be equipped with a GPS device to always detect its current position. In addition, CarTalk2000 uses a number of different routing protocols, such as topological information routing, procedural routing, or reactive routing such as ad hoc on-demand distance vector routing, dynamic source routing, and hybrid routing. .. Each of these protocols uses complex and distinct protocol rules.

The main drawback of the CarTalk2000 system is that finding nearby nodes significantly increases the amount of data transferred. Each node periodically sends a beacon to notify nearby vehicles of its presence. In areas of high traffic, this can result in beacon message collisions.

However, these GPS networks have major drawbacks. In a highly mobile vehicle environment, GPS information quickly becomes ineffective. Exchanging constantly changing GPS information between vehicles to perform GPS location routing results in excessive protocol overhead and wasted radio bandwidth. As a result, such GPS location routing techniques cannot achieve minimum communication delay times or maintenance of multi-hop throughput.

Therefore, configure an ad hoc network that can meet stringent VSC performance requirements while maintaining minimum communication latency and multi-hop throughput without requiring excessive bandwidth or significant protocol overhead. Is needed.

<p> [A brief overview of the invention]</p><p> Therefore, an object of the present invention is to create a communication boundary suitable for communication between mobile devices by grouping a plurality of mobile devices into a management group such as a local peer group (LPG), and coordinate message transmission. It is to relay and control the range and direction of message propagation. Furthermore, it is an object of the present invention to provide a simple protocol for establishing and maintaining local peer groups, dynamically assigning identification information, and periodically updating the relative order of mobile devices.</p><p> Disclosed are methods of organizing and maintaining ad hoc networks for communicating between multiple mobile devices. The method involves grouping multiple mobile devices into at least one local peer group (LPG) and multiple devices within each LPG based on their relative location within each LPG. The unique identifier is based in part on the LPG in which the corresponding mobile device is located, including the step of ordering and assigning a unique identifier to each of the multiple mobile devices.</p><p> There are two types of LPG: fixed LPG and dynamic LPG. The location and size of the fixed LPG is predefined and programmed into the memory of each mobile device. Dynamic LPG is formed on the basis of clustering of one or more of a plurality of mobile devices. The network can include fixed LPG and / or dynamic LPG.</p><p> Each LPG is divided into equivalent cells (ECs) defined by a group of mobile devices. Each mobile device in this group is within one hop of each other and can communicate with any mobile device in this EC with only one message transmission. Each EC is controlled by the Equivalent Cell Header (ECH).</p><p> Update the relative positions of mobile devices to address the reordering caused by the movement of multiple mobile devices. Ordering and reordering can be achieved by creating a position vector that represents the relative position of each mobile device within each LPG.</p><p> The position vector initializes the position vector, sends the initialized position vector to another mobile device participating in the LPG, and another mobile device compares its position with the position information contained in the transmission. , Based on that comparison, is generated by inserting the position value of this other mobile device into the position vector and sending the updated position vector to all other mobile devices in the LPG.</p><p> Alternatively, the reordering and reordering of mobile devices sends a message containing the location of the first mobile device, instructions in the intended message direction, and the time of transmission, and the second mobile device receives the outgoing message. , Estimate the displacement of the first mobile device based on the received outgoing message, calculate and calculate the current position of the first mobile device based on the estimated displacement and the position of the first mobile device This can be achieved by comparing the current position with the position of the second mobile device. The second mobile device relays or forwards the message only when it is determined that the second mobile device is in the intended message direction.</p><p> The unique identifier for each mobile device is unique to LPG. Therefore, the unique identifier of the mobile device is changed when the mobile device changes the LPG. In addition, mobile devices located near the boundary between two adjacent LPGs or within the overlapping area of adjacent LPGs are assigned two IP addresses to allow communication between the adjacent LPGs.</p><p> This unique identifier may be an IP address. IP addresses can be assigned based on a given network prefix that is associated with unique LPG identification information and unique mobile device identification information. Unique LPG identification information and unique mobile device identification information can be calculated from the hash function. Alternatively, the unique LPG identification information and the unique mobile device identification information can be provided from an external wireless device communicating with the mobile device.</p><p> Each mobile device can be classified according to the type of mobile device, and a unique identifier can be assigned based on this classification.</p><p> These and other features, benefits and advantages of the present invention will become apparent by reference to the accompanying drawings. It should be noted that, throughout the drawings, similar reference numerals refer to similar structures.</p>

[Detailed description of the invention]

According to the present invention, a plurality of nodes, that is, mobile devices, are organized into manageable groups. These groups are used to coordinate data transmission between nodes. Groups are constructed based on the relative position of nearby nodes or on a fixed position. This grouping, or local peer group (LPG), is the basis for routing radio signals within a single LPG or between multiple LPGs. Radio signals include vehicle safety applications and information applications.

The purpose of LPG is to build a degree of coordination between multiple nearby nodes. The nodes near these are mobile devices capable of wireless communication. The mobile wireless device may be a PDA, laptop, mobile phone, or vehicle to which or incorporates the wireless device. Specifically, the mobile device includes a vehicle equipped with a communication device installed in the vehicle or individually brought into the vehicle, and a pedestrian carrying the communication device.

There are two types of cooperation. The first type is close coordination of adjacent mobile devices and is used for intra-LPG communication. In-LPG communication is used to support almost instantaneous message transmission. For example, the transmission of emergency road obstacle warnings and other types of emergency or safety messages will be performed using intra-LPG message transmission. These messages generally require a delay time of around 100 msec.

The second type is loose coordination, that is, grouping nearby mobile devices. This type of coordination is used to support inter-LPG communication between linked or interconnected LPGs. For example, inter-LPG communication can be used for road recognition applications and for driver visibility enhancement.

LPG not only supports efficient and reliable mobile device-to-mobile communication, but also communicates between mobile devices and fixed infrastructure so that mobile devices and road infrastructure can be integrated into one complete communication network. Can also help.

FIG. 1 shows two LPGs, the first LPG100 containing four nodes 110, 111, 112 and 113. Each of these four nodes 110, 111, 112 and 113 can transmit data to each other. The second LPG 120 includes nodes 121, 122, 123, 124, 125 and 126. Nodes 121-126 can each send data to each other. This type of transmission is intra-LPG transmission and is instantaneous. Nodes 110 to 113 in LPG100 can transmit data to nodes 121 to 126 in LPG120 by using inter-LPG communication. The two LPGs 100 and 120 form an ad hoc network 150.

There are two types of LPG: fixed LPG and dynamic LPG. Fixed LPG uses pre-assigned group position definitions to divide mobile devices. In contrast, dynamic LPG can properly combine mobile devices based on the (dynamic) radio area for communication by nearby mobile devices.

FIG. 2 shows a plurality of fixed LPGs (LPG1 to 8) 200 to 207. Each LPG is defined by a particular location or area. That is, if a wireless device or mobile device is in Area 1, that device is LPG1. If the wireless or mobile device is in Area 2, the device is LPG2, and so on. The individual size of fixed LPG is a design choice and is determined according to various factors such as radio antenna range, communication range, number of mobile devices, terrain, environmental conditions, traffic patterns and population density. The location and size of fixed LPGs are fixed, but traffic patterns and population (moving device) densities vary from place to place, so each fixed LPG may be of a different size. In general, the LPG size should be larger than the wireless communication range to enable multi-hop communication. In addition, fixed LPGs can also overlap with areas between adjacent LPGs to facilitate efficient inter-LPG communication. The overlapping areas can have a size that fits the situation to accommodate a variety of situations (eg, different speeds depending on the mobile device).

According to one embodiment of the invention, the boundaries for fixed LPG are based on predetermined areas such as zip code and area code. The zip code usually corresponds to the population density. Population density in an area is a good indicator of traffic patterns and the number of mobile devices in that area.

Network architectures based on fixed LPG require mobile devices to be equipped with a Global Positioning System (GPS) or some other location information. This allows the mobile device to identify or detect the fixed LPG to which the mobile device belongs. The mobile device changes the fixed LPG as it changes position. Therefore, the mobile device needs to periodically receive the updated position data. This cycle depends on the speed or speed at which the mobile device moves. Mobile devices include a database of LPGs and their locations.

Fixed LPGs have the great advantage of being able to integrate with the wireless infrastructure to provide backbone access and inter-LPG communication, even when some LPGs are empty or there are not many mobile devices within the LPGs. Have.

Each fixed LPG is assigned a unique identifier to facilitate communication. In one embodiment of the invention, a unique identifier for a fixed LPG is assigned based on the zip code of that LPG. This method leverages an existing zip code database. Therefore, it is not necessary to create a new identification number. Alternatively, in another embodiment, GPS coordinates of fixed LPG can be used. Similarly, the method utilizes a predetermined database. In another embodiment, state and city names can be used as unique identifiers for LPG. Alternatively, any combination of the above embodiments can be used to assign an LPG-specific identifier. The unique identifier of LPG is used as part of the unique identifier of the mobile device, as described below.

Forming and naming LPGs is easier than dynamic LPGs because all fixed LPG areas are clear. Moreover, when using fixed LPG, you do not have to worry about the rules for merging or splitting LPG.

FIG. 3 shows a plurality of dynamic LPGs (LPGs A to E), 300 to 304, respectively. In contrast to fixed LPG, dynamic LPG is formed based on the wireless communication area of nearby mobile devices so that mobile devices can coordinate communications without worrying about their exact location.

Since dynamic LPGs are formed based on the wireless communication area, mobile devices within the LPG can always communicate with each other via one-hop or multi-hop transmission. The mobile device can control the size of the dynamic LPG in order to keep the number of mobile devices in each LPG reasonably small and to enable efficient communication with short delays. Moreover, in contrast to fixed LPG, dynamic LPG ensures that communication is always possible within each LPG.

In one embodiment, the ad hoc peer-to-peer network can be built from one or more fixed LPGs, or from one or more dynamic LPGs. In another embodiment, the ad hoc peer-to-peer network can be constructed from both fixed LPG and dynamic LPG as a hybrid LPG network. The hybrid LPG network combines the advantages of fixed LPG and dynamic LPG while eliminating the problems that arise when they are adopted separately.

One of the advantages of fixed LPG is the ability to easily group mobile devices by area and interact with the infrastructure. Further, as will be described in detail later, the fixed LPG makes it possible to easily assign an address designation identifier, that is, a unique identifier, to each mobile device. In addition, all nodes are aware of the topology and structure of the entire network. Therefore, nodes or mobile devices can be easily tracked.

Dynamic LPG has several advantages. One of these advantages is that dynamic LPG does not require pre-configuration because the network is formed based on node clustering. Furthermore, dynamic LPG allows more freedom to form, merge, and divide LPG, and once formed, all vehicles can communicate at once. Therefore, communication between nearby mobile devices is even easier.

The disadvantage of fixed LPG is that it requires more widely ubiquitous roadside radio access points, roadside gateways, roadside data storage (for deposit and retrieval), which is not necessary for dynamic LPG. In contrast to.

The hybrid method utilizes the topology of the road. Specifically, when infrastructure is unavailable, dynamic LPG is used to form the network. When infrastructure becomes available in an area, fixed LPG can be used to network with dynamic LPG and infrastructure.

For example, infrastructure such as road infrastructure will enable road-to-vehicle communication and road support (road-to-vehicle) communication. This is especially useful when using fixed LPG. In addition, the road infrastructure facilitates communication from the infrastructure to the vehicle. This type of communication is to disseminate specific emergency information such as hidden driveway warnings, electronic road signs, road conditions, railroad crossing warnings, route guidance and navigation, highway merging assistance, intersection collision warnings, and construction section warnings. Is important to.

There are two main types of LPG. One is unordered LPG and the other is relatively ordered LPG. In relatively ordered LPG, at least some of the mobile devices recognize the relative position of nearby mobile devices. Relative ordering is the basis for routing messages within LPG. Being able to detect and recognize the relative order and orientation of nearby mobile devices will enable efficient message routing within the LPG environment. This efficient routing is important when the message is an emergency message in a road environment. For example, some vehicles may specify that warning messages go behind LPG. The vehicle in front of the vehicle transmitting in LPG does not need to receive or relay the message. Since the vehicle knows the relative direction, it can direct the message in the appropriate direction, thereby reducing the amount of relay traffic and bandwidth used.

Directional detection or recognition can be derived from the relative order of the mobile device. In one embodiment, the relative ordering is done "on-demand". In another embodiment, the relative ordering is maintained cyclically.

FIG. 4 shows a method of ordering LPG "as needed" according to an embodiment of the present invention. The process begins at step 400. The first mobile device. A message containing the GPS location, current speed and time stamp of the mobile device is sent with the intended message direction. In step 410, the second mobile device receives this message. In step 420, the second mobile device estimates the current position of the first mobile device. The estimation of the current position of the first mobile device can be made based on the possible displacement of the first mobile device from the previously known position of the first mobile device. The previous location is determined directly from the received message. Possible displacements are calculated based on the estimated velocity and time difference. Since the received message contains a time stamp, the second mobile device calculates the time, that is, the difference from that time stamp to the time the message was received. In this case, in those mobile devices, both the clock and GPS information times need to be synchronized, that is, the GPS devices need to be synchronized. The estimated speed can be calculated in several different ways. In one embodiment, the (instantaneous) speed of the first mobile device is included in the message sent by the first mobile device. This speed can be used by the second mobile device to estimate the current speed of the first mobile device. In another embodiment, the second mobile device can use its own speed as the speed of the first mobile device. Alternatively, a predetermined estimated speed can be used. The predetermined estimated speed will be pre-stored in the memory of the mobile device as a database that may change based on the speed limit, time of day, location, weather conditions and terrain. The second mobile device multiplies the estimated velocity by the time difference to determine the possible displacement. This value is the possible displacement from the previous position and adjusts the previous position of the first mobile device.

In one embodiment of the invention, the displacement of the first mobile device has an orientation component. In this embodiment, the estimated displacement takes into account the change in orientation. A change in position is applied to the previous position of the first moving device with respect to the direction of movement. In one embodiment, the first mobile device can include the GPS orientation (eg, NW, SE35 °) in its message (along with its position, time stamp, etc.) and the information in this orientation is exact. Used by a second mobile device to estimate the displacement. Alternatively, in another embodiment, the second mobile device utilizes local terrain information to allow the first mobile device (without the first mobile device transmitting orientation information). Orientation can be estimated. That is, both mobile devices may be traveling along the same road, which is used to estimate the orientation of the first mobile device. Therefore, the second mobile device can apply the calculated displacement to its previous position (of the first mobile device) in the direction in which the second mobile device is moving.

In step 430, the second mobile device compares the calculated estimated position of the first mobile device with the current position of its own node to determine the relative order of the two mobile devices.

The second mobile device relays or forwards the message only when it is determined that the own node is in the intended message direction. When the position and orientation of the own node are between the mobile device on the transmitting side and the mobile device on the receiving side, the mobile device is in the intended message direction. Specifically, the second mobile device uses the calculated relative order or position to determine if the second mobile device is along the intended path.

In one embodiment, orientation information is used to determine if the second mobile device is following the intended path. This orientation information is used by the second mobile device to derive the estimated position of the first mobile device, as described above. When the relative order between the two mobile devices is determined as described above, the second mobile device has the orientation of the first mobile device included in the message of the first mobile device and its own orientation. By using, it is possible to determine whether or not the second mobile device is on the intended message transmission path of the first mobile device. For example, both mobile devices have similar orientations (ie, traveling along the same road) and the second mobile device is in front of the first mobile device (determined by its relative order). If the intended message direction is in the same direction, the second mobile device forwards the message (of the first mobile device), while the intended message direction is. When having the opposite orientation, the second mobile device does not forward the message. In another embodiment where the first mobile device does not send information about its orientation as a message, the second mobile device moves the first, for example, by estimating the displacement with respect to the previous position, as described above. The orientation of the device can be estimated. Once the orientation and relative order of the two mobile devices is known, the second mobile device will perform the message transmission intended by the first device in the same way as described above. It can be determined whether or not it is along the route.

If the second mobile device is not in the path, the message will not be forwarded. The ordering of mobile devices according to this embodiment has the advantage that the bandwidth is not congested with the ordering request when the ordering of the mobile devices is not important.

In another embodiment of the invention, the relative order of the mobile devices is periodically updated with a position vector. FIG. 5 shows an example of ordering LPG using this method. FIG. 5 shows the LPG500 with the LPG position vector V510. LPG is mapped to a one-dimensional array or vector V510. Each mobile device in the LPG500 will have one vector ID. The vector ID is exactly the position index of V. As shown in FIG. 5, the vector V510 represents the order of the positions of the mobile devices. In Figure 5, there are 6 different relative sequences 1-6. The arrow indicates the direction of movement of the moving device, for example, the flow of traffic.

The position vector V510 allows the mobile device to control the direction of information transmission. Specifically, the position vector V510 can be used to route information within a peer group. For example, as shown in Figure 5, if the sender's mobile device with index 3 indicates that the message is directed to a mobile device with an index less than 3, then index j &lt;3. Only mobile devices with will relay the message. This is achieved by indicating that the message is directed to a vehicle with an index less than j. The relay continues until the message reaches the rear boundary node of LPG, or until the message reaches the maximum number of hops. In the same way, forward information propagation can be achieved.

Furthermore, the routing priority can be promoted by using the position vector V510. The MAC layer can generate access priorities based on this position vector 510. Generally, in that network, the mobile device in front (forward of LPG) has a lower position index because it is likely that the mobile device in front observes the warning event and deserves to use the radio channel with higher priority. The mobile device in the part) is given a higher access priority.

FIG. 6 shows a method of creating a position vector V510 according to an embodiment of the present invention. The process begins in step 600 by initializing the position index I when the mobile device, eg, node N, joins the LPG. Node N contacts this node by receiving a message from at least one other mobile device already in the LPG (eg node L). In step 602, node N knows the position of node L based on the received message including the GPS position of node L. Node N compares the received position information with its own GPS information, and inserts itself into the vector V510 based on the comparison. Node N then sends a new position vector V510 to other mobile devices in the LPG (eg node L). For example, if node N is in front of node L and node L is at the front end position with an index of N, in step 605 node N gives itself the value of N-1 as its position index. Assign, become the new front end of LPG. On the other hand, when node N is behind node L and L is the rear end position having an index of n, in step 610, node N assigns itself a value of N + 1 as its position index. Then take over the node position.

If the mobile device with the index of n (eg node L) is neither the front end nor the rear end, node N joins the center of the LPG. At that time, as described above, node N inserts itself into position V by comparing GPS and node L in step 615, and then in step 620 everything behind the insertion point. Trigger an index update for mobile devices. At that time, other nodes behind the insertion point update their position index based on the change in their GPS position.

Alternatively, instead of automatically triggering another mobile device update when a new node or mobile device is inserted, the new mobile device is assigned an index n + 1 and all have an index greater than n. The mobile device increments those indicators by one.

Another alternative to automatically updating or incrementing the position vector V510 is to increment other mobile devices within a given position interval. This will reduce the frequency of index updates. The centrally participating node N is assigned an index derived from the interval of values between n and n + K and does not need to increment the index of the mobile device with a position greater than n + K. Only mobile devices within this interval (n ~ n + k) need to update their position index.

In addition, the position vector V510 can be updated to maintain the relative order of the mobile devices within the LPG, i.e., when the mobile devices join the LPG. Each mobile device can periodically update its position index. The position index (i) of the mobile device in the LPG can be maintained so that the position vector V510 contains the current relative position of the mobile device in the LPG. Specifically, the position index can be updated as mobile devices pass each other and change their relative position. The mobile device position index is swapped when the two mobile devices swap their relative positions. For example, at periodic intervals, mobile devices swap or transmit their GPS positions and swap position indexes if their relative positions swap. The period can be adjusted based on network type, terrain, time of day, traffic pattern and message type, or LPG location. For example, updates are more frequent when the mobile device is around an exit / entrance ramp or intersection, and less frequent when it is between an exit / entrance ramp or an intersection. By increasing the update interval, the overhead for maintaining ordering consistency can be reduced.

However, GPS or location information exchange has particular drawbacks in the road environment. Specifically, the number of mobile devices in the LPG will result in a large amount of GPS coordinates being constantly communicated (in an attempt to keep up with changes in relative position). In addition, the resulting position calculation may not be accurate enough, as the GPS coordinate error can be in the same digits as the distance of the mobile device. Furthermore, the above method requires a large amount of computation, one in general, GPS information is already outdated when other mobile device receives the information.

In another embodiment, the relative order of mobile devices can be determined by using messages and position vectors without using GPS information. As mentioned above, maintaining ordering using GPS techniques can incur significant overhead, especially when the number of mobile devices is high. In this embodiment, the LPG is divided into several small groups, namely equivalent cells (ECs). Each EC is assigned one position index. An EC is a group of nearby mobile devices within the same wireless communication area. An EC is a segment of LPG in which all mobile devices in the EC have the same vector index, and message transmission can be received by all mobile devices in the EC without the need for relaying.

In order to disseminate information using EC as a basic unit, EC is formed to link with other EC. FIG. 7 shows a plurality of ECs (EC1 to 5) 701 to 705 in the LPG700. The EC701 to 705 can be arranged in the LPG700 so that the wireless communication areas overlap. In the network shown in Figure 7, the relative order of LPGs is maintained across ECs, reducing overhead. In addition, the message is relayed only once per EC, improving bandwidth efficiency.

For example, mobile devices in one EC can communicate with each other in one packet transmission. Each EC is organized so that several mobile devices within the EC can relay packets as needed. The EC can be ordered within the LPG, allowing messages to hop along the EC. Specifically, if one mobile device in EC3 703 wants to send a packet, that mobile device sends the packet (once) to the adjacent EC2 702 and EC4 704. This ensures that packets are delivered to all mobile devices within EC2 702 and EC4 704. This packet is relayed by EC2 702 and EC4 704 to their individual adjacent ECs by only one packet per EC. This type of inter-adjacent EC routing, with only one packet per adjacent cell, can minimize packet transmission within the LPG.

EC is maintained and controlled by a single equivalent cell header (ECH). Each ECH711-715 is linked to its adjacent ECH so that all ECH711-715 in the LPG are serially linked either directly or indirectly. ECH711 to 715 are connected in the order of radio hop count and serve as a forwarding node for their LPG. Only ECH711-715 are responsible for relaying messages, thereby minimizing unnecessary traffic.

In this embodiment, ECH orders itself and maintains those orders to achieve ordering for LPG. Each ECH notifies its presence within its LPG by sending a pre-defined message. This message is sent periodically to provide a list of linked ECHs. That is, this message includes ECH nodes one hop, two hop, and three hop ahead in the position order as seen from the transmitting ECH. The list is received by another ECH, which causes the other ECH to update its list and store it in memory. Non-ECH720 also updates their list. This will ensure that all ECH lists match each other. The list represents the relative order of each ECH. This facilitates determination of the direction of movement and the direction of transmission.

In one embodiment, the outgoing message is the ID of the originator sending the message and the first list of ECH nodes that the originator can see along the first communication path of the EC connected in order. Includes, optionally, a second list along the second communication path of the EC connected in order. Yet another list may be provided, with each linked ECH (LECH) list centered around the source ECH, one branch of the EC connected in order, that is, all that meet along the communication path. Contains the ECH ID of the ECH node.

For example, each ECH knows the relative position of the ECH immediately adjacent to it. That is, the ECH of EC3 703 is known to have different directions of ECH of EC2 702 and EC4 704 based on the list or vector transmitted by the ECH of EC2 702 and EC4 704, respectively. EC3 703's ECH sends a message containing this information. In addition, the EC2 702 ECH is known to have different directions for the EC1 701 and EC3 703 ECH, based on the list or vector transmitted by the EC1 701 and EC3 703 ECH, respectively. This information is combined and stored as a list maintained by each ECH.

As a result, by using the relative order of ECH, messages can be routed in the appropriate direction without using any GPS information.

Alternatively, in another embodiment, all mobile devices are equipped with directional antennas in important directions (eg, front, back, left and right, and possible diagonal directions) in these directions. The presence of other mobile devices can be detected. Any mobile device can instruct the message to travel backwards in the peer group, and any mobile device that sends and receives the message only at a directional antenna pointing behind it. , Can only be relayed by an antenna pointing behind it. This technique provides basic orientation detection, but does not provide relative position between mobile devices.

Mobile devices according to the invention include wireless devices that are attached to, incorporated into, or used in combination with the mobile device. FIG. 8 shows a wireless device according to the present invention. The wireless device according to the invention includes a computing device 800 having a transmission means 802, such as a wireless transceiver, to provide wireless communication between nodes within the wireless communication range. Further, the control means 804, such as a microcontroller, a microprocessor, etc., is configured to receive a signal from another node through the transmitting means 802 and transmit a signal to the other node through the transmitting means 802. The control means 804 also provides motion control by executing an instruction. The storage means 806 is located in the computing device 800 and operably communicates with the control means 804. As the storage means 806, a memory module, a removable medium, a combination of a large number of storage devices, and the like can be used, and the storage means provides processor executable instructions required to execute the protocol of the above embodiment. Has enough capacity to store. Further, the timing means 808 is provided as a separate component or by one function of the control means 804. Timing means 808 provides time interval tracking required for each timer referenced in the above embodiments. A voltage supply means 810, such as a power supply, is electrically connected to all components of the computing device 800 to provide operating power to the components as needed. The wireless device further comprises an internal clock that maintains the clock for the wireless device and is used as a time stamp for all messages. Further, the wireless device includes address allocation means 812 and network interface means 814. Alternatively, the address assigning means 812 can be part of control means 804.

Processor-executable instructions for executing the above embodiments can be built into a storage means 806 in the form of EPROM, flash memory, or other such non-volatile storage device. In addition, processor executable instructions can be stored on computer-readable media such as optical or magnetic media, or downloaded over a network (eg, the Internet). It is preferred that the user be able to periodically update the processor executable instructions as they become available, as needed, to further enhance the system.

Each mobile device will be assigned a unique identifier to facilitate sending and receiving messages over ad hoc networks. As the unique identifier, any number uniquely assigned to the mobile device can be used so that the mobile device in one LPG cannot be assigned the same unique identifier. This identifier must be assigned promptly, if necessary, to accommodate instant communication. As described above, the unique identifier can be any number or address that facilitates communication, such as a MAC address, VIN number, or IP address, but here, for the purpose of illustration, an IP address is assigned. Will be described. Mobile devices typically have at least one IP address. However, in one embodiment, the mobile device is assigned two IP addresses to support both intra-LPG communication and inter-LPG communication.

In a preferred embodiment, the IP address is based on a dedicated network prefix, a unique identifier for LPG, and mobile device identification information. Specifically, the IP address can be assigned based on a unique number corresponding to a specific mobile device concatenated with a predetermined network prefix. Here, the unique number is based on the LPG in which the mobile device exists and the number corresponding to the mobile device.

Similar assignment techniques can be used to assign addresses to both fixed and dynamic LPGs, but address assignments are described individually for each type of LPG.

In the case of fixed LPG, in one embodiment of the invention, the IP address may be a standard network prefix and LPG ID concatenated with a MAC address and a VIN number or a hash value of time. The use of hash functions is especially important when the address space is limited, ie IPv4. According to this embodiment, the mobile device will be assigned its own IP address.

In an ideal situation, LPG has only N (N is the maximum address space) mobile devices so that address space constraints are virtually insignificant. This makes it easy to assign a private class to each LPG. Each mobile device in LPG has a different subordinate part of the IP address. This IP address can be reused in different LPGs as long as the LPGs are not close to each other.

However, typically, LPG can be higher than N mobile devices. Therefore, the given hash function is stored in the memory section of the mobile device. The address assigning means 812 accesses this predetermined hash function from memory and assigns a lower part of the IP address. The hash function converts multiple input numbers into M-bit numbers (where M is the maximum number of bits in the lower part of the IP address). The plurality of input numbers can include a VIN number, a MAC address and the time when the mobile device participated in LPG.

The standard network prefix is the upper part of the IP address. Standard network prefixes are also stored in memory. In addition, IP addresses are LPG-specific. Part of the IP address is used to identify the particular LPG where the mobile device is located. A database of LPG locations and associated LPG IDs is also stored in memory. When a mobile device enters a new LPG area, the mobile device must change its IP address to reflect the specific IP address associated with that LPG. The advantage of fixed LPG is that the LPG position is fixed and clear. This makes it easy to assign an LPG ID.

Alternatively, in another embodiment of the invention, part or all of the IP address can be assigned by a fixed radio device within the LPG. For example, part of the IP address can represent the sequence or order in which the mobile device entered LPG. In this case, an external wireless device that transmits the sequence number to the incoming mobile device is required. Connections can be established through query-relay-response type operations. When a new mobile device enters LPG, it queries (through transmission). The inquiry is relayed to a predetermined external wireless device by another mobile device in LPG. The external wireless device may include a roadside gateway device, another mobile device such as a reader, or a first mobile device within the LPG. The external wireless device acts as a DHCP server.

The external wireless device responds to the query by generating a sequence number or IP address and sending the response. This sequence number is used as the lower part of the IP address instead of the hash value. The sequence number is concatenated with the higher part of the IP address, as described above. Using this method, the IP address can change continuously as the sequence changes as a result of the mobile device constantly moving. Alternatively, the entire address can be sent to mobile devices entering LPG.

In another embodiment of the invention, if the IP protocol corresponds to a wide range of IP addresses, the IP address may be a standard network identifier concatenated with all MAC addresses or VIN numbers. For example, when using the IPv6 protocol, there is a large amount of space for assigning unique addresses to each mobile device without the need for a hash function. The upper 64 bits of the IP address can be dedicated to the LPG ID, and the lower EUI 64 bits can be calculated directly from the MAC address or VIN number.

The upper part of the IP address can contain a standard network prefix and a unique LPG ID. The lower EUI part contains each of the MAC address or VIN number.

Figure 9 shows an example of assigning an IP address according to the IPv4 protocol. FIG. 9 shows four overlapping LPGs, LPG1 901, LPG2 902, LPG3 903 and LPG4 904. The first two three-digit numbers 905 in the IP address represent the standard network prefix "192.168". The standard network prefix "192.168" is the same for all LPGs in the network. The third three-digit number 906 is the LPG ID, which is unique to LPG. As shown in FIG. 9, LPG1 901, LPG2 902, LPG3 903 and LPG4 904 each have a value of 1, 2, 3 and 4 in the third three digit number 906. The fourth three-digit number 907 represents the identification information of each mobile device. This number changes based on the mobile device. This number can be assigned using any one of the above embodiments.

Figure 10 shows one exemplary format for IP addresses in the case of the IPv6 protocol. For illustrative purposes, FIG. 10 uses the same LPG reference code as that used in FIG. The upper part 1000 is shown to be 64-bit and represents the LPG ID, and the lower part 1001 is also 64-bit and represents the mobile device identification information (EUI). Both the upper part 1000 and the lower part 1001 are different for each fixed LPG.

Further, as described above, there may be some overlapping areas between the fixed LPGs in order for the mobile device to smoothly change the LPGs and to facilitate inter-LPG communication. In a preferred embodiment, in overlapping areas, each mobile device has two IP addresses and allows access to both LPGs. When the mobile device approaches the overlapping area, the address assigning means 812 assigns a second IP address to the mobile device. Specifically, the mobile device compares the position of the overlapping area stored in the memory with the current position, and determines whether or not the mobile device is located in the overlapping area or the boundary area. The wireless device has network interface means 814 (ie, 802.11 card). One physical wireless interface can support many logical interfaces. Each logical interface has one IP address. Therefore, each network interface means 814 can have two or more IP addresses. Each IP address can be assigned according to any of the embodiments identified above.

For dynamic LPG, techniques similar to IP address assignment for fixed LPG can be used, but IP address assignment for dynamic LPG is more dynamic. This is because the position of LPG is no longer fixed. In addition, LPG IDs are not constant and change constantly. Furthermore, in the case of dynamic LPG, the allocation of IP addresses for communication between LPGs is different.

In the case of intra-PLG IP address assignment for dynamic LPG, the technique is similar to the technique used to assign an IP address to a fixed LPG for IPv4. Figures 11a and 11b show two different examples of IP address formats for the IPv4 protocol. In both formats, the high-order part of the IP address, the first two three-digit number 1100, is determined by standard network prefixes such as 192.168, 10.0 and 172.12. In one embodiment, the standard network prefix will be a private address. A standard network prefix would be the first two three digits of that address.

The third three-digit number 1101 is the LPG ID. In one embodiment, the LPG ID is randomly generated. The fourth three-digit number is the identification information of the mobile device. This identification number can be assigned based on the hash function of VIN or MAC address 1102a, as shown in Figure 11a, or based on the sequence in which the mobile device enters LPG1102b, as shown in Figure 11b. be able to. Hash functions and sequencing have been described earlier with respect to fixed IP address allocation and will not be further described.

This IP address enables communication within LPG, that is, communication within LPG. However, for inter-LPG communication, mobile devices must be assigned separate IP addresses. This will be a public IP address. This public IP address can be assigned by an external wireless device acting as a DHCP server or by another mobile device acting as DHCP. This address assignment follows the DHCP protocol between the mobile device (which acts as the representative of LPG) and the external device (which acts as the DHCP server).

In one embodiment of the invention, one mobile device within an LPG is assigned a public IP address for inter-LPG communication using the IPv4 protocol. As shown in Figure 12a, one node 1202 is assigned the public IP address IPA1204. The node 1202 may be the first mobile device in the LPG, the mobile device selected as the reader, or the mobile device selected based on another predetermined selection criterion. Alternatively, the selection can be made randomly. The remaining nodes 1201 cannot be assigned the public IP address IPA1204.

In another embodiment, each mobile device in a given LPG is assigned a different IP address. As shown in Figure 12b, the LPG1200 has six nodes 1201. Each node 1201 will be assigned a different IP address IPA1204 ~ IPF1209.

In the third embodiment, only one global public IP address is assigned to all mobile devices in the LPG. As shown in Figure 12c, each mobile device or node 1201 in the LPG1200 is assigned the same public IP address 1204. This public IP address 1204 can be globally recognized by other nodes for communicating over the Internet. For example, the public IP address can be 239.5.5.5.

For the IPv6 protocol, there are two different ways to assign an IP address for intra-LPG communication. A wireless device using the IPv6 protocol has two automatic setting functions, that is, a link local address and a router advertisement address setting function.

Figures 13a and 13b show two different examples of IP address formats for intra-LPG communication. As shown in FIG. 13a, the first method uses a link local address 1300, eg fe80. The link local address 1300 is the upper part of the IP address. The lower part, EUI1302, is 64-bit and is calculated from the MAC address and / or VIN number. However, the link-local address method is valid only within LPG and requires a second additional address for inter-LPG communication.

The second method is to use a site-local method or a router advertising address, as shown in Figure 13b. The network includes a predetermined mobile device prefix 1301 dedicated to the mobile device network or vehicle network. This mobile device prefix 1301 is combined with the LPG ID to be the upper 64 bits, as shown in Figure 13a as "XXXX" 1303. The lower 64 bits, EUI64 1302, will be the same as in Figure 13a. Therefore, the EUI64 numbers are the same for both formats, the difference being the high-order part of the ID address.

In both formats, the LPG ID is used as part of the address. The LPG ID must be unique for each LPG. According to one embodiment of the invention, the LPG ID may be either a randomly assigned number or a number predefined by a hash function. The hash function can consist of the location of the LPG, the MAC address of the first mobile device in the LPG, if available, or the VIN number of the first mobile device in the LPG.

When assigning an address between LPGs, in one embodiment, a part of the IP address is assigned by using an external wireless device. The external radio device can be any device, such as a roadside gateway or border router, that transmits its address range and prefix to LPG. Network prefixes can be obtained from those gateway (router) advertisements. The received network prefix 1400 will be used as a higher part of the IP address, eg, a global directory for the IP address. The lower part of the IP address can use the same EUI number 64 1302 used for the intra-LPG communication IP address.

In another embodiment, a given vehicle or mobile device prefix 1301 is created and introduced into the memory section of each mobile device. This mobile device prefix 1301 is combined with LPG ID 1303 to form the upper 64 bits. The LPG ID must be unique for each LPG. According to one embodiment of the invention, the LPG ID may be either a randomly assigned number or a number predefined by a hash function. The hash function can consist of the location of the LPG, the MAC address of the first mobile device in the LPG, if available, or the VIN number of the first mobile device in the LPG. The lower part of the IP address can use the same EUI number 64 1302 used for the intra-LPG communication IP address.

In one embodiment, any mobile device can be assigned any IP address. In another embodiment, specific IP addresses can be reserved for different classes of mobile devices. For example, an emergency vehicle can be assigned a range of IP addresses. IP addresses within this range are stored for emergency vehicles such as ambulances, police cars and fire trucks. The external wireless device or gateway recognizes a special mobile device and stores a list of special mobile devices or classifications of the mobile device in memory. These special vehicles must use special queries to request an IP address.

This facilitates priority messages from emergency vehicles. In other words, all messages originating from a particular range of IP addresses have the highest priority for transmission.

The present invention has been described herein with reference to certain exemplary embodiments. Certain modifications and changes may be apparent to those skilled in the art without departing from the scope of the invention. The exemplary embodiments are intended to be exemplary and are not intended to limit the scope of the invention as defined by the appended claims.

<figref num="1">It is a figure which shows an example of two local peer groups by this invention.</figref><figref num="2">It is a figure which shows a plurality of fixed LPGs by this invention.</figref><figref num="3">It is a figure which shows a plurality of dynamic LPGs by this invention.</figref><figref num="4">It is a figure which shows the method of ordering LPG "on demand" by one Embodiment of this invention.</figref><figref num="5">It is a figure which shows an example of ordering a mobile device according to another embodiment of this invention.</figref><figref num="6">It is a figure which shows the method of ordering the mobile device by another embodiment of this invention.</figref><figref num="7">It is a figure which shows a plurality of ECs in one LPG.</figref><figref num="8">It is a figure which shows the wireless device attached to or built in the mobile device according to this invention.</figref><figref num="9">It is a figure which shows an example of assigning an IP address by the embodiment specified above.</figref><figref num="10">It is a figure which shows the format of the IP address by another embodiment of this invention.</figref><figref num="11">It is a diagram showing two different IP address formats used when assigning IP addresses to mobile devices in dynamic LPG.</figref><figref num="12">It is a figure which shows the embodiment for assigning an IP address for communication between LPGs by this invention.</figref><figref num="13">It is a figure which shows two different formats of the IP address for communication in LPG in the case of dynamic LPG.</figref><figref num="14">It is a figure which shows two different formats of the IP address for communication between LPG in the case of dynamic LPG.</figref>