RU2378770C2 - Method and device for encoding and planning in data packet transmission systems - Google Patents

Abstract

FIELD: physics; communications.

SUBSTANCE: invention relates to communication systems. The method and device according to this invention relate to planning and encoding in communication systems which use automatic repeat request (ARQ) and/or multi-switched planning and transmission. According to the proposed method, receiving nodes selectively store received information, as well as listened information as prior information, and the information is transmitted back relative the respective stored prior information to the sending node. The sending node creates composite data packets through combined encoding and planning several data packets. The said composite data packets are transmitted to receiving nodes. After receiving a composite data packet, the receiving nodes use their stored prior information when extracting data for themselves from the composite data packets.

EFFECT: increased service quality.

39 cl, 15 dwg, 1 tbl

Description

FIELD OF THE INVENTION

The present invention relates to a communication system with at least one sending node in communication with a plurality of receiving nodes, the medium having unreliable and possibly changing characteristics. In particular, the method and apparatus according to the present invention relates to the use of scheduling in systems using automatic repeat request (ARQ) and / or multi-hop scheduling and transmission.

State of the art

Wireless communication systems are currently subject to a change in technology, from circuit-switched technology in second-generation systems like GSM to packet-switched systems in third-generation systems and future communication systems. The change in technology is the result of growing demands for non-voice services, such as providing multimedia services and web browsing, combined with the demands for efficient use of scarce radio resources and increased flexibility. Packet data based on communication technology reveals vast potential improvements over circuit-switched technology with respect to flexibility, possible performance (data rate) and the ability to adapt to a changing radio environment. A key feature in any packet data system is the planning of data packets or protocol data units (PDUs). The scheduling mechanism, or scheduler, of the sending entity may, for example, support multiple data buffers, at least one buffer for each other entity that the sending entity is exchanging with. In practice, many (logical) buffers can act as a single (physical) buffer together with pointers or alternatively by viewing the physical buffer. The data packets supplied to the sending entity, for example from the core network, are stored in an appropriate buffer, and the scheduling function ensures that other entities are supplied with their respective data packets in ways that, for example, take into account the unidirectional channel capacity, bandwidth requirements for different applications , QoS requirements (quality of service), etc. It may be noted that in traditional planning, retransmissions via ARQ (described in more detail below) are usually only loosely and indirectly associated with scheduling functionality. For example, the scheduler may consider the remaining lifetime for the packet (if defined) as input. When the PDU is retransmitted one or more times, the time runs out and the lifetime value for the PDU decreases, thereby implicitly affecting its priority in the planning process.

In the development of packet-based services for cellular wireless systems, considerable attention has been paid to providing flexible, yet optimized planning functionality. The new transport channel, fifth version high speed forward link shared channel (HS-DSCH) according to the UMTS specification (see http://www.umtsworld.com), introduces new radio interface functionality such as fast channel-dependent scheduling, fast link adaptation and fast automatic repeat request (ARQ) protocol. The scheduler in the sending entity, here often referred to as the Node-B, organizes a sequence in which user data (data packets) buffered in the Node-B are transmitted to various other objects, for example, the User Equipment (OP, UE). User data scheduled for transmission to a separate UE is received from the buffer of the respective UEs in Node-B and inserted into transport blocks. The scheduler selects the transport block to be transmitted, the time interval (or code) to use for transmission, and the UE for which this transport block is intended. The transport block will have varying lengths depending on the amount of data, but is transmitted in a time interval of a fixed duration, usually 2 ms. Transport blocks are usually separate for each destination UE, however, they can be transmitted simultaneously if code multiplexing is used.

Ad hoc networks (special purpose networks) and networks with many switching (with multiple reception of information) represent a different approach in communication systems and have recently attracted considerable interest. In this type of network, many and preferably all mobile nodes, for example, a cell phone / mobile terminal, PDA or laptop computer, are able to act as a router (mobile host computer) for other mobile nodes. The need for a fixed infrastructure is thus eliminated, although access to a fixed network such as the Internet is a good complement to a completely ad hoc operation. Accordingly, data packets sent from the source mobile node to the destination mobile node are usually routed through a plurality of intermediate mobile nodes (with many receptions) before reaching the destination mobile node. A special ( ad hoc ) network is usually completely self-organizing in that the routing paths (a sequence of retransmissions) are not always predefined, although complex optimization routines can be used to find the best paths. Future and exploited ad hoc networks are envisioned to use a variety of switches. Multi-hop networks, on the other hand, may have some predetermined preferred hopping patterns, i.e., multi- hop networks are not necessarily an ad hoc network. However, the term “multi-hop network” is used below and should be interpreted as any network that uses multiple hop during communication, that is, includes ad hoc networks . A detailed description of networks with many switches (many hops) is given in Wireless ad hoc networking - The art of networking without a network ", by M. Frodigh et al, Ericsson Review, pp 248-263 (4) 2000.

The nodes in the network usually support a preferably recently updated routing table identifying the mobile nodes to which the existing node is capable of sending a data packet. In a multi-hop network using routing a data packet or the like, the following procedure is performed for each routed packet: when a node receives a packet, it checks its routing table for the next switching (re-receive) node that directs the data packet to the destination. If the receiving node does not have the next switching node and is not a destination, then the state of the routing table is inconsistent in a network with many switches. To update this state, the receiving node can, for example, initiate a search for a route to the destination, wait until the state is updated automatically (can be performed on a regular basis), or simply reply to the previous station that it does not have a correctly working route, and the mentioned the previous station may try a different route. The latter case, however, in reality does not completely solve the problem, but slightly facilitates it. The process continues until the data packet ultimately reaches the destination node. Alternatively, no routing lists are stored in the mobile nodes, and routing paths are established for each communication session. The scheduler of the sending entity in the multi-hop network organizes the transmission of data packets and at least considers which packets are constantly in the queue, the information contained in the routing lists when to transmit, and preferably also other transmission factors, such as unidirectional channel capacity and current radio environment.

Routing procedures and updating routing lists can be performed in a variety of different ways, and many are known in the art. Recently, new multi-switch transmission schemes have been proposed using characteristics inherent in the radio channel. Optional diversity transfer (SDF) and multi-user diversity (MDF) transmission schemes as described in "Multiuser Diversity Forwarding in Multihop Packet Radio Networks", by P. Larsson and N. Johansson, Proceedings of IEEE WCNC 2005, New Orleans, March 2005, which can be seen as providing flexible planning in such variations of the radio channel, were investigated to instantly select the optimal route and / or adapt transmission speed.

Automatic Repeat Request (ARQ), as mentioned above, has been proposed for use on the air interface in cellular wireless communication systems. ARQ can also be used in multi-switch systems. Data before transmission is usually divided into smaller packets, Protocol Data Units (PDUs). Reliable transmission is ensured by encoding packets with error detection code so that the receiver can detect erroneous or lost packets and thus request retransmission. The integrity of the data sequence is usually ensured by sequential numbering of packets and the application of certain transmission rules.

In the simplest form of ARQ, commonly referred to as a stop-and-wait ARQ, the data sender stores each data packet sent and awaits confirmation from the receiver of the correctly received data packet through an acknowledgment message (ACK). When the ACK is received, the sender discards the stored packet and sends the next packet. The process is usually complemented by timers and the use of negative acknowledgment (NACK) messages. The sending entity uses a timer that starts when a data packet is transmitted, and if no ACK (or NACK) was received before the timer expires, the data packet is retransmitted. If the receiver detects errors in the packet, it may send a NACK to the sender. After receiving the NACK, the sender retransmits the data packet without waiting for the timer to expire. If the ACK or NACK message is lost, the timer will eventually expire and the sender will retransmit the data packet.

ARQ has been introduced in the art in several different aspects. From simple stop-and-wait, more complex conventional ARQ schemes have been developed, such as Return to N and selective deviation (or selective repetition), which provides better performance. Publication WO 02/09342 discloses an ARQ scheme that adds flexibility to a traditional ARQ scheme by introducing ARQ parameters that are set and / or consistent to provide the desired compromise regarding communication resources.

In another line of ARQ development, coding redundancy is used in various ways to improve communication efficiency (usually measured as performance). These circuits are called hybrid ARQ circuits. The combination of coding and ARQ, hybrid ARQ schemes may provide some adaptation to changes in the radio environment, such as fading. In Hybrid ARQ Scheme 1, forward error correction (FEC) is combined with ARQ. In Hybrid ARQ scheme 2, PDUs are sent more or less (FEC) encoded but followed by a cyclic code check (CRC) to check for the presence of erroneous bits after decoding, and if retransmission is required, send parity bits (also known as bits redundancy) generated by the FEC encoder, systematic bits, or a combination of both. When parity bits are used together with previously received bits representing the same data packet, this is often called Hybrid ARQ scheme 2 based on increasing redundancy. This parity bit sequence may, in some Hybrid ARQ scheme 2, be directly decoded, and / or improve the decoding of a previously received incorrectly decoded PDU. When systematic bits are used together with pre-received bits representing the same data packet, this is often referred to as Hybrid ARQ scheme 2 based on a combination of tracking. Hybrid ARQ schema version 2 is used in UMTS.

WO 0249292 addresses some of the challenges of using Hybrid ARQ in UMTS systems, especially with regard to scheduling and buffering. Scheduling is simplified and buffer size is reduced by introducing a data flow control mechanism between the Radio Network Controller (RNC) and Node B.

Schemes have been proposed, for example in WO 02052771, in order to optimize the required bandwidth and resolve conflicting requirements from the UE through improved scheduling at base stations. Planning also considers channel conditions.

Prior art coding and scheduling schemes represent significant improvements in terms of overall performance and flexibility. However, the increasing demands of higher productivity, coverage, and flexibility cannot be satisfied only with the prior art.

SUMMARY OF THE INVENTION

In known communication systems, in particular wireless systems in which the environment is unreliable, information is sent that is not received by the designated receiving node, but which is received by another node in the system. Prior art methods and constructions are not able to recognize and exploit the fact that the information sent, which was received by nodes other than the assigned, can be used to improve coding and scheduling in the sending node in relation to, for example, full performance.

Obviously, an improved method and apparatus for scheduling and coding is needed, using the fact that information is received by nodes in the system other than the originally assigned receiving node, which are suitable in communication systems using automatic repeat request (ARQ) or scheduling and transmission with many switches, The environment is unreliable.

An object of the present invention is to provide a method and apparatus that overcomes the disadvantages of prior art methods. This is achieved by the method according to paragraph 1 of the claims, by the method in the sending node, as defined in paragraph 18 of the claims, by the method in the receiving node, as defined in paragraph 27 of the claims by the sending node, as defined in paragraph 32 of the claims, the receiving node, as defined in paragraph 36 of the claims, and the system, as defined in paragraph 38 of the claims.

This problem is solved by the fact that the present invention provides a method and apparatus that facilitates the use of listening (eavesdropped) and previously rejected information to improve coding and scheduling in the sending node. According to the method, the receiving nodes selectively store the received information as a priori information and feed back information (feedback) regarding their respective stored a priori information to the sending node. The sending node generates composite data packets by jointly coding and scheduling a plurality of data packets to a plurality of users, at least in part based on feedback information about a priori information of the respective receiving nodes. The sending node transmits a composite data packet to a plurality of receiving nodes. After receiving the composite data packet, the receiving nodes use their stored a priori information in the process of extracting data for themselves from the composite data packets. In addition, and in combination with a priori feedback information, the sending node can use conventional feedback informing of received data packets.

The invention is applicable to systems with multiple unicast ARQs (e.g., cellular and multi-hop systems), as well as multi-hop systems where listening information may also be received from senders other than the sender node.

Thanks to the invention, fewer data packets must be sent from the sending node to the plurality of receiving nodes in order to achieve the correct reception of the transmitted data packets.

According to one aspect of the invention, there is provided a method that comprises the steps of:

- at least one receiving node receives and stores at least one data packet assigned to another receiving node, and the stored data packets form at least a part of the a priori information of the receiving node that received the data packet;

- at least one of the receiving nodes feeds back information about its a priori information to the first sending node and / or to the second sending node;

- at least one of the sending node (s) that received the feedback information generates and transmits a composite data packet, wherein the composite data packet contains information from at least two separate data packets, each containing information intended for at least two receiving nodes, wherein the aforementioned formation uses a priori information of at least one receiving node;

- at least one receiving node decodes, at least partially, a composite data packet using its prior information.

Combined (joint) coding is preferably non-linear, for example, performed using exclusive OR operations or modulo operations.

Preferably, the combined coding and scheduling includes an optimization process considering various combinations of packets and various combinations of receivers and knowledge of their stored a priori information.

According to a second aspect of the invention, there is provided a method in a sending node that comprises the steps of:

storing as a priori information at least one data packet assigned to at least one other receiving node;

transmitting feedback information on a priori information to at least one other node in the communication system; and

after receiving the composite data packet, decoding, at least in part, the said composite data packets by using the stored a priori information.

According to a third aspect of the invention, there is provided a method in a receiving unit, which comprises the steps of:

storing as a priori information at least one data packet intended for at least one other receiving node;

transmitting feedback information regarding a priori information to at least one other node in the communication system; and

after receiving the composite data packet, decoding, at least in part, the said composite data packets by using the stored a priori information.

According to a fourth aspect of the invention, there is provided a sending node that comprises a feedback receiver adapted to receive and identify a priori information in feedback information from receiving nodes, a priori information storage module for storing a priori information from a plurality of receiving nodes, a combined coding and scheduling module for forming a composite a data packet from a plurality of individual data packets. The a priori information storage module is connected to said feedback receiver. The combined coding and scheduling module is configured to use a priori information from the a priori information storage module and determine which of the plurality of individual data packets to extract from the buffer module for use in a composite data packet.

According to a fifth aspect of the invention, there is provided a receiving node that comprises a buffer of a priori information for storing selected data packets as a priori information, and an identification and decoding module PDU (protocol data units) configured to extract a priori information from said a priori information buffer for decoding received constituents data packets.

One of the advantages of the invention is that fewer transmissions are needed to ensure that information that reaches its destination allows for increased throughput and reduced latency.

Another advantage is that the energy / power used in the communication system can be reduced for the same throughput and latency.

Another advantage is that low decoding (and coding) complexity can be used.

Embodiments of the invention are defined in the dependent claims. Other objectives, advantages and new features of the invention will become apparent from the following detailed description of the invention when considered in conjunction with the accompanying drawings and the claims.

Brief Description of the Drawings

The invention is described in detail below with reference to the drawings, in which:

FIG. 1 is a schematic illustration of transmission sequences in a cellular communication system according to the prior art;

FIG. 2 is a schematic illustration of transmission sequences in a multi-hop system according to the prior art;

FIG. 3 is a flow chart of a method according to the present invention;

FIG. 4 is a schematic illustration of transmission sequences in a communication system according to the present invention;

FIG. 5 is a schematic illustration of transmission sequences in a communication system according to one embodiment of the present invention;

FIG. 6 is a schematic illustration of transmission sequences in a multi-hop system according to one embodiment of the present invention;

FIG. 7 shows a flowchart according to receiving operations according to the method of the present invention;

FIG. 8 is a flowchart of transmission operations according to the method of the present invention;

FIG. 9 is a schematic illustration of a transmitter and a receiver according to the present invention;

FIG. 10 is a schematic illustration of coding principles according to one embodiment of the present invention;

FIG. 11 is a schematic illustration of a feedback message according to one embodiment of the present invention;

FIG. 12 is a schematic illustration of transmission sequences in a cellular communication system according to one embodiment of the present invention.

DETAILED DESCRIPTION OF THE INVENTION

In the communication system of the present invention, a sending entity is involved in communication with a plurality of receiving entities. A sending entity, for example, a base station (BS), in a transmission operation is called a sending node (SN), and a receiving entity, for example, implemented as a mobile station (MS), in a receiving operation is called a receiving node (RN). It should be noted that the mobile station can also act as a sending node, and the base station as a receiving node. The present invention can be advantageously used both in conventional cellular communication systems with a base station in communication with a plurality of mobile stations and in multiple switching systems, wherein at least one mobile station communicates with at least two other mobile stations to enable exchange. As described above, various scheduling schemes can be used in such systems to increase efficiency, and different types of ARQ schemes can be used to increase transmission reliability.

First, a conventional ARQ scheme according to the prior art is considered. The traditional ARQ scheme between one sender and one receiver below is referred to as ARQ unidirectional transmission. It should be noted that, for example, in a downlink cellular communication system, multiple unidirectional ARQ sessions are performed simultaneously to different users, where each user can have multiple streams with their own unidirectional ARQ instance. In FIG. 1 illustrates a sending node, in this case, the base station 105 is in communication with two receiving nodes v _a and v _A, respectively, implemented as a mobile station 110 and a mobile station 120. Therefore, two unidirectional ARQ protocols are executed in parallel, the first between the base station 105 and the mobile station 110 and the second between the base station 105 and the mobile station 120. In the example illustrated in FIG. 1, at time T _{1, the} sending node, the base station 105, sends information in the form of a data packet (a) to the mobile station 110, the data packet (a) not being received correctly by the mobile station 110. The data packet (a) may also be received (listened) by other user (s), for example, the receiving node v _A (mobile station 120). However, according to the prior art unidirectional transmission ARQ scheme, such listening data packets are discarded by the receiving node v _A. Alternatively, if the receiving node v _A knows that it is not the designated receiving node, data packets are not considered at all. At time T _2, a data packet (A) is sent from the sending node 105 to the mobile station 120, but also this transmission is unsuccessful. Through ARQ procedures, the sending node 105 is provided with acknowledgment information and at times T ₃ and T _{4, the} sending node 105 retransmits packet (a) and packet (A), respectively. The two receiving nodes v _a and v _A correctly receive their respective data packet (a) and (A). It should be noted that transmissions at times T ₁ and T ₂ can occur at the same time if a transmission technology is used that allows simultaneous transmissions, for example, orthogonal frequency division multiple access (OFDMA), i.e., packet (A), and packet (a) are sent simultaneously, but on non-overlapping sets of OFDM subcarriers. Retransmission may also occur simultaneously.

Networks with many switching represent another deployment scenario where nodes route traffic to each other, in addition to generating and receiving their own traffic. However, multi-hop networks retain the attributes of a cellular communication system, that is, this usually includes a sender exchanging with a plurality of stations over an unreliable environment. One type of multi-hop network principle uses transmission scheduling for each node. This planning process can take into account many different aspects, such as packet delay, QoS (quality of service) requirement and averaging, as well as instantaneous link characteristics to determine which packet to send, to whom and when. Multiple user routing is disclosed in US200402333918. Like a cellular communications network, a node in a multi-hop network can use unidirectional ARQ, that is, one or more instances for each neighbor. An example of a multi-hop network with packets scheduled for different users is illustrated in FIG. 2, where the nodes v _x 205 and v _y 215 represent the sending nodes and send data packets to the nodes v _A 225 and v _a 210, respectively, acting as destination nodes. First, the data packet (A) is sent to the (intermediate) receiving node v _s 220. The node v _s 220 sends the data packet (A) to the node v _A 225. At a later point in time, the node v _y 215 sends the data packet (a) to the intermediate node v _s 220, which forwards the data packet (a) to the node v _a 210. Similar to the case with cellular communications and according to ARQ procedures, the reception is confirmed and, if necessary, the lost data packets are retransmitted to the designated receiver.

According to the method and apparatus of the present invention, a priori information, for example, listening information, such as discarded data packets in the above examples, is used to increase efficiency in a communication system. The receiving nodes selectively store the received information as a priori information and feed back information about their respective stored a priori information to the sending node. The sending node generates composite data packets by jointly coding and scheduling a plurality of data packets to a plurality of users, at least in part, based on feedback regarding a priori information of the respective receiving nodes. In addition, and in combination with a priori feedback information, the sending node may use conventional feedback informing about received data packets. A composite data packet is transmitted to the receiving nodes. After receiving the composite data packet, the receiving nodes use their stored a priori information in the process of extracting data for themselves from the composite data packets. Thus, fewer data packets must be sent from the sending node to the plurality of receiving nodes in order to achieve the correct reception of the transmitted data packets. The invention is applicable to multiple unidirectional ARQs (e.g., cellular and multi-hop systems), as well as multi-hop systems, where listening to information may also come from other senders other than the sender node.

The principle of the method according to the present invention in an enlarged form is illustrated by the sequence of operations in FIG. 3 and the schematic transmission diagram of FIG. 4. As illustrated in the drawings, a plurality of radio nodes 405, 410, 415, which are parts in a wireless communication system, are in the process of exchanging information in the form of data packets. The term "radio nodes" should be interpreted broadly; any device capable of wireless communication and compatible with the standards used in a wireless communication network can be considered as a radio node. Typically, a radio node is capable of both sending and receiving data packets, which is referred to as sending and receiving operations, respectively, or a sending / receiving node, meaning a radio node in a send / receive operation. Radio nodes include, but are not limited to, radio base stations, mobile stations, laptop computers and PDAs (personal digital assistants) equipped with wireless communications, and vehicles and vehicles equipped with wireless communications. In this example, the radio node 405 is primarily in the send operation (sending node 405) and the nodes 410, 415, and 420 are primarily in the receive operation (receiving nodes 410, 415, 420). Solid lines indicate assigned transmissions, and dashed lines indicate listening transmissions. Crossed packets indicate failed reception. The method according to the invention is preferably preceded by the initial exchange of a separate data packet, while the preceding step 300 comprises the steps of:

300: Data packets, illustrated as packets (X) and (Y), are sent from one or more radio nodes in a send operation, here, a sending node 405, to a plurality of receiving nodes 410, 415, 420. Typically, each individual data packet has a designated receiving knot. The transmission of data packets may occur simultaneously or sequentially depending on the transmission technology.

The method according to the invention comprises the steps of:

310: The receiving nodes 410, 415, 420 store their respective data packets, i.e. their intended information, if it was correctly received. In addition, the receiving node can receive and store listening information, that is, data packets intended for other receiving nodes, but which the receiving node in question received and was able to decode, and / or data packets that were sent to the receiving node in question in a multi-switch scenario for further transfer to your final destination. Listened information constitutes a priori information of each receiving node 410, 415, 420. In the illustrated example, data packets (X) and (Y) are a priori information of node 410, (Y) is a priori information of node 415, and (X) and (Z) are a priori information of the node 420, (Z) - adopted earlier.

320: The receiving nodes 410, 415, 420 transmit back to the sending node 405, or sending nodes, information of the corresponding a priori information. Typically, the receiving node also feeds back information regarding the transmission result using ARQ procedures, for example.

330: The sending node 405 generates, if possible and advantageously, a composite data packet 450 by using backward-supplied knowledge of the corresponding a priori information from the receiving nodes 410, 415, 420. The composite data packet contains data intended for at least two different receiving nodes. Preferably, knowledge of the a priori information is used by the sending node 405 to schedule which individual data packets should be contained in the composite data packet and jointly encode a plurality of individual data packets that should be contained in the composite data packet. At least a portion of the composite data packet should consist of co-encoded multiple individual data packets. The encoding characteristic of a composite packet is that the number of bits in the composite packet is less than the sum of the number of bits of the packet parts that are coded. This process is referred to below as combined coding and scheduling, and is described in detail and illustrated below. A sending node can form many different composite packets intended for different pairs or groups of receiving nodes. In this example, the sending node 405 forms a composite data packet containing data from (X), (Y) and (Z).

340: The sending node 405 transmits a composite data packet to the designated receiving nodes, in the example of FIG. 4 - to the receiving nodes 410, 415, 420.

350: After receiving the composite data packet, the receiving nodes 410, 415, 420 decode, if possible, the composite data packet and extract the corresponding own data, which was previously unknown to the corresponding receiving node. In the process of decoding and extracting, a priori known information and, possibly, proprietary data packets previously decoded by the receiver are used. There may be a case where the receiving node may not have the complete information necessary to completely decode and extract its own data from the composite data packet. If this is the case, then the receiving node can partially decode the composite data packet, and save the result, the remaining composite data packet for further processing, when other information becomes available, for example, other data packets assigned to this receiving node should be sent from the sending node 405, or listening data packets. Alternatively, the composite data packet is stored without trying to decode until the receiving node receives all the required information. Information regarding the information required to decode the main part of the composite data packet may be contained in the header. In this example, node 420 can retrieve (Y) and node 410 retrieves (Z). Node 415 may retrieve the residual composite data packet.

The a priori information fed back from the receiving nodes 410, 415, 420 to the sending node 405 can preferably be combined with feedback information about which data packets were received and which do not have, provided that such information can be determined, own data packets, that is, data packets for which a particular receiving node was a designated receiver. Therefore, the additional backward transmission of a priori information can be considered as an extension of the traditional unidirectional transmission ARQ feedback in that the node reports the decoding result also for other transmissions not intended for this node. The combination of a priori feedback and traditional ARQ unidirectional feedback transmission may be referred to as extended or full status of a received packet. Here, “full” means all status information, while “advanced” indicates more feedback information than that provided by traditional unidirectional ARQ.

The listened data packets received at step 310 are typically either ordinary data packets or composite data packets. Alternatively or in combination, the composite data packets may be used as a priori information by the receiving node, even if the receiving node does not currently have enough information to decode the composite packet.

The method according to the invention is described below with reference to embodiments suitable for cellular systems and multi-hop networks, respectively.

In FIG. 5 illustrates a conventional cellular communication system in which a sending node, a base station 505, communicates with a plurality of receiving nodes, mobile stations 510 and 520. In the prior art, it was possible to have multiple instances of unidirectional transmission ARQ. Here, according to one embodiment of the invention, each has an integrated multi-user unidirectional ARQ scheme, operating between a sender and multiple receivers, ensuring retransmission support for each user stream, but also including the multi-user aspect in the retransmission process. After the process described in relation to FIG. 3, the steps of an embodiment are illustrated by the following non-limiting example:

300a: At times T ₁ and T _{2, the} sending node, the base station 505, transmits a data packet (a) assigned to the receiving node v _a , the mobile station 510, and a data packet (A) intended for the receiving node v _A , the mobile station 520 , respectively. Both tricks are unsuccessful. However, the mobile station 520 (receiving node v _A ) receives (listens) the data packet (a), and the mobile station 510 (receiving node v _a ) listens to the data packet (A).

310a: the mobile station 520 (receiving node v _A ) stores the data packet (a) and the mobile station 510 (receiving node v _a ) stores the data packet (A). The stored corresponding data packets constitute a priori information of the receiving nodes.

320a: Then, at time T _{3, the} mobile stations 510, 520 transmit back a priori information, that is, inform the base station 505 of which data packets were received (or, conversely, which were not received, or a combination thereof), or extended, or the full status of the received package. Feedback information is in the form of a feedback message.

330a: The base station 505 generates and plans to transmit a composite data packet based on a feedback message containing a priori information from the corresponding mobile station 510, 520, which packets to re-transmit and take into account the encoding principles used. Here, one coding example uses an exclusive OR operation of packet (a) with packet (A).

340a: At time T _{4, the} base station 505 transmits a composite data packet, a packet (a) processed by an exclusive OR operation with packet (A), to the mobile stations 510, 520.

350a: After the (composite) reception of the composite data packet is received, each of these two mobile stations 510, 520 can decode the composite data packet and retrieve its corresponding missing information, i.e., data packet (a) for node v a _and data packet (A) for node v _A , although only one packet was sent using its corresponding a priori information. The decoding comprises, for the mobile station 510, an exclusive-OR operation of a previously received data packet (A) with a composite data packet to extract the data packet (a). Similarly, the mobile station 520 uses the previously received data packet (a) to retrieve the data packet (A).

For simplicity, an embodiment is illustrated with only two receiving nodes. However, as understood by those skilled in the art, taking into account the above description, the method can be extended to a plurality of receiving nodes or groups of receiving nodes.

Transmission at times T ₁ and T ₂ can occur at the same time if, for example, OFDMA is used, that is, packet (A) and packet (a) are sent simultaneously, but over non-overlapping sets of OFDM subcarriers. Simultaneous transmission of data packets, for example, by OFDMA, can also be used in a multi-hop scenario. Other methods for simultaneously transmitting at times T ₁ and T _{2 are} also not excluded in accordance with the invention.

Another embodiment of the invention relates to a scenario with many switches (receptions). In FIG. 6 illustrates a multi-hop network in which a plurality of nodes 605, 610, 615, 620, and 625 are used for multiple hops to transmit a data packet (a) and data packet (A) to their respective destinations. Nodes for a plurality of hops typically act alternately as sending nodes and receiving nodes. The task of a node for a plurality of hops acting as a sending node is to direct data in its buffer to a desired receiver, which in turn transmits data to a destination. In the description relating to a multi-hop scenario, the terms “assigned node” and “assigned receiver” refer to nodes / receivers that are the intended receiver of a particular transmission (re-reception). Therefore, the assigned node / receiver is not necessarily the final destination of the data packet. Nodes for multiple switching are, for example, mobile stations. After the process described with reference to FIG. 3, the operation is illustrated by the following non-limiting example:

300b: At time T _{1, the} sending node, node v _x 605 for multiple switching, transmits a data packet (A) intended for node v _A 625 through node v _s 620, in this case acting as the designated receiving node. The data packet (A) is also listened to by the receiving node v _a 610. At time T _{2, the} second sending node, node v _y 615 for a plurality of switches, transmits the data packet (a). The designated receiver, node v _s 620 for multiple hops, receives a data packet (a), and the data packet (a) is also tapped by the receiving node v _A 625.

310b: The receiving node v _a 610 stores the data packet (A), the receiving node v _A 625 stores the data packet (a) as its corresponding a priori information and the node v _s 620 stores both the data packet (A) and the packet for a plurality of switching (a) data.

320b: Then, at time T _{3, the} receiving nodes inform other nodes in the network with a lot of switching their a priori information and it is also possible which assigned packets were received (or, conversely, were not received) in the feedback messages. In this example, the node v _s 620 for a plurality of switches receives information that the data packet (a) was received by the receiving node v _A 625 and the data packet (A) was received by the receiving node v _a 610.

330b: Based on the received feedback messages, the node v _s 620 for multiple switching, now acting as the sending node, schedules which packets to transmit and jointly encodes them into a composite data packet. Here, a simple coding example comprises performing an exclusive OR operation for packet (a) with packet (A).

340b: At time T _{4, the} node v _s 620, for a plurality of switches, acting as a sending node, transmits a composite data packet (that is, the result of an exclusive OR operation of a packet (a) with a packet (A)) to the receiving nodes v _a 610 and v _A 625.

350b: After receiving the composite data packet, the receiving nodes v _a 610 and v _A 625 decode their respective missing information, i.e., the original data packet (a) and data packet (A), respectively, using their stored corresponding a priori information. The decoding comprises the execution by the receiving nodes v _and 610 of an exclusive-OR operation of a previously received data packet (A) with a jointly encoded multiple data packet in order to extract the data packet (a). By analogy, the receiving nodes v _A 625 use the previously received data packet (a) to retrieve the data packet (A).

It should be noted that the receiving nodes v _a 610 and v _A 625 may not necessarily be the final destinations of the data packets (a) and (A) and can now forward the corresponding data packets (a) and (A) to their respective final destinations if the nodes v _and v _a 610 and 625 are not the final destination.

In a network with many switches, it can also be accepted that one of the nodes, for example, v _A 625, sent a packet to the node v _s 620, therefore, there is no need to send feedback from the node v _A 625 to v _s 620. However, in the process of formation of a composite packet, the node v _s 620 relies on feedback from v _a 610. In general, at least one receiving node must ensure the transfer of a priori information back, and this information is used in the planning process.

While the situation described above, where the listening information from other transmitters (other than ultimately sending the composite data packet) was used as a priori information, other combinations and methods for obtaining a priori known information are also possible. For example, similar to the method in FIG. 5, you can also use earlier transmissions from the same sender. In addition, other receiving nodes can also decode the composite data packet and retrieve data packets that are not intended for them, which can then be used as a priori information in the future process of decoding the composite data packets assigned to them.

It should be noted that there may be a case where it is only possible to partially decode a jointly encoded data packet, for example, when three or more data packets are jointly encoded and only one a priori data packet is known and stored by the receiving node. An example is the encoding of packets A, B and C, in which only packet C resides in the receiving node. Then, the combination of encoded A with B will be extracted during the decoding process and then stored as well as communicated to the sending node (or including other sending nodes as well). It should be noted that the status of the received packet then indicates that A and B are still co-encoded. The sending node may include in the planning process the knowledge that a priori information residing in one or more receiving nodes is at least partially co-encoded. When decoding at the receiver, the information of the jointly encoded packet can be used, at least partially, as prior knowledge when receiving and decoding a composite packet.

As indicated above, in the method according to the present invention, both composite data packets and conventional data packets must be processed by the receiving node and the sending node. The flowchart of FIG. 7 illustrates an embodiment of the invention representing the execution of a method at a receiving node. The term “regular data packet” means a non-integral data packet, that is, data packets of the type that is also used in the prior art. The flowchart of FIG. 8 illustrates an embodiment in a sending node.

The operation of the receiver when receiving a data packet, as can be seen from FIG. 7 contains the steps of:

705: The receiving node receives the data packet and performs conventional decoding, that is, typically FEC decoding.

710: The receiving node determines whether the received data packet is a composite data packet. This information is preferably and usually contained in the header of the data packet or, alternatively, in a control message transmitted out of the frequency band or in the frequency band. If the data packet is not composite, that is, a regular data packet, the algorithm proceeds to step 730.

715: The receiving node determines whether it is possible to reconcile the composite data packet with any stored a priori information. If not, the composite data packet is stored in the a priori information buffer, step 745.

720: The receiving node decodes the composite data packet with the corresponding a priori information.

725: If the residual composite packet remains after decoding, that is, if the stored a priori information is sufficient only to partially decode the composite data packet, the residual data packet is stored in the a priori information buffer, step 745. If the composite packet is decoded completely, the algorithm proceeds to step 730.

730: The receiving node determines whether the data packet, regular or retrieved from the composite data packet, is for another node. If the data packet is intended for another node, then this data packet is stored in the a priori information buffer, step 745.

735: If the receiving node is the designated receiver for the data packet, this data packet is stored in its own ARQ buffer, if necessary, or sent to a higher level; and

740: The receiving node transmits information regarding its own received data back to the sending node and possibly other nodes. The receiving node returns to step 705 to process the other received data packets.

745: The receiving node stores a data packet, a composite data packet, or a residual composite data packet in a priori information buffer.

750: The receiving node transmits back information regarding the received a priori information to the sending node and, possibly, to other nodes. The receiving node returns to step 705 to process the other received data packets.

An operation in a sending node may be assumed to consist of three different parts or cycles, as illustrated in the flowcharts of FIG. 8a-c. The first part (a) receives and processes feedback messages, the second part (b) form composite data packets, and the third part (c) sends reset messages to interrupt feedback from the receiving nodes. All parts can work simultaneously.

The first part (a) of the operation of the sending nodes contains the steps:

805: The sending node monitors whether any feedback messages have been received.

810: The sending node determines whether the feedback information is feedback information regarding the a priori information from the receiving node or whether it is feedback information regarding the received own data. If - relative to its own data, the algorithm proceeds to the usual ARQ operation, step 815, if relative to a priori information, the algorithm proceeds to step 820.

815: The sending node performs the usual ARQ operation and returns to control step 805.

820: The sending node stores information from the feedback information in the a priori information buffer and returns to control step 805.

The second part (b) of the operation of the sending nodes contains the steps:

825: The sending node determines whether data packets have been sent. This may be based, for example, but not limited to, whether feedback information has just arrived, whether a new packet has just arrived for transmission, or whether the transmission case is determined by some other function.

830: The sending node schedules data packets to be sent from its buffers. At the planning stage, the sending node determines whether the data packets were combined into a composite data packet, taking into account the a priori information from the a priori information buffer, or whether a regular packet should be sent. The planning process also determines for which node or nodes the package or packages are assigned (s).

835: The sending node checks whether the composite packet was scheduled at block 830. If not, then the transmission of the normal data packet is performed at block 845.

840: If a composite packet was planned, then a composite data packet is generated by jointly encoding individual data packets from data buffers.

845: A data packet, or a regular data packet, or a composite data packet, is sent.

The third part (c) of the operation of the sending nodes concerns how long the prior information should be stored. When the receiving node has received the assigned data packet, the other receivers should no longer continue to store the relevant information, as it will never be retransmitted again. In addition, other receivers should not continue to inform that they have received this information. Therefore, a mechanism is required to suppress (discard) the outdated information of other users, and also to ensure that feedback messages are not sent for packets already received by the designated node. This operation contains the steps of:

850: The sending node determines whether a reset (suppression) message has been sent, and which data packet (s) this reset message should relate to.

830: The sending node sends a reset message.

An appropriate cycle for processing reset messages is also performed at the receiver. The loop in the receiver, as illustrated in FIG. 7 contains the steps of:

760: The receiving node controls whether a reset message has been received.

765: The receiving node identifies and discards (suppresses) outdated a priori information based on the information contained in the received reset message.

Details and examples of suitable reset mechanisms are described below.

An apparatus according to the present invention suitable for carrying out the above described embodiments is schematically illustrated in FIG. 9. Modules and blocks according to the present invention described above should be regarded as functional parts of the sending and / or receiving node in the communication system and, optionally, as physical objects. Modules and blocks, at least in part, are preferably implemented as means of program code adapted to carry out the method according to the invention. The term “comprising” primarily refers to a logical structure, and the term “connected” should be interpreted as relationships between functional parts and optionally physical connections. However, depending on the design chosen, some modules may be implemented as physically distinctive objects in a receiver or transmitter.

The transmitter 900 of the sending node comprises transmission means 903 that provides the necessary functionality for performing the actual transmission. Suitable transmission media, for example, radio transmission media, are known to those skilled in the art. The transmitter 900 also comprises a combined coding and scheduling module 905, in which a combined coding and scheduling algorithm resides. The combined coding and scheduling module 905 is in communication with the a priori information module 910; module 915 additional information; buffer module 920; and module 925 encoder and sort PDU. The transmitter also comprises means for receiving and processing feedback messages 930 of both the ACK and / or NACK, for packets that were received by the designated receiver and feedback information containing a priori information from the receiving nodes. Integrated coding and scheduling module 905 comprises means 933 for conventional ARQ operations. The a priori information module 910 stores and updates the list of statuses of the received packets based on feedback information from the receiving nodes, i.e., the statuses of the extended or fully received packet. Buffer module 920 provides send buffers, typically one for each stream. Assuming that the transmitter intends to send a packet, it considers which packet resides in the send buffers of buffer module 920 and the a priori information of the various receiving nodes, which is stored in the a priori information module 910. The possible additional knowledge provided by the supplementary information module 915 is also used for planning. Additional information includes, but is not limited to, channel quality information (CQI) for each link used in the flexible scheduling described below, QoS requirements for expanding the invention with QoS scheduling aspects, and the status of individual packets, for example, their lifetime value . In the case of multiple switches for distributed execution, the supplementary information module 915 also comprises means for determining the routing cost, as well as means for determining the routing cost of neighboring nodes, and thus allowing the scheduler to consider the routing cost of neighboring nodes as well as its own routing cost, so that ensure that data packets are routed to the intended destination, as well as allowing optimal routing planning decisions. If mobility is reasonably low, a centralized determination of route and cost may be an alternative to a distributed case. For this latter case, information related to the route is then distributed from the central node to other nodes in the network. Based on these parameters, and possibly additional parameters, one or more packets are selected from the send buffers to the encoder module 925 and the PDU sort. If a plurality of packets are assembled, they are jointly encoded to form a composite data packet by the PDU encoder and sorting module 925, and then CRC and FEC (preferably) are added, and the packets are transmitted via the radio transmission means 905.

The receiver unit 940 of the receiving unit comprises receiving means 945, which provides the necessary functionality to perform the actual reception. Suitable means of reception, such as radios, are known to those skilled in the art. The receiver also includes means for issuing and processing feedback messages, both related to ARQ, and related to a priori information 950; a FEC decoding and CRC module 955 in conjunction with a reception means 945; PDU identification and decoding module 960 and a priori information buffer 965. The PDU identification and decoding module 960 is in communication with the decoding and CRC FEC module 955 and a priori information buffer 965, as well as with top-level functionalities / modules (not shown) to provide received data. The a priori information buffer 965 contains buffers for correctly decoded packets (here, decoded packets mean that the CRC is correct, however, there may still be some residual combined encoding, i.e., the remote influence of packet A, but packets B and C are still encoded together), for example Listened data packets destined for other receivers. The PDU identification and decoding unit 960 comprises ARQ means 952. ARQ Tool 952 must be interpreted broadly, that is, be able to process positive, negative confirmations, or a combination thereof.

A receiver 940 decodes the packet and identifies which packets were encoded together. Based on a priori knowledge of previously correctly received packets (intended for other users) and a received coded packet, the receiving node extracts new information. The decoded information can then be directed to higher levels (if it is intended for this node) or stored in the buffer 965 a priori information. In the case where it is only possible to partially decode the composite data packet, for example, when three or more data packets are jointly encoded and only one a priori data packet is available to the receiver 940, then the residual jointly encoded information, the residual composite data packet, is stored. An example is the transmission of a composite data packet that contains jointly encoded data packets A, B and C and in which only packet C is always located in the receiver. Then the residual composite data packet, a combination of A encoded with B, will be stored in the buffer 965 of the a priori information of the receiver 940.

After the receiver 940 has successfully received the encoded data packet, it updates the list of statuses of the received packets permanently located in the a priori information module 910 of the transmitter 900, immediately or with a slight delay. Delay can be useful in order not to take up resources and not waste energy unnecessarily due to the overhead of each feedback packet. The update is achieved by means of ARQ means 952 of the receiver 940 and ARQ means 933 of the transmitter 900.

In addition, it should be noted that the receiver 940 can also act as a transmitter if data is then transmitted. The same is true for transmitter 900, that is, it can also act as a receiver for other data.

Using a priori information, for example, listening information, and allowing both the sending node (using feedback information) and the receiving node to use this information, it is possible to reduce the number of transmissions needed to transfer a certain amount of data from one node to another, and in the scenario with many switches - from source to destination. This improves overall performance as well as individual user productivity. In addition, end-to-end latency features should be improved. Alternatively, depending on the conditions, fewer transmissions may be used to increase power and energy efficiency in the sender and the communication system with the plurality of receivers.

In particular, the efficiency of multiple parallel unidirectional ARQs can be improved with respect to performance and delay, as well as power consumption.

In addition, the efficiency of transmission scheduling algorithms in a multi-hop network can be improved with respect to performance and latency, as well as energy consumption. Regarding multi-shift transmission, one of the additional objectives of the invention is to improve the so-called flexible multi-shift transmission scheme, that is, circuits that seek to adapt the transmission so that peak possibilities such as those offered by the channel and unpredictable fluctuating interference , are used when choosing who to communicate with.

Encoding methods

A coding method suitable for the method according to the present invention is preferably based on bitwise exclusive-OR coding because of its simplicity. Other codes may also be used, for example, an erase code similar to the Reed-Solomon code. Regarding Reed-Solomon type coding, the same operation as the exclusive-OR operation between two words is possible, for example, if you select an abbreviated RS (Reed-Solomon) code with K = 2 and with the keywords N = 3. The non-systematic keyword N-K = 1 is resubmitted instead of two word-for-word exclusive-OR words. Other erase codes or code-oriented erasure coding methods may also be used.

Many different methods can be envisioned for joint (combined) encoding using the exclusive X and subsequent identification of which packets are jointly encoded together. An example of possible code frame formats is given with reference to the illustrations in FIG. 10. In this example, two data packets (A) 1005 and (B) 1010 are jointly encoded to form a composite data packet 1015. Useful data can be processed directly or exclusively by means of identifying which individual packets should be offered. where encoded together. In one coding method, see FIG. 10, identifiers (for example, headers or subsets of relevant information from the headers of individual packets) of jointly encoded packets (only two packets are shown here, but can be easily extended to a larger number of packets) are transmitted in the header 1020 of the composite packet. The identifier may, for example, contain the identifier of the source node, the identifier of the destination node and the sequence number of the packet for each encoded packet. In addition to identifiers, the header of the composite package also reports the format of the composite package, that is where the packages are placed in the composite package. For example, if there are two packets and one of the packets contains fewer bits than the other packet, as in FIG. 10, the number of bits contained in the packet with the fewer bits, as well as the position of the first bit of the shorter packet are also indicated. When the number of bits is different, padding 1025 is used, as in FIG. 10 for packet B 1010. The header format field 1020 of the composite packet may also indicate that two packets B and C are concatenated with one another (not shown) and then encoded, for example, with a third packet or more packets. After the correct FEC decoding and detection of the correct CRC 1030, the illustrated composite packet header allows a simple identification of which packets were encoded together. The receiver uses this information to select an a priori known packet from the memory of the decoded data packets and to extract another packet (s). It should be noted that the header of the composite packet may also contain other information, such as in a network with many switching, which, in addition to packet identifiers, may be involved in which relay station is sending and which relay stations should receive.

A different coding version than the one illustrated above (not shown) is to transmit the composite packet header in a normal broadcast message, i.e. out of band transmission type. Another encoding method (not shown) may use a blind identification approach, that is, the hypothesis of testing encoded messages with respect to the a priori information database and the use of CRC verification to verify the validity of testing the hypothesis.

The present invention is not limited to the use of exclusive OR operations when encoding composite data packets. Coding operations are preferably adapted to the transmission technology used, processing capacity, delay sensitivity, etc. Another example of an encoding operation suitable for use in the method according to the invention is based on a modulo operator. Coding per symbol of a set of signals is discussed below, and the procedure can be repeated for a plurality of consecutive symbols of a set of signals. The modulo capture operation in this example should be performed for both the real and imaginary parts independently when processing complex numbers and use the definition of the module operation and the mathematical remark that:

((A + B) mod L - B) mod L = (A) mod L

which indicates that the real estimated signal B can be superimposed on the real estimated signal A and allow unperturbed reconstruction of signal A (as long as the signal does not exceed the quantization level L), while the amplitude (and therefore power) of the composite signal limited (non-linearly encoded).

{-3,-1,1,3} +i*{-3,-1,1,3}. Теперь, поскольку приемник знает последовательность D₂(n) данных, он также знает соответствующий символ S₂ (для каждого S₁). Тогда для вещественной части (и, равным образом, для мнимой части) совместно и кодированный сигнал в передатчике равенIn practice, this can be used as follows. The sender has the characters S ₁ and S ₂ , which usually take different meanings. For example, in 16 QAM (quadrature amplitude modulation) S _i

{-3, -1,1,3} + i * {- 3, -1,1,3}. Now, since the receiver knows the data sequence D ₂ (n), it also knows the corresponding symbol S ₂ (for each S ₁ ). Then for the real part (and, likewise, for the imaginary part) together and the encoded signal in the transmitter is

+S

) mod L (S

+ S

) mod L

which is then received and corrected, that is, compensated for path losses (ensuring that the same scale is used for the received signal and the signal that is subtracted), and complex phase (ensuring that the corresponding in-phase and quadrature phase axes combined with the signal that is subtracted) to give out the received signal

= (S

+ S

) mod L + N

R

= (S

+ S

) mod L + N

является членом шума (и помехи). Полезный сигнал тогда восстанавливается с помощьюwhere N

is a member of noise (and interference). The useful signal is then restored using

= ((R

) mod L - S

) mod L = (S

+ N

) mod L

= ((R

) mod L - S

) mod L = (S

+ N

) mod L

Nonlinear coding can also be performed by quantization by means of a structure of a higher dimension than only one-dimensional quantization, as described above. In this case, quantization works with vectors instead of scalars.

Feedback messages

Feedback from the receiving node to the sending node can be considered as part of the ACK procedure and preferably uses a predefined feedback message containing both ACK and a priori information. Feedback messages can be composed in various ways, for example, depending on the transmission protocols used, ARQ procedures, etc. Feedback messages are preferably issued and processed using ARQ means 933 and 952 of transmitter 900 and receiver 940, respectively. Non-limiting examples of possible feedback messages are provided below:

A) In ARQ unidirectional transmission, only one sending node uses received status messages coming from multiple receivers with which it exchanges:

a. Given this, we note that if a unique sequence number is assigned to the encoded packet, this is sufficient if the receiver responds with it. This means that the transmitter, based on the knowledge of what the receiver has previously received and the sequence number of the encoded packet, can determine what kind of knowledge about the data the receiver has and in what encoded form it is stored. This is illustrated by the fact that if a composite data packet (coded data packets A, B and C) was received and that only packet C was constantly in the receiver. Then the combination of A encoded with B will be the stored form in the receiver after removing the influence of the data packet C.

b. An alternative to the unique sequence number approach is to use a timestamp when the data packet has been received since the transmitter can store what was transmitted at different points in time.

c. Another alternative method is that individual (decoded) serial numbers of data packets are specified in the receiver feedback message.

B) In networks with many switches, many nodes can listen to status messages (even if they were not senders of the corresponding packets), and not just the transmitting station. Therefore, there is a need to have a frame format that allows all nodes to identify which data packets are encoded together. The explicit frame format, as shown in FIG. 10 represents a possible solution. It should be noted that in multi-hop networks, multiple instances of unidirectional ARQ can also belong to a single transmitter.

The possible frame format for the received data packet status message according to case A) and case B) above, i.e. corresponding to the frame format in FIG. 10 is schematically illustrated in FIG. 11. The feedback message 1100 contains a message header 1105 illustrating the structure of the feedback message. Flow identifier 1110 indicates to which flow the received packet status belongs. In a multi-switch scenario, for example, source and destination identifiers can be embedded, as well as a subflow indication unique to the source-destination pair. The received packet field 1115 indicates which packets were received, that is, data packets that are part of the a priori information of the receiving node, or normal acknowledgments for the packet that were intended for the node sending the feedback message. A list of explicit sequence numbers, or a bitmap with starting sequence numbers, can be used for this purpose. The receiver also sends back the status of the received packets intended for itself to the transmitter, as in the traditional unidirectional transmission ARQ.

In order to avoid when the receiver sends feedback information regarding data packets to other receivers that has already been received by the designated receiver, as well as unnecessarily storing these packets, a reset method is needed. This method is described below.

Forward and reverse reset message

When the receiver has received its intended information (i.e., data packets), other receivers should no longer continue to store the relevant information, since it will never be retransmitted again. In addition, other receivers should not continue to transmit a message that they have received this information. Therefore, a mechanism is required to suppress (discard) the outdated information of other users, and to ensure that extended or full received packet status messages are no longer sent for packets already received by the designated node.

This is the task of the so-called direct reset message, which indicates (via broadcasting) which packets were received by their intended receiving nodes. After receiving such a message, the receiver 940 removes the decoded data packets from its a priori information buffer 965 and no longer reports the corresponding data packet as received.

The minimum requirement may be that the sender must ensure that the lower edge of the ARQ transmission window is sent as a direct reset message and that packets below the lower transmission window are discarded at the receivers.

More preferably, the transmitter informs all receivers of at least the lower boundary of the ARQ window, that is, it informs the receivers up to the sequence number that was received by the intended receiver of its own stream. This can be considered as multicasting the lower edges of the ARQ window to many users and represent an alternative embodiment of the present invention.

An alternative to the aforementioned, or preferably addition, is the use of a reverse reset message. In this alternative embodiment, the first node listens for the received data packet status message from the neighboring receiving node (s) regarding their correctly received packets destined for said node. The first node uses this information to purge the corresponding data packets in its own buffer containing data packets destined for other nodes.

Scheduler Algorithms

The scheduling according to the present invention is performed by the combined coding and scheduling unit 905 in the transmitter 900 at step 340. This section of the description illustrates how to identify suitable data packets to perform joint coding, and which coding to use.

To illustrate this, an ARQ example of unidirectional transmission to many users is used, but the generalization for a multi-switch scenario is obvious. As described above, the sender maintains a list of received packet statuses from multiple nodes, a list of received packet statuses resident in the a priori information module 910. An example status list is schematically illustrated in the table. The status list, illustrated here as an example, shows which packets were received by whom. For example, node 1 did not receive its own destined packets, but received packets with sequence numbers SeqNr n + 1 and n + 3, intended for node 2, as well as packets with sequence numbers SeqNr n + 4, intended for node 3.

An example of the list of statuses of received packets in the transmitter Sender Status List Host Nodes one 2 3 Node queue one 2 3 one 2 3 one 2 3 Pic
ice. package number n Accepted Accepted n + 1 Accepted n + 2 Accepted n + 3 Accepted Accepted n + 4 Accepted Accepted Accepted Accepted

Based on this list and possibly other additional information that is provided from the additional information module 915, the sender identifies which packets to jointly encode and transmit. For example, the sender can identify and again send the encoding of a packet with sequence number n to node 2 and the packet with sequence number n to node 3 as bitwise coding D ₂ (n) ⊕ D ₃ (n) for complete packets, where D indicates the data sequence of some lengths, the subscript is the receiving node, and the number in parentheses is the serial number. If both node 2 and node 3 receive this message, both can decode their information. It should be noted that there is no need to use the same serial numbers, an example of this is the coding D ₂ (n + 1) ⊕ D ₁ (n + 2). It should also be noted that the encoding is not limited to only two packets, for example, the utility of encoding three packets D ₁ (n + 4) ⊕ D ₂ (n + 3) ⊕ D ₃ (n + 4) can be understood from the table.

A preferred scheduling and coding algorithm is described below. To facilitate understanding of the algorithm, consider the Cartesian product of the number of elements m:

Let CP _m (A ₁ , ..., A _k ) be the Cartesian product of the number of elements m over the sets A ₁ , A ₂ , ...., A _k , where k≥m.

For example: let A = {a ₁ }, B = {b ₁ , b ₂ } and C = {c ₁ , c ₂ }, then CP ₃ (A, B, C) = {(a ₁ , b ₁ , s ₁ ), (a ₁ , b ₁ , s ₂ ), (a ₁ , b ₂ , s ₁ ), (a ₁ , b ₂ , s ₂ )} and

CP ₂ (A, B, C) = (a ₁ , b ₁ ), (a ₁ , b ₂ ), (a ₁ , s ₁ ), (a ₁ , s ₂ ), (b ₁ , s ₁ ), (b ₁ , s ₂ ), (b ₂ , s ₁ ), (b ₂ , c ₂ )}

Henceforth, the sets A _i should be interpreted as a set of packets (a _j ) intended for the node v _i already transmitted but not received by the node v _i (here j is the index for the sequence number).

A preferred scheduling and coding algorithm to be performed as sub-steps of step 330 of the method of the invention described with reference to FIG. 3 contains the steps of:

1. Identify all input signals where the proper receiver has received its intended packet. Discard these input signals, since the purpose of transmitting the assigned packet to the desired node has already been fulfilled (that is, clear the already received packet from the buffer for the receiver). The remaining input signals can now be used in combined coding.

2. Form a Cartesian product and start searching for a Cartesian product in descending order. Whenever a viable set of input signals is found (that is, all packets in the set have been received by all nodes in the set, except for the intended receiver), the search is stopped, and the set of packets to be subjected to the exclusive-OR operation is found. Alternatively, the set of nodes is ordered in the desired priority order. (The most important sets within the Cartesian product first, then in decreasing order.)

3. Encode data for each set, for example, in the form of a bitwise exclusive-OR operation of all nodes.

4. Transmit co-encoded packet (with a suitable combination of header, tail bits, CRC and FEC added to the end).

5. Sometimes: Accept the status lists of the received packet from the receiving nodes and possibly other nodes.

6. Sometimes: Flush the receiver buffers of correctly decoded packets of another receiver, that is, send a direct reset message.

7. Return to stage 2.

Alternatively, reduced complexity is achieved by replacing the second step with the following:

2 '. 1) select one package (randomly or in some way prioritized package based on, for example, packet delay, QoS (quality of service) and / or fairness requirements) and include it in set P (initially empty),

2) identify which other nodes have accepted (and confirmed) this packet and include them in set N,

3) two different options are now possible:

i) form a Cartesian product of the number of elements k and below (assuming that the number of nodes that received the packet is equal to k) and follow the algorithm described above, or

ii) iterate through 2 ', i.e., select the second (and third, etc.) packet (from the set of nodes in N) and update the sets P and N (in order to realize that in the set N all the preselected packets must be received by the considered node, and some packet for the considered node must be received by all pre-selected nodes, that is, intended receivers of the selected packets). This is done until the set N becomes empty.

Other scheduling and coding algorithms are possible. For example, consider packets with different sequence numbers directed to a single node. As in step one above, delete the packet that has already been received by the designated node. Sort subsequent packets based on the number of other nodes that have received this packet. Repeat this process for the packet header for each other node. Now, some packets have been received by many nodes, while the other has been received only in few or no other nodes. The strategy now is to look for compatible sets of nodes among those packets that were accepted by many nodes, and if no suitable compatible sets are found, move on to packets received by fewer and fewer nodes. This pre-sorting procedure reduces the complexity of the search, as described above in the main algorithm.

Flexible planning

In addition to the combined coding and scheduling described above, the scheduling decision may also include channel quality indication (CQI) information to further improve performance.

The use of CQIs is known in prior art planning, where it is often called flexible scheduling. The CQI is a metric fed back from the receiving node to the sending node indicating the estimated (and sometimes predictable) link quality for the upcoming transmission instance (s). Based on the CQI and possibly other criteria, the sending node in traditional flexible planning selects a data packet and sends it at the (estimated / predicted) peak opportunity. This peak opportunity usually occurs when the instantaneous quality of the channel exceeds its average quality, for example, due to the fact that the channel experiences fading and / or that there is no interference or the channel with the dominant interference experiences fading. Since the channel changes over time due to mobility and fluctuating traffic, CQI should be updated regularly. Flexible planning is known to increase productivity through an effect that is commonly known as multi-user diversity.

According to this aspect of the invention, flexible scheduling and combined scheduling and coding are jointly performed by combining both functions. In networks with many hops, you might also want to include an increase in the cost of routing each packet to the destination, that is, regardless of whether flexible scheduling is used or not.

It is important that there are some benefits of using the invention for flexible planning, namely that many peak opportunities can be selected and used. This differs from the prior art, which is limited due to the lack of the ability to send multiple messages contained in one packet, send only one packet and, therefore, at most use only one peak capability at a time. FIG. 12 schematically illustrates an embodiment of the invention utilizing a variety of peak capabilities, in more detail. A flexible scheduling and transmission switching case is illustrated in which a plurality of nodes 1205, 1210, 1215, 1220 and 1225 with a plurality of switching are occupied in the direction of the data packet (a) and data packet (A) to their respective destinations. Node 1205 currently acts as a sending node v _s . The receiving node v _a 1210 stores a priori information containing the data packet (A), the receiving node v _A 1215 is the data packet (a), the receiving node v _x 1220 is the data packet (a) and the receiving node v _y 1225 is the data packet (b ) Flexible multi-hop scheduling is used by the sending node 1205 in that these two channels are used, offering peak capabilities, the channels to the receiving node v _a 1210 and the channel to the receiving node v _A 1215. Therefore, a composite data packet based on packets (A) and (a) data is selected by means of a coding and scheduling algorithm, instead of a composite data packet that is currently to be transmitted on less favorable channels. The method is not limited to the illustrated use of two communication lines or two separate data packets.

To illustrate the operation of the invention in a multi-hop network using the idea of flexible scheduling, two schedulers based on multi-hop schemes denoted by SDF and MDF, as described in the above documents, can be considered. Any node that listens for received packet status messages, that is, an extension of the acknowledgment scheme available in the SDF and MDF to support the invention, uses this information in the planning process and sends the packet either in the traditional way or jointly encodes multiple packets according to the invention. In particular, the CQI values for communication lines to various users can be taken into account in the planning process.

While the above combined flexible scheduling and coding scheme has been illustrated primarily for a multi-hop network, it is clear that it can also be used in a multi-user unidirectional ARQ scenario.

The method and apparatus according to the invention are applicable to any network where packets can be sent more than once. This is integral to networks employing ARQ (due to retransmissions), as well as to networks with multiple hops (due to the fact that packets are usually routed through multiple hops, and also because of the potential implementation of ARQ unidirectional transmission). The invention has been described for a wireless scenario, but can equally well be used in other communication scenarios.

The method according to the present invention is preferably implemented by means of software products or products of program modules containing software code means for performing the steps of the method. Software products are preferably executed on a variety of objects within a network. Software products are distributed and downloadable from a computer-used environment, such as a USB memory, CD, or broadcast over the air, or downloaded from the Internet, for example.

While the invention has been described with reference to what is considered to be the most practicable and preferred embodiments, it should be understood that the invention should not be limited to the disclosed embodiments, but rather is intended to cover various modifications and equivalent structures, included in the scope and form of the attached claims.

Claims (39)

1. A method of encoding and scheduling data packets in a communication system, wherein the communication system comprises at least a sending node (405) and at least two receiving nodes (410-420), and wherein the sending nodes buffer, schedule, encode and transmit packets data containing information intended for a specific receiving node or to specific receiving nodes, the method is characterized in that it comprises the steps of:
the receiving node (410) selectively stores the received information as a priori information, wherein at least a portion of the a priori information is listening information intended for another receiving node,
the receiving node (410) sends back information about its a priori information to the sending node (405), and
the sending node (405) uses this information regarding a priori information to generate and transmit the composite data packet to at least the receiving node (410), wherein said composite data packet contains information assigned to at least two receiving nodes. 2. The method according to claim 1, characterized in that it comprises the steps of:
(310) at least one of the receiving nodes (410-420) receives and stores at least one data packet destined for another receiving node, the stored data packets forming at least a portion of the a priori information of the receiving node that received the data packet;
(320) at least one of the receiving nodes (410-420) sends back information about its a priori information to the first sending node and / or to at least the second sending node,
(330, 340) at least one of the sending node (s) (405) that received the feedback information generates and transmits a composite data packet (450), wherein the composite data packet (450) contains information from at least at least two separate data packets, each containing information assigned to at least two receiving nodes, while the aforementioned formation uses a priori information of at least one receiving node (410-420); and
(350) at least one receiving node decodes, at least in part, a composite data packet (450) using its prior information. 3. The method according to claim 2, in which at the stage (330, 340) of formation and transmission, the sending node generates a composite data packet by combined coding and scheduling of at least two data packets. 4. The method of claim 3, wherein the exclusive-OR operations are used in combined coding. 5. The method according to claim 3, in which the operations of taking modulo are used in combined coding. 6. The method according to claim 3, in which, when coding and scheduling are combined, optimization is performed considering various combinations of packets and various combinations of receivers, and knowledge of their stored a priori information. 7. The method according to claim 6, in which additional optimization information is used in addition to a priori information. 8. The method according to claim 7, in which the additional information contains one or a combination of parameters from: quality of service requirements, indication of channel quality, routing cost values and characteristics of the data packet. 9. The method according to any one of claims 2 to 8, wherein in the receiving and decoding step (350), the receiving node partially decodes the composite data packet using its a priori information, said partially decoded composite data packet generating a residual composite data packet and stored by the receiving one node as a priori information. 10. The method according to any one of claims 2 to 8, wherein in the receiving and decoding step (350), the receiving node stores a composite data packet. 11. The method of claim 10, wherein in the step of (350) receiving and decoding the receiving packet, the node stores the composite data packet as a priori information. 12. The method according to any one of claims 2 to 8, wherein in the receiving and storing step (310), at least one composite data packet intended for another receiving node is stored as part of the a priori information of the receiving node. 13. The method according to any one of claims 1 to 8, in which the number of bits used for the composite data packet is less than the sum of the number of bits of two separate data packets. 14. The method according to any one of claims 1 to 8, in which, at the receiving stage (310), the receiving nodes (410-420) receive data packets transmitted from the first sending node (405), at the step (320) of the reverse transmission, the receiving nodes ( 410-420) feed information back to at least the first sending node (405), and in the step of generating and transmitting the composite data packet (340), the first sending node (405) generates and transmits the composite data packet. 15. The method according to any one of claims 1 to 8, in which at step (320) the reverse transmission of at least one receiving node (410-420) feeds information back to at least the second sending node (405), and at the stage of formation and transmitting the composite data packet (340), the second sending node (405) generates and transmits the composite data packet. 16. The method according to any one of claims 1 to 8, in which the communication system is a cellular communication system, and the first sending node is a base station (505). 17. The method according to any one of claims 1 to 8, in which the communication system is a system with many switching. 18. The method in the sending node in the communication system of combined coding and scheduling of multiple data packets in which the sending node (405) is configured to communicate with at least two receiving nodes (410-420), and the sending node transmits information in the form of separate packets data intended for individual receiving nodes, the method is characterized in that it comprises the steps of:
(805) receive feedback information from at least one of the receiving nodes (410-420), said feedback information containing information on a priori information from at least one of the receiving nodes (410), wherein the information on a priori information information about information being tapped by the receiving node (410);
(825-840) generating a composite data packet from a plurality of data packets intended for at least two receiving nodes (410-420), said formation being at least partially based on information regarding said a priori information. 19. The method of claim 18, further comprising the steps of:
control (805) the sending node whether any feedback messages have been received;
determining (810) by the sending node whether the feedback information and feedback information regarding the a priori information from the receiving node or whether it is feedback information regarding the received own data, and if regarding the own data, the sending node continues to perform normal ARQ operations, and if with respect to a priori information, then the sending node (820) stores the information from the feedback information in the a priori information buffer, and returns to the control step 805. 20. The method according to claim 19, in which at the forming steps (330, 340) the sending node generates a composite data packet by combined coding and scheduling of at least two data packets. 21. The method of claim 20, wherein the exclusive-OR operations are used in combined coding. 22. The method of claim 20, wherein the modulo take operations are used in combined coding. 23. The method according to any one of claims 20 to 22, wherein optimization is performed in the combined coding and planning, considering various combinations of packets and various combinations of receivers and knowledge of their stored a priori information. 24. The method according to item 23, in which the optimization uses additional information in addition to a priori information. 25. The method according to paragraph 24, in which the additional information contains one or a combination of parameters from: quality of service requirements, indication of channel quality, routing cost values and data packet characteristics. 26. The method according to any one of claims 19-22, wherein the number of bits used for the composite data packet is less than the sum of the number of bits from two separate data packets. 27. A decoding method at a receiving node in a communication system in which the receiving node is configured to communicate with at least one sending node (405), the method being characterized in that it comprises the steps of:
storing (310) at least one data packet for at least one other receiving node as a priori information;
feed back (750) information regarding a priori information to at least one other node; and after receiving (340, 720) the composite data packet decode at least partially mentioned composite data packets using the stored a priori information. 28. The decoding method in the receiving node according to item 27, further comprising the steps of:
determining (705) the receiving node whether the received data packet is a composite data packet or a regular data packet;
determine (710) by the receiving node whether it is possible to match the composite data packet with any previously stored a priori information, and if not possible, the composite data packet is stored as a priori information. 29. The decoding method in the receiving node according to item 27 or 28, further comprising the step of storing (745) the residual composite data packet if the previously stored a priori information is sufficient only for partial decoding of the composite data packet, wherein said residual composite data packet contains a partially decoded composite data packet and saved as a priori information. 30. The method according to any one of paragraphs.27-28, in which at the receiving and saving step (310) the receiving nodes receive data packets transmitted from the first sending node (405), at the reverse transmitting step (705), the receiving nodes transmit back to at least the first sending node (405). 31. The method according to any one of paragraphs.27-28, in which, at the step of postback (705), the receiving node transmits back to at least a second sending node (405), different from the sending node from which the data packet was received at the previous stage reception. 32. A sending node adapted for use in a communication system, wherein the sending node (405) is configured to communicate with at least two receiving nodes (410, 420) by transmitting information in the form of a plurality of separate data packets intended for individual receiving nodes, characterized in that:
the feedback receiver (930) is adapted to receive and identify information on a priori information in the feedback information from the receiving nodes (410, 420), and the information on a priori information contains information about the messages being listened to;
a priori information storage module (910) for storing a priori information from a plurality of receiving nodes, while the a priori information storage module (910) is connected to said feedback receiver (930);
a combined coding and scheduling module (905) for generating a composite data packet from a plurality of separate data packets, while the a priori information storage module (910) is configured to use a priori information from the a priori information storage module (910) and determine which multiple individual packets retrieve the data from the buffer module (920) for use in the composite data packet. 33. The sending node according to claim 32, further comprising an additional information module (915) connected to the combined coding and scheduling module (905), said additional information module (915) configured to store additional channel information and provide the combined module (905) coding and scheduling additional channel information. 34. The sending node according to claim 33, wherein the additional information module (915) is configured to store one or a combination of parameters from: service quality requirements, channel quality indications, routing cost values, and data packet characteristics. 35. The sending node according to claim 34, wherein the combined coding and scheduling module (905) is configured to perform scheduling and coding based on information provided from both the a priori information storage module (910) and the additional information module (915). 36. The receiving node, adapted for exchange with at least one sending node (405) in the communication system, characterized in that
the a priori information buffer (965) is configured to store at least one data packet intended for at least one other receiving node as a priori information;
a module (960) for identifying and decoding protocol data units (BDPs, PDUs), configured to extract a priori information from said a priori information buffer (965) for decoding received composite data packets. 37. The receiving node according to clause 36, further comprising a sender (950) of feedback information in connection with a PDU identification and decoding module (960) and configured to generate feedback messages containing information regarding the stored a priori information. 38. A communication system comprising at least one sending node adapted to communicate with at least two receiving nodes by transmitting information in the form of a plurality of separate data packets intended to separate receiving nodes, characterized in that the communication system comprises at least one sending node (405) according to claim 32. 39. The communication system according to claim 38, further comprising at least one receiving node according to claim 36.

Images