НАДЕЖНАЯ ГРУППОВАЯ ПЕРЕДАЧА С ЛИНЕЙНО НЕЗАВИСИМЫМ КОДИРОВАНИЕМ ПАКЕТОВ ДАННЫХ
SECURE GROUP TRANSFER WITH LINEAR INDEPENDENT CODING OF DATA PACKAGES

Область техники, к которой относится изобретение
Настоящее изобретение, в общем, относится к системам групповой передачи, а более конкретно к новой стратегии для планирования и кодирования пакетов для групповой передачи.
Уровень техники
Имеется постоянно растущая потребность в повышении производительности систем связи, в общем, и беспроводных сетей, в частности. Групповая передача является подходом для повышения пропускной способности за счет эффективной передачи одной и той же информации нескольким пользователям/приемным устройствам. Когда канал является ненадежным, может быть невозможным доставлять данные во все приемные устройства надежным способом. Поэтому групповая передача по ненадежным каналам в типичном варианте требует использования методов прямой коррекции ошибок (FEC) или методов обратной коррекции ошибок, таких как автоматические запросы на повторную передачу (ARQ).
Так называемое фонтанное кодирование представляется интересным подходом для надежной групповой передачи [1-2]. Фонтанное кодирование - это идеальная схема кодирования данных без учета скорости, форма FEC, которая формирует новую информацию о четности до тех пор, пока все пользователи не декодировали отправленный файл данных. Приближением идеальных фонтанных кодов являются так называемые торнадо-коды и LT-коды. Другие фонтанные коды включают в себя так называемые торнадо-коды и оперативные коды. Основная философия в LT-кодах (и, в общем, в большинстве фонтанных кодов), в которых формируется новая информация о четности, основана на случайном выборе степени кодирования, т.е. числа пакетов, которые должны быть кодированы совместно, согласно заранее заданному степенному распределению и последующей операции побитового XOR (сложения по модулю 2) пакетов. Хотя внутренне не является частью фонтанного кодирования, подтверждение приема в типичном варианте отправляется, когда приемное устройство приняло достаточное число пакетов четности, которые дают возможность декодирования, и не раньше этого. Следовательно, только одно подтверждение приема требуется для FC-файла для каждого пользователя. Данные приближения FC обеспечивают эффективную групповую передачу в каналах со стиранием, где примерно на величину ε должно быть принято больше избыточности, чем данных.
ARQ - это эффективная стратегия контроля ошибок для передачи данных, в которой приемное устройство обнаруживает ошибки при передаче в сообщениях и автоматически запрашивает повторную передачу от передающего устройства. Обычно сообщения обратной связи от приемных устройств к передающему устройству используются для того, чтобы предоставлять возможность передающему устройству определять, какие пакеты приняты корректно посредством заданных приемных устройств, а какие - нет. Пакеты, которые не приняты корректно, должны быть повторно переданы.
ARQ, как предлагается, должен использоваться в качестве стандарта для связи по радиоинтерфейсу в системах сотовой беспроводной связи и также может использоваться в многопролетных системах. Типично, информация делится на меньшие пакеты, называемые протокольными блоками данных (PDU), до передачи. Надежная передача обеспечивается за счет кодирования пакетов кодом обнаружения ошибок, так что приемное устройство может обнаруживать ошибочные или потерянные пакеты и тем самым запрашивать повторную передачу. Целостность последовательности данных обычно обеспечивается посредством последовательной нумерации пакетов и применения определенных правил передачи.
Может быть полезным сначала сделать обзор основных принципов ARQ на основании одноадресной передачи до пояснения подробностей относительно групповой передачи ARQ, имея в виду, что основные принципы одноадресной передачи ARQ в основном переносятся на групповую передачу ARQ.
В самой простой форме ARQ, обычно называемой ARQ с остановкой и ожиданием, передающее устройство данных сохраняет каждый отправленный пакет данных и ждет подтверждения приема от приемного устройства корректно принятого пакета данных посредством сообщения подтверждения приема (ACK). Когда ACK принято, передающее устройство отбрасывает сохраненный пакет и передает следующий пакет. Процесс в типичном варианте дополняется таймерами и применением сообщений негативного подтверждения (NACK). Передающий объект использует таймер, который запускается при передаче пакета данных, и если ACK (или NACK) не принято до того, как таймер истекает, пакет данных передается повторно. Если приемное устройство обнаруживает ошибки в пакете, оно может передать NACK передающему устройству. После приема NACK передающее устройство повторно передает пакет данных, не дожидаясь истечения таймера. Если сообщение ACK или NACK потеряно, таймер в конечном счете истекает, и передающее устройство повторно передает пакет данных.
Из простой передачи с остановкой и ожиданием созданы более продуманные схемы традиционного ARQ, например, метод возврата на N и метод избирательного отказа (или избирательного повторения), которые обеспечивают более высокую пропускную способность.
В другом направлении развития ARQ избыточность в кодировании используется различными способами для того, чтобы увеличивать производительность связи (в общем, измеряемую как пропускная способность). Эти схемы упоминаются как схемы гибридного ARQ. Комбинация кодирования и ARQ, схемы гибридного ARQ, позволяют предоставлять определенную адаптацию к изменениям в среде радиосвязи, к примеру, затуханию. В гибридном ARQ 1, FEC комбинируется с ARQ. В гибридном ARQ 2, PDU отправляется в большей или меньшей степени кодированным посредством FEC, но с прилагаемым кодом контроля циклическим избыточным кодом (CRC) для проверки наличия ошибок в битах после декодирования, и если запрашивается повторная передача, то посылаются биты четности (также известные как биты избыточности), сформированные посредством FEC-кодера, систематические биты или комбинация и того, и другого.
Если эффективность не является основной целью, то несколько параллельных процессов одноадресной передачи ARQ могут использоваться для того, чтобы обеспечивать надежную "групповую передачу". Это может быть стандартным подходом, когда размер группы групповой передачи, т.е. число заданных приемных устройств, является небольшим. Тем не менее, для больших групп этот способ связи неэффективен. Поэтому в типичном варианте считается более эффективным объединять параллельные процессы одноадресной передачи в один так называемый процесс групповой передачи ARQ, в котором одна информация передается нескольким пользователям [3].
Ссылка [4] относится к оптимизации производительности для надежных множественных потоков одноадресной передачи.
Ссылки [5-7] описывают схемы, в которых одни данные передаются в групповом режиме нескольким пользователям, и эффективная повторная передача предоставляется за счет комбинирования нескольких пакетов, негативно подтвержденных (передачей NACK) несколькими приемными устройствами, в один блок.
Проблема при традиционной групповой передаче ARQ, в общем, состоит в том, что производительность является чрезвычайно низкой, когда число пользователей является большим. Фактически, следует отметить, а также легко понять, что пропускная способность стремится к нулю, когда число пользователей K стремится к бесконечности.
+ε
Хотя фонтанное кодирование смягчает проблемы производительности в традиционной групповой передаче ARQ, ее производительность составляет примерно T=p/(1+ε), где T - это пропускная способность, ε зависит от отправляемого объема данных, а p - это вероятность приема. В [2] приблизительно установлено, что 1больше 1,06 с вероятностью 1/10, и не больше 1,10 за 10000 испытаний так называемой реализации торнадо Z-кода. Кроме того, установлено, что торнадо-коды не имеют достаточно четких пределов по неэффективности декодирования для коммерческих приложений и что для текущих коммерческих реализаций цифровых фонтанных LT-кодов неэффективность декодирования составляет больше 1,05 с вероятностью меньше чем 10 практически для любого размера исходного файла.
Фонтанное кодирование имеет несколько недостатков. FC базируется на статистическом обеспечении декодируемости за счет обеспечения информации об избыточности и не базируется на детерминированной декодируемости. Во-первых, в типичном варианте требуются большие объемы информации для небольшого значения ε, и производительность в типичном варианте является низкой, когда передается только небольшое количество пакетов данных. Время на декодирование доставляемых данных довольно значительно, поскольку вся избыточность должна быть получена до того, как декодируемость может быть гарантирована. LT-коды, форма фонтанных кодов, как известно, имеют неудовлетворительный нижний предел по ошибкам, что, по меньшей мере, частично разрешается посредством других FC, таких как торнадо-коды.
Хотя схемы, предложенные в ссылках [5-7], представляют собой шаг в правильном направлении для групповой передачи ARQ с детерминированной декодируемостью, эти схемы по-прежнему не обеспечивают оптимальную производительность. Причина этого заключается в том, что традиционная операция групповой передачи ARQ является более статической, чем необходимо, и не распознает и не использует все степени свободы.
Таким образом, есть общая потребность в еще более эффективной по пропускной способности стратегии для надежной групповой передачи.
Раскрытие изобретения
Настоящее изобретение преодолевает эти и другие недостатки средств предшествующего уровня техники.
Общая цель настоящего изобретения состоит в том, чтобы предоставить высокоэффективную по пропускной способности стратегию для надежной групповой передачи.
Цель изобретения состоит в том, чтобы предоставить способ и средство для планирования и кодирования пакетов данных для передачи в сеансе групповой передачи от передающего устройства, по меньшей мере, в два приемных устройства в системе групповой передачи ARQ.
Цель также состоит в том, чтобы предоставить передающее устройство, выполненное с возможностью использования в системе групповой передачи ARQ.
Конкретная цель состоит в том, чтобы предоставить стратегию групповой передачи, которая обеспечивает повышенную пропускную способность, уменьшенную задержку и/или пониженное энергопотребление.
Особенно желательно предоставить стратегию групповой передачи, которая обеспечивает детерминированную декодируемость кодированных пакетов.
Эти и другие цели достигаются изобретением в соответствии с прилагаемой формулой изобретения.
Изобретение, в общем, относится к планированию и кодированию пакетов данных для передачи в сеансе групповой передачи от передающего устройства в группу групповой передачи, по меньшей мере, из двух приемных устройств в системе групповой передачи ARQ.
Основная идея изобретения состоит в том, чтобы выполнять процедуру в каждом из множества событий планирования, включающую в себя формирование, по меньшей мере, одного составного пакета данных как взвешенной линейной комбинации обычных пакетов данных на основании соответствующего вектора весовых коэффициентов, содержащего набор весовых коэффициентов кодирования, посредством использования информации обратной связи от приемных устройств, указывающей принимаемые пакеты данных, и передачу сформированного составного пакета(ов) данных в приемные устройства рассматриваемой группы групповой передачи. В этой процедуре, весовые коэффициенты кодирования вектора весовых коэффициентов адаптированы для каждого составного пакета или пакетов данных на основании информации обратной связи так, что составной пакет представляет собой линейную комбинацию, которая является линейно независимой для каждого приемного устройства, по меньшей мере, из набора приемных устройств, от любого пакета данных, ранее принятого посредством приемного устройства во время рассматриваемого сеанса групповой передачи.
Посредством выполнения этой процедуры в связи с каждым из множества событий планирования, количество передач, требуемых для передачи данного объема передаваемой в режиме групповой передачи информации, будет сокращено.
Возможность передавать новые линейно независимые пакеты данных (составные пакеты данных и, дополнительно, также обычные пакеты), по меньшей мере, в большей части событий передачи во время сеанса групповой передачи значительно повышает пропускную способность для надежной групповой передачи, особенно когда число пользователей является большим.
В идеальной ситуации, при систематической передаче определенного числа обычных и/или составных пакетов данных, которые являются линейно независимыми от любого пакета данных (обычного или составного), ранее принятого посредством каждого из приемных устройств, состоящих в наборе приемных устройств, во время сеанса групповой передачи, достаточно того, чтобы отправлять просто N таких пакетов данных, чтобы извлекать все N обычных пакетов данных, таким образом получая максимальную пропускную способность.
В любом случае, по сравнению с традиционной групповой передачей ARQ, изобретение требует, чтобы меньше пакетов данных отправлялось от передающего устройства в приемные устройства, чтобы обеспечить корректный прием передаваемых пакетов данных.
Таким образом, изобретение предоставляет повышенную пропускную способность для (полностью) надежной групповой передачи, а также предоставляет детерминированно декодируемую схему повторной передачи.
Например, в фонтанном кодировании число субпакетов, которое должно быть принято для декодирования полного файла, является случайной величиной, т.е. не является детерминированно ограниченным.
Изобретение предоставляет систему, реализующую вышеупомянутую схему, а также соответствующее передающее устройство, выполненное с возможностью использования в системе групповой передачи ARQ.
Настоящее изобретение, в общем, применимо к групповой передаче ARQ в системах связи, имеющих ненадежные линии связи, таких как системы беспроводной связи. Например, изобретение преимущественно может быть использовано в типичной сотовой системе с базовой станцией, поддерживающей обмен данными с множеством мобильных терминалов.
Изобретение может предлагать следующие преимущества:
- Надежная групповая передача.
- Повышенная (или даже максимальная) пропускная способность.
- Уменьшенное (или даже минимальное) время задержки.
- Эффективное использование энергии/мощности.
- Детерминированные пределы по числу пакетов, которые должны быть приняты для декодируемости.
Другие преимущества, предлагаемые в соответствии с изобретением, должны приниматься во внимание при прочтении нижеприведенного описания вариантов осуществления изобретения.
Краткое описание чертежей
Изобретение вместе со своими дополнительными задачами и преимуществами лучше всего будет понятно при обращении к нижеследующему описанию, рассматриваемому вместе с прилагаемыми чертежами, из которых:
Фиг.1 иллюстрирует пропускную способность полностью надежной групповой передачи ARQ для K=1, 2, 4, 8, 16, 32, 64 и 128 как функцию от вероятности корректного приема.
Фиг.2 - принципиальная блок-схема, иллюстрирующая простой пример общего представления системы групповой передачи ARQ.
Фиг.3 - блок-схема способа, иллюстрирующая примерную полную процедуру ARQ.
Фиг.4 - блок-схема способа планирования и кодирования обычных пакетов данных в составной пакет данных согласно предпочтительному примерному варианту осуществления изобретения.
Фиг.5 - иллюстрирует возможный вариант осуществления кодирования двух обычных пакетов данных в составной пакет данных.
Фиг.6 - принципиальная блок-схема, иллюстрирующая систему для групповой передачи пакетов данных от передающего устройства ко множеству пользователей согласно предпочтительному примерному варианту осуществления изобретения.
Фиг.7 - принципиальная блок-схема планирования и кодирования пакета данных согласно примерному варианту осуществления изобретения.
Осуществление изобретения
На чертежах одинаковые ссылочные позиции используются для соответствующих или аналогичных элементов.
Далее, термин "обычный пакет данных" обозначает стандартный (несоставной) пакет данных (т.е. только простой обыкновенный пакет данных), тогда как составной пакет данных основан, по меньшей мере, на двух обычных пакетах данных. "Передаваемый в режиме групповой передачи пакет данных" может быть обычным пакетом данных или составным пакетом данных, и в его самом универсальном значении этот пакет данных может упоминаться как "общий пакет данных", "передаваемый в режиме групповой передачи пакет данных" или "общий передаваемый в режиме групповой передачи пакет данных".
K-1.
K
Проблема при традиционной групповой передаче ARQ, в общем, состоит в том, что производительность является чрезвычайно низкой, когда число K приемных устройств/пользователей является большим. Фиг.1 иллюстрирует пропускную способность полностью надежной групповой передачи ARQ для K=1, 2, 4, 8, 16, 32, 64 и 128 как функцию от вероятности корректного приема. Крайняя левая кривая иллюстрирует ситуацию для Как можно видеть, производительность уменьшается по мере того, как число узлов возрастает, и приближается к нулю, когда число узлов приближается к бесконечности, за исключением специального идеального случая, когда вероятность корректного приема равняется 1.
Таким образом, есть общая потребность в более эффективной по пропускной способности стратегии для надежной групповой передачи.
Будет полезно начать с краткого обзора системы групповой передачи ARQ. В системе связи ARQ, которая должна быть использована с настоящим изобретением, передающее устройство 100, в общем, вовлечено в сеанс групповой передачи с несколькими приемными устройствами 200, как схематично проиллюстрировано на фиг.2. Передающее устройство 100 обычно представляется посредством передающего узла, такого как базовая станция, в операции передачи, а приемные устройства от 200-1 до 200-K обычно представляются посредством приемных узлов, например, реализованных посредством мобильных терминалов, в операции приема. Следует отметить, что мобильный терминал, например, также может выступать в качестве передающего узла, а базовая станция - в качестве приемного узла. В групповой передаче один и тот же набор информации обычно передается на все приемные устройства, являющиеся частью группы групповой передачи. Группа групповой передачи, в общем, включает в себя, по меньшей мере, два приемных устройства, иногда называемых пользователями. Для передачи определенного числа пакетов данных в сеансе групповой передачи это, в общем, означает, что каждый отдельный пакет данных является пакетом данных, передаваемым в режиме групповой передачи, предназначенным для всех рассматриваемых приемных устройств. Следует отметить, что если связь предназначена для всех пользователей в рамках, к примеру, соты или системы, она зачастую обозначается как широковещательная передача, а не групповая передача. Следовательно, широковещательная передача - это крайний случай групповой передачи, при которой все приемные устройства в соте и т.п. принимают данные.
Настоящее изобретение преимущественно может быть использовано в типичных сотовых системах с базовой станцией, поддерживающей обмен данными с множеством мобильных терминалов. В общем, различные схемы планирования могут быть использованы в таких системах для повышения производительности, и ARQ используется для повышения надежности передач.
Изобретение описано в беспроводном сценарии, но с тем же успехом может быть использовано в других сценариях связи с ненадежными линиями связи.
Основная идея изобретения основана на выполнении процедуры в каждом из множества событий планирования, включающей в себя формирование, по меньшей мере, одного составного пакета данных как взвешенной линейной комбинации обычных пакетов данных на основании соответствующего вектора весовых коэффициентов, содержащего набор весовых коэффициентов кодирования, посредством использования информации обратной связи от приемных устройств, указывающей принимаемые пакеты данных, и передачу сформированного составного пакета(ов) данных в приемные устройства рассматриваемой группы групповой передачи. В этой процедуре весовые коэффициенты кодирования вектора весовых коэффициентов предпочтительно адаптивно выбираются, для каждого составного пакета или пакетов данных, на основании информации обратной связи так, что составной пакет представляет собой линейную комбинацию обычных пакетов данных, линейно независимых от любого пакета данных (обычного или составного), ранее принятого посредством каждого из приемных устройств в релевантном наборе приемных устройств группы групповой передачи во время сеанса групповой передачи.
Релевантный набор приемных устройств, упоминаемый выше, в общем, включает в себя, по меньшей мере, два приемных устройства и может быть поднабором или полным набором приемных устройств во всей группе групповой передачи.
Под "ранее принятым пакетом данных", в общем, подразумевается передаваемый в режиме групповой передачи пакет данных (обычный или составной), который корректно демодулирован и декодирован по схеме FEC на стороне приемного устройства.
Посредством выполнения этой процедуры в каждом из множества (два или более) событий планирования и посредством передачи новых линейно независимых пакетов данных (составные пакеты данных и, возможно, также обычные пакеты данных), количество передач, требуемых для передачи данного объема передаваемой в режиме групповой передачи информации, сокращается, и пропускная способность для надежной групповой передачи повышается.
Специалисты в данной области техники должны понимать, что релевантный набор приемных устройств/пользователей, который должен рассматриваться при адаптации весовых коэффициентов кодирования, изменяется по мере того, как сеанс групповой передачи выполняется, и может отличаться от одного события планирования к следующему. Как только приемное устройство приняло все передаваемые в режиме групповой передачи пакеты данных, это приемное устройство более не рассматривается. В общем, только приемные устройства, которые все еще должны принимать один или более передаваемых в режиме групповой передачи пакетов данных, рассматриваются как релевантный набор группы групповой передачи. Это означает, что в течение всего сеанса групповой передачи релевантный набор приемных устройств, рассматриваемых в процессе планирования (т.е. адаптации весовых коэффициентов), постепенно уменьшается до тех пор, пока все приемные устройства не приняли всю передаваемую в режиме групповой передачи информацию.
Изобретатель выявил значимость адаптации кодовых весовых коэффициентов на основании ранее принятого набора пакетов для каждого приемного устройства в выбранном наборе приемных устройств, в отличие от выбора в предшествующем уровне техники поднабора приемных устройств, для которых применяется статический кодовый вектор только из единиц при условии, что все приемные устройства приняли все пакеты, кроме одного.
Как подробно пояснено позже, идея линейно независимого кодирования пакета данных может быть описана в отношении увеличения ранга матрицы векторов весовых коэффициентов (содержащей весовые коэффициенты кодирования). Более конкретно, ранее принятые передаваемые в режиме групповой передачи пакеты данных (обычные и/или составные пакеты данных), для каждого приемного устройства, могут быть описаны как линейная система уравнений на основании матрицы векторов весовых коэффициентов. Увеличение ранга соответствует формированию новой линейно независимой строки в матрице векторов весовых коэффициентов, которая эквивалентна новому линейно независимому кодированию передаваемого в режиме групповой передачи пакета данных.
1
2
Для лучшего понимания изобретения может быть полезным рассмотреть иллюстративный пример. Рассмотрим передающее устройство с двумя обычными пакетами данных, которые должны быть переданы двум приемным устройствам/пользователям U и U. Таблица I ниже иллюстрирует пример возможного сценария передачи/повторной передачи согласно примерному варианту осуществления изобретения. Например, набор кодирования "001" означает, что первый обычный пакет умножается на весовой коэффициент кодирования 0, второй обычный пакет умножается на весовой коэффициент кодирования 0, а третий обычный пакет умножается на весовой коэффициент кодирования 1, фактически означая, что только третий обычный пакет передается. Таким же образом, "001" для пользователя означает, что этот конкретный пользователь принял третий обычный пакет данных, тогда как "x" для пользователя означает, что информация не принята корректно этим пользователем.
Таблица I
TX #
Набор
U<sub>1</sub>
U<sub>2</sub>
Комментарии
1
001
001
X
U<sub>1</sub> принимает третий обычный пакет.
2
010
X
010
U<sub>2</sub> принимает второй обычный пакет.
3
100
X
100
U<sub>2</sub> принимает первый обычный пакет.
4
111
111
X
Возможно, например, что отправляется не 110 (поскольку ранг для U<sub>2 </sub>не увеличился бы), а 111, 101 и 011 OK. U<sub>1</sub> принимает составной пакет на основании весовых коэффициентов 111.
5
011
011
X
U<sub>1</sub> принимает составной пакет на основании весовых коэффициентов 011.
6
001
001
U<sub>2</sub> принимает составной пакет на основании весовых коэффициентов 001.
Пример таблицы I показывает двух пользователей, принимающих три пакета. Следует отметить, что, в общем, недостаточно принимать сначала только обычные пакеты и один составной пакет, чтобы гарантировать декодирование всех обычных пакетов данных. Вместо этого, проиллюстрировано, что передающее устройство должно адаптивно выбирать кодовые весовые коэффициенты, и в этом конкретном примере оно выполняет это на каждом этапе так, что ранг конкретной для приемного устройства матрицы каждого пользователя увеличивается для всех релевантных пользователей, если они принимают составной пакет. Адаптация весовых коэффициентов, как описано здесь, вместо адаптации набора пользователей, которым отправляется один составной пакет, как описано в документах предшествующего уровня техники [5-7], радикально повышает производительность. Помимо этого, ссылки [5-7] не используют конкретные для пользователя матрицы для планирования и кодирования. Дополнительно следует отметить, что в ссылках [5-7] передающее устройство не отправляет пакеты таким образом, чтобы приемное устройство могло использовать несколько составных пакетов одновременно для декодирования.
В этом примере также можно отметить, что как только один пользователь принял достаточное число пакетов данных, обычных и составных пакетов данных, и ранг соответствующей матрицы является полным, больше не требуется или даже невозможно далее увеличивать ранг матрицы этого приемного устройства. Следовательно, только матрицы неполного ранга рассматриваются при определении адаптивных кодовых весовых коэффициентов, что обеспечивает то, что ранг увеличивается для оставшихся приемных устройств матрицы неполных рангов. Предположим, что весовые коэффициенты кодирования составного пакета данных в первом событии планирования адаптированы так, что составной пакет представляет собой линейную комбинацию, которая является линейно независимой, для каждого приемного устройства из первого набора приемных устройств, от любого пакета данных, ранее принятого посредством приемного устройства во время сеанса групповой передачи. Во втором последующем событии планирования, весовые коэффициенты кодирования другого составного пакета данных тем самым могут быть адаптированы так, что составной пакет представляет собой линейную комбинацию, которая является линейно независимой для каждого приемного устройства из второго меньшего набора приемных устройств, от любого пакета данных, ранее принятого посредством приемного устройства во время сеанса групповой передачи.
Естественно, в более реалистичном сценарии число пользователей и число пакетов данных зачастую больше, но вышеупомянутый упрощенный пример служит для того, чтобы иллюстрировать ключевые характеристики настоящего изобретения. В практических вариантах применения число пользователей/приемных устройств K может быть любым числом от двух до, возможно, ста и более.
Обычно, линейная комбинация, например, двух обычных пакетов данных, таких как пакет A и пакет B, означает просто то, что пакеты комбинируются с равным взвешиванием, фактически используя один и тот же весовой коэффициент кодирования "1". Те обычные пакеты данных (такие как пакет C и пакет D), которые не рассматриваются в линейной комбинации, могут считаться имеющими весовой коэффициент кодирования "0".
При определенных обстоятельствах, особенно когда группа групповой передачи включает в себя три или более пользователей, возможность выбирать вектор весовых коэффициентов, имеющий, по меньшей мере, два различных ненулевых весовых коэффициента кодирования, увеличивает (и в большинстве случаев гарантирует) возможность формировать составной пакет данных, который представляет собой новое линейно независимое кодирование обычных пакетов данных, отличный от любого пакета данных (обычного пакета данных или составного пакета данных), ранее принятого посредством каждого релевантного приемного устройства, являющегося частью выбранного набора приемных устройств, во время сеанса групповой передачи.
1
2
3
Рассмотрим передающее устройство с тремя обычными пакетами данных, которые должны быть переданы трем приемным устройствам/пользователям U, U и U. Таблица II ниже иллюстрирует пример возможного сценария передачи/повторной передачи согласно другому примерному варианту осуществления изобретения. Например, набор кодирования "01" означает, что первый обычный пакет умножается на весовой коэффициент кодирования 0, а второй обычный пакет умножается на весовой коэффициент кодирования 1, фактически означая, что только второй обычный пакет передается. Таким же образом, "01" для пользователя означает, что этот конкретный пользователь принял второй обычный пакет данных, тогда как "x" для пользователя означает, что информация не принята корректно этим пользователем.
Таблица II
TX #
Набор
U<sub>1</sub>
U<sub>2</sub>
U<sub>3</sub>
Комментарии
1
01
01
X
X
U<sub>1</sub> принимает второй обычный пакет.
2
10
X
10
X
U<sub>2</sub> принимает первый обычный пакет.
3
11
X
X
11
U<sub>3</sub> принимает составной пакет.
4
12
12
X
X
Необходимо выходить за рамки поля {0,1} для того, чтобы находить новое линейно независимое кодирование: 12.
5
01
X
X
U<sub>1</sub> - это полный ранг, так что только U<sub>2</sub> и U<sub>3</sub> рассматриваются. Ни один не принимает.
6
01
-
X
01
U<sub>3</sub> принимает второй обычный пакет.
7
01
01
U<sub>1</sub> и U<sub>3</sub> - это полный ранг, так что только U<sub>2</sub> рассматривается, U<sub>2</sub> принимает второй обычный пакет.
1
2
3
Со ссылкой на таблицу III ниже, описывается еще один пример сценария передачи. В этом конкретном примере, рассмотрим передающее устройство с тремя обычными пакетами данных, которые должны быть переданы трем приемным устройствам/пользователям U, U и U.
Таблица III
TX #
Набор
U<sub>1</sub>
U<sub>2</sub>
U<sub>3</sub>
Комментарии
1
001
001
X
X
U<sub>1</sub> принимает третий обычный пакет.
2
010
X
010
X
U<sub>2</sub> принимает второй обычный пакет.
3
100
X
100
X
U<sub>2</sub> принимает первый обычный пакет.
4
101
101
X
X
Возможно, отправляется не 110 (поскольку ранг для U<sub>2 </sub>не увеличился бы), а 101 и 011 OK. U<sub>1</sub> принимает составной пакет на основании весовых коэффициентов 101.
5
011
X
X
011
U<sub>3</sub> принимает составной пакет на основании весовых коэффициентов 011.
6
111
X
X
111
U<sub>3</sub> принимает составной пакет на основании весовых коэффициентов 111.
7
211
X
211
X
Необходимо выходить за рамки поля {0,1} для того, чтобы находить новое линейно независимое кодирование: 211. U<sub>2</sub> принимает составной пакет на основании весовых коэффициентов 211.
8
110
110
-
X
U<sub>2</sub> - это полный ранг, так что только U<sub>1</sub> и U<sub>3</sub> рассматриваются.
9
001
-
-
001
U<sub>1</sub> и U<sub>2</sub> - это полный ранг, так что только U<sub>3</sub> рассматривается.
Следует отметить из таблицы II, что каждый пользователь принимает только два различных пакета данных, которые могут быть составными пакетами данных, обычными пакетами данных или комбинацией обоих. Также может быть подтверждено, что каждый пользователь может определять эти два обычных пакета данных, поскольку предусмотрено то, что каждый пользователь в каждой передаче гарантированно принимает новую линейную комбинацию обычных пакетов данных. То же самое применимо к таблице I и таблице III.
Как отмечено выше, специальная возможность адаптивно выбирать вектор весовых коэффициентов, имеющий, по меньшей мере, два различных ненулевых весовых коэффициента кодирования, увеличивает возможность всегда формировать составной пакет данных, который представляет собой новое линейно независимое кодирование обычных пакетов данных, отличный от любого пакета данных (обычного пакета данных или составного пакета данных), ранее принятого посредством каждого приемного устройства для всех или релевантного поднабора приемных устройств во время сеанса групповой передачи. При определенных обстоятельствах, особенно когда число пользователей является большим, это может быть важным, поскольку возможность передавать новые линейно независимые пакеты данных (обычные и/или составные пакеты данных) для каждого приемного устройства, по меньшей мере, в большей части событий передачи во время сеанса групповой передачи значительно повышает пропускную способность для надежной групповой передачи.
В общем, посредством систематической передачи определенного числа передаваемых в режиме групповой передачи пакетов или общих пакетов данных (обычных и/или составных пакетов данных), которые являются линейно независимыми от любого передаваемого в режиме групповой передачи пакета данных (обычного пакета данных или составного пакета данных), ранее принятого посредством набора приемных устройств во время сеанса групповой передачи, достаточно отправлять просто N таких пакетов данных для того, чтобы извлекать все N обычных пакетов данных, таким образом получая максимальную пропускную способность. Тем не менее, если приемное устройство принимает больше N пакетов данных, которые основаны только на N обычных пакетов данных, по-прежнему возможно извлекать N обычных пакетов данных.
По сравнению с традиционной групповой передачей ARQ, изобретение требует того, чтобы меньше передаваемых в групповом режиме пакетов данных отправлялось от передающего устройства в приемные устройства, чтобы обеспечивать корректный прием передаваемых пакетов данных. Изобретение предоставляет стратегию для надежной групповой передачи с детерминированными пределами на число пакетов, которое должно быть принято для декодируемости.
В примерном варианте осуществления изобретения также можно формировать несколько пакетов данных в данном событии планирования и передавать несколько составных пакетов в пакетной передаче. В таком событии планирования несколько составных пакетов данных обычно формируются с помощью одной информации обратной связи, так чтобы несколько составных пакетов данных зависели друг от друга (хотя каждый из них по-прежнему является линейно независимым от ранее принятых пакетов посредством каждого приемного устройства из релевантного набора приемных устройств, а также в пакетной передаче вышеприведенных передаваемых составных пакетов). Если это осуществляется систематически во множестве событий планирования, может быть возможным уменьшать объем служебных сигналов обратной связи, требуемых для передачи данного количества передаваемой в режиме групповой передачи информации.
Для лучшего понимания изобретения, примерная полная процедура ARQ будет далее вкратце описана со ссылкой на блок-схему последовательности операций способа по фиг.3.
На этапе S1, один или более пакетов данных отправляются от одного или более узлов в операции отправки, по меньшей мере, в два приемных узла. Каждый отдельный пакет данных предназначен для всех рассматриваемых приемных узлов, т.е. пакеты данных - это "передаваемые в режиме групповой передачи пакеты данных". Передача пакетов данных может осуществляться одновременно или последовательно, в зависимости от технологии передачи. На этапе S2, приемные узлы сохраняют соответствующие пакеты данных, которые корректно приняты (корректно демодулированы и декодированы согласно схеме FEC). На этапе S3, приемные узлы возвращают информацию пакетов, которые они приняли, в передающий(ие) узел(лы). На этапе S4, передающий узел формирует, если это выгодно, составной передаваемый в режиме групповой передачи пакет данных посредством использования сведений обратной связи о принимаемых пакетах данных от приемных узлов 110, 120 или альтернативно отправляет обычный передаваемый в режиме групповой передачи пакет данных. Составной передаваемый в режиме групповой передачи пакет данных обычно формируется на основании нескольких выбранных обычных передаваемых в режиме групповой передачи пакетов данных, которые должны быть (повторно) переданы. Например, число битов в составном передаваемом в режиме групповой передачи пакете преимущественно может быть меньше суммы числа битов частей пакетов, которые совместно кодированы. Передающий узел может формировать множество различных составных передаваемых в режиме групповой передачи пакетов для передачи, возможно, в комбинации с передачей обычных передаваемых в режиме групповой передачи пакетов данных, чтобы оптимизировать пропускную способность. На этапе S5, передающий узел передает составной передаваемый в режиме групповой передачи пакет данных или выбранный обычный передаваемый в режиме групповой передачи пакет данных во все приемные узлы. После приема составного передаваемого в режиме групповой передачи пакета данных приемные узлы декодируют, если возможно, составной передаваемый в режиме групповой передачи пакет данных и извлекают соответствующие передаваемые в режиме групповой передачи данные, которые ранее неизвестны, для соответствующего приемного узла. В процессе декодирования и извлечения, предпочтительно используются передаваемые в режиме групповой передачи пакеты данных, ранее декодированные согласно схеме FEC посредством приемного устройства.
В этом контексте, изобретение специально предназначается для формирования (кодирования) составных пакетов и определения (планирования) того, какие обычные пакеты данных использовать (и как) в каждом составном пакете данных. В этом смысле, формирование составного пакета данных может рассматриваться как совместная процедура планирования и кодирования. Это главным образом касается стороны передающего устройства, как проиллюстрировано на блок-схеме последовательности операций способа по фиг.4. На этапе S11, передающее устройство принимает информацию обратной связи, указывающую принимаемые пакеты данных, от приемных устройств. Как ранее упомянуто, ключевая характеристика изобретения состоит в том, чтобы формировать, по меньшей мере, один составной передаваемый в режиме групповой передачи пакет данных как взвешенную линейную комбинацию обычных пакетов данных на основании тщательно выбранного набора весовых коэффициентов кодирования, как указано на этапе S12 и S13. Весовые коэффициенты кодирования, по меньшей мере, для одного составного пакета данных адаптируются на этапе S12 на основании информации обратной связи о ранее принятых пакетах данных так, что составной пакет представляет собой новое кодирование обычных пакетов данных, линейно независимых от любого пакета данных, ранее принятого посредством каждого приемного устройства в релевантном наборе приемных устройств во время сеанса групповой передачи. Это означает, что весовые коэффициенты кодирования адаптивно выбираются в ответ на ранее принятые пакеты каждого приемного устройства через обратную связь, чтобы предоставлять новое линейно независимое кодирование обычных пакетов данных. На этапе S13, составной пакет данных формируется предпочтительно посредством умножения обычных пакетов данных на соответствующие адаптированные весовые коэффициенты кодирования. На этапе S14, формируемый составной пакет данных передается в приемные устройства. Как проиллюстрировано на последовательности операций полного ARQ на фиг.3, процедура предпочтительно повторяется до тех пор, пока все обычные пакеты в сеансе групповой передачи не переданы всем релевантным пользователям группы групповой передачи.
Дополнительно, несколько составных пакетов данных могут быть сформированы и переданы в данном событии планирования посредством повторения этапов S12-S14, как указано пунктирной линией на фиг.4. Это подробнее описано позже.
Обратная связь от приемных узлов в передающий узел предпочтительно может быть частью процедуры подтверждения приема (ACK). Сообщения обратной связи в типичном варианте могут составляться различными способами, например, в зависимости от используемых протоколов передачи, процедуры ARQ и т.д.
Различные способы и форматы кодирования могут использоваться с изобретением, как подробнее описано ниже.
Следует понимать, что при настоящем изобретении ничего не препятствует полной процедуре начаться на этапе S1 (см. фиг.3) посредством передачи составного пакета данных.
Также следует отметить, что передачи могут осуществляться одновременно, если используется технология передачи, предоставляющая возможность параллельных передач, например, используется множественный доступ с ортогональным частотным разделением каналов (OFDMA), т.е. первый пакет и второй пакет отправляются параллельно, но по непересекающимся наборам OFDM-поднесущих. Повторная передача также может осуществляться одновременно.
В более математическом подходе, чтобы пояснить изобретение, ранее принятые передаваемые в режиме групповой передачи пакеты данных (обычные и/или составные пакеты данных) для каждого приемного устройства, могут быть описаны как линейная система уравнений на основании матрицы векторов весовых коэффициентов. Для ранее принятого составного пакета данных вектор весовых коэффициентов, обозначенный как ω, должен включать в себя набор весовых коэффициентов кодирования, тогда как для ранее принятого обычного пакета данных вектор весовых коэффициентов должен включать в себя один ненулевой весовой коэффициент кодирования. При событии кодирования и планирования, при формировании нового составного пакета данных для передачи в приемные устройства идея состоит в том, чтобы адаптивно выбирать весовые коэффициенты кодирования взвешенной линейной комбинации обычных пакетов данных на основании обратной связи ранее принятых пакетов данных так, что ранг должен увеличиваться для линейной системы уравнений каждого рассматриваемого приемного устройства. Увеличение ранга соответствует формированию новой линейно независимой строки в конкретной для каждого приемного устройства матрице векторов весовых коэффициентов, которая эквивалентна новому линейно независимому кодированию передаваемого в режиме групповой передачи пакета данных.
Теперь, при приеме посредством каждого пользователя одного или более передаваемых в режиме групповой передачи пакетов данных (обычных и/или составных пакетов данных) можно рассматривать их как систему линейных уравнений, в которой передаваемые в режиме групповой передачи пакеты данных известны, взвешивания известны, и каждый набор приемных устройств стремится решать свою линейную систему уравнений для того, чтобы определять и декодировать обычные пакеты данных. На стороне передающего устройства цель состоит в том, чтобы формировать (диспетчеризовать и кодировать) соответствующую систему уравнений, а на стороне приемного устройства цель состоит в том, чтобы решать (декодировать) линейную систему уравнений и извлекать обычные пакеты данных.
Если новый линейно независимый передаваемый в режиме групповой передачи пакет данных передается каждый раз так, что ранг последовательно увеличивается для каждого принимаемого пакета данных (для каждого пользователя, принимающего пакет данных) или, по меньшей мере, большинство раз, пропускная способность значительно повышается. В первом случае, когда новый линейно независимый передаваемый в режиме групповой передачи пакет данных передается каждый раз, декодируемость N обычных пакетов данных может быть гарантирована, когда просто N пакетов данных принято, поскольку матрица векторов весовых коэффициентов включает в себя N линейно независимых строк, из которых могут быть извлечены все N обычных пакетов данных. Поскольку ранг матрицы увеличивается для каждого принимаемого пакета данных, достаточно обеспечивать то, что все пользователи приняли только N пакетов данных, для того чтобы декодировать и извлекать все N обычных пакетов данных.
Кроме того, чтобы предоставлять то, что ранг увеличивается для всех или поднабора рассматриваемых приемных устройств, авторы изобретения выяснили, что иногда недостаточно использовать весовые коэффициенты, которые могут допускать только значения 0 и 1. Иногда, когда число приемных узлов является большим относительно числа обычных пакетов, которые предусмотрены для передачи, будет полезным использовать вектор весовых коэффициентов, который имеет, по меньшей мере, два различных ненулевых весовых коэффициента кодирования, как пояснено ранее.
Отметим, что хотя линейная комбинация, в принципе, может быть выполнена с помощью обычной арифметики, приводя к переносу битов, которые должны быть сформированы для составного пакета, предпочтительно использовать показатель, который обеспечивает то, что длина составного пакета является практически такой же, как для обычных пакетов. Следовательно, арифметика на основании конечных полей предпочтительна и предполагается далее. Возможным типом арифметики является так называемая арифметика по модулю, но изобретение не ограничено ею. Также отметим, что операция линейного кодирования может быть выполнена для полного пакета данных, или альтернативно обычные пакеты данных делятся на несколько более управляемых подстрок, для которых выполняется одна операция линейного кодирования.
Отметим, что далее предполагается, что мы оперируем с любым типом арифметики, который предоставляет те же правила, что и традиционная арифметика, которая дает возможность формирования (планирования и кодирования) и решения (декодирования) линейной системы уравнений. Следовательно, без потери общности, уравнения далее записываются в традиционной арифметической системе обозначений.
Во-первых, априорная информация каждого пользователя, т.е. ранее принятые общие передаваемые в режиме групповой передачи пакеты данных (обычные и/или составные пакеты данных), может быть описана как линейная система уравнений согласно следующему:
n
k
k
k
k
.
где d - это значение n-го обычного пакета, - это значение для m-го общего передаваемого в режиме групповой передачи пакета данных для пользователя k,  - это весовой коэффициент для пользователя k и обычного пакета n и принимаемого общего передаваемого в режиме групповой передачи пакета данных m пользователем k, M - это последний принимаемый пакет данных пользователем k, а N - это общее число обычных пакетов, которые должны быть переданы. Отметим, что каждый пользователь, возможно, принял различное число передаваемых в режиме групповой передачи пакетов данных, и для этого нужен индекс k в переменной M
k
Теперь, чтобы упростить систему обозначений, можно записать (1) в матричной форме для пользователя :
k
k
C=WD (2)
Формирование (кодирование) и решение (декодирование) системы линейных уравнений, возможно, как указано ранее, выполняется с помощью обычной арифметики, "арифметики по модулю" или любой другой подходящей арифметики.
Значения, которые весовые коэффициенты  могут допускать, в типичном варианте ограничиваются по числу. Дополнительно, изобретение не устанавливает специальным образом то, какие значения можно допускать для весовых коэффициентов, и они могут быть выбраны из произвольного набора, к примеру, {0,..., 3} или даже некоторого более мнимого произвольного набора, такого как {0, 1, 2, 3, 5, 7, 11, 13}. Чем больше число значений, которые могут быть допущены, тем большая степень свободы представляется, что помогает находить кодовый вектор, который может быть использован для того, чтобы формировать составной пакет данных. Кроме того, большее число пакетов влечет за собой большую степень свободы, что помогает находить кодовый вектор, который может быть использован для того, чтобы формировать составной пакет данных.
Тем не менее, алфавит для весовых коэффициентов кодовых векторов в типичном варианте должен быть достаточно большим, чтобы получать достаточную степень свободы для того, чтобы давать возможность всем рассматриваемым пользователям получать N линейно независимых уравнений. Однако алфавит не должен быть очень большим. Моделирование демонстрирует, что для K=20 пользователей, N=6 пакетов, где вероятности приема для пользователей являются независимыми, и каждая вероятность приема при этом допускается равной p=0,05, достаточен размер алфавита (или, эквивалентно, основание b) только в 3 элемента {0, 1, 2} (или, эквивалентно, основание b=3).
N
N
p,
Чтобы реализовать идею минимального значения для основания b (или, эквивалентно, минимального числа элементов в алфавите), мы знаем, что число кодовых слов bдолжно быть больше, чем число, которое каждый из K пользователей принимает, в наихудшем случае, N различных передаваемых в режиме групповой передачи пакетов данных. Следовательно, условие состоит в том, что b>N·K. Хотя это не идеальная оценка, тем не менее, она указывает, что b, N и K взаимосвязаны. Также обычно имеется зависимость от вероятности приема и при высокой вероятности приема есть высокая вероятность того, что несколько пользователей принимают один пакет данных.
k
Также отметим, что возможно то, что строка в W и кодовый вектор или вектор весовых коэффициентов содержат только один ненулевой элемент. Это эквивалентно отправке просто одного обычного пакета для общего передаваемого в режиме групповой передачи пакета данных. Изобретение предпочтительно использует арифметику конечных полей, которая позволяет использовать больше элементов, чем только "0" и "1". Когда число пользователей является большим и число обычных пакетов данных к передаче является небольшим, это гарантирует обнаружение новых линейных комбинаций.
В систематическом подходе, когда желательно находить новую линейную комбинацию каждый раз, базовая последовательность операций следующая:
- Рассмотрение группы групповой передачи пользователей, где пользователи индексируются посредством k
- При N обычных пакетов данных для групповой передачи
k
- Для каждого пользователя k, извлечение матрицы весовых коэффициентов W
k
k
k
- k выбор кодового вектора так, чтобы Rank(W')=Rank(W)+1, где  для тех k, где Rank(W)<N
- Формирование и отправка составного пакета на основании кодового вектора ω
- Обновление всех матриц весовых коэффициентов на основании обратной связи приема.
Другая эквивалентная формулировка, также дающая в результате увеличение ранга, следующая:
- Рассмотрение группы групповой передачи пользователей, где пользователи индексируются посредством k
- При N обычных пакетов данных для групповой передачи
k
- Для каждого пользователя k, извлечение матрицы весовых коэффициентов W
k
k
- Определение нуль-пространства для W и обозначение его как Ξ
-
k
k выбор кодового вектора ω так, что  для тех k, где Rank(W)<N
- Формирование и отправка составного пакета на основании кодового вектора ω
- Обновление всех матриц весовых коэффициентов на основании обратной связи приема.
Как пояснено ранее, другой способ формулирования этого состоит в том, чтобы заявлять, что весовые коэффициенты кодирования выбираются так, что каждый раз отправляется новое линейно независимое кодирование обычных пакетов данных.
Вышеупомянутая операция обеспечивает то, что любой пользователь, принимающий общий передаваемый в режиме групповой передачи пакет данных, всегда увеличивает свой ранг. Когда пользователь принял N пакетов данных групповой передачи, система уравнений должна иметь N линейно независимых строк, т.е. полный ранг. Следовательно, пользователь может декодировать все обычные пакеты данных, принимая только минимальное число общих передаваемых в режиме групповой передачи пакетов данных. Поскольку может отнимать больше времени для определенного пользователя то, чтобы принимать свои N пакетов данных групповой передачи, некоторые другие пользователи могут принимать свои требуемые N пакетов данных групповой передачи и затем некоторые последующие пакеты данных, которые являются избыточными и могут быть отброшены (или не приняты).
N
Возможный подход для того, чтобы находить подходящий кодовый вектор ω, основан на гипотезе итерационных испытаний предварительных кодовых векторов ω. Например, выберем алфавит (т.е. поле) значений, которые могут допускать элементы кодового вектора ω. С учетом алфавита, упорядочим список со всеми возможными перестановками, т.е. список, имеющий b вариантов кодового вектора (где b - это число элементов в поле, а N - это число обычных пакетов данных, которые должны быть переданы). Выполняем поиск по списку от начала до конца (или так далеко, как требуется) и по очереди назначаем каждый элемент в списке как вариант кодового вектора ω. Для каждого варианта кодового вектора ω проверяем то, удовлетворяется ли условие согласно алгоритму кодирования/планирования (т.е. ранг увеличивается или альтернативно ненулевой вектор проецирует ω на нуль-пространство) для всех пользователей с матрицами весовых коэффициентов неполного ранга. Если условие выполняется, выбираем вариант кодового вектора в качестве кодового вектора ω.
Фактически, вариант кодового вектора может быть создан посредством прибавления значения "1" к предыдущему варианту кодового вектора, т.е. просто счетчика. Чтобы предоставлять подходящий набор значений для весовых коэффициентов, к примеру, от нуля до некоторого числа b-1, вариант кодового вектора может использовать и выполнять подсчет с основанием b, где каждая цифра должна соответствовать весовому коэффициенту.
b
В качестве альтернативы подсчету в прямом направлении с основанием для следующего варианта кодового вектора можно вместо этого проходить через все или набор слов с весовым коэффициентом "1", т.е. только один весовой коэффициент является ненулевым, а затем все или комбинации набора слов с весовым коэффициентом "2" и так далее. Идея здесь состоит в том, чтобы сохранять число на ненулевых элементах весового коэффициента максимально низким, чтобы минимизировать сложность кодирования и декодирования. По меньшей мере, для одного кодового вектора, тем не менее, имеется, по меньшей мере, два ненулевых весовых коэффициента кодирования в соответствии с изобретением.
k
.
,
k
k
k
k
k
k
k
k
k
k
k
k
В качестве альтернативы, может быть возможным определять кодовый вектор непосредственно из нуль-пространств матриц весовых коэффициентов. Для каждого пользователя  рассмотрим матрицу весовых коэффициентов Wи определим ассоциированное нуль-пространство и обозначим его Ξ. Для каждого пользователя k теперь следует сформировать кодовый вектор ω с таким свойством, что он имеет ненулевую проекцию, по меньшей мере, на один из векторов в ΞМы знаем, что, если кодовый вектор ω выбирается как одно из основания в Ξ, скажем, первый вектор нуль-пространства ξкаждый должен иметь требуемую ненулевую проекцию для этого пользователя. Тем не менее, необходимо обеспечивать то, что это является истиной для всех или, по меньшей мере, для данного поднабора пользователей. Один способ, чтобы добиться этого, состоит в том, чтобы формировать суперпозицию по всему первому вектору нуль-пространства ξ в Ξрассматриваемого пользователя. Тем не менее, необходимо не допускать, чтобы какой-либо вектор ξ отменялся посредством другого ξ вследствие суперпозиции. Если это не достигается, можно изменять весовые коэффициенты для суперпозиции или выбирать один или более ξ как не первый вектор в соответствующем нуль-пространстве Ξ. Следовательно, задача состоит в том, чтобы находить кодовый вектор ω так, что ξ •ω ≠ 0 k, где "•" - это скалярное произведение.
k
В качестве альтернативы или дополнения также возможно приближаться к идее с точки зрения оптимизации, поскольку есть множество различных вариантов кодового вектора ω, которые могут быть выбраны в каждом примере. Цель оптимизации предпочтительно должна состоять в том, чтобы гарантировать, что требуется только небольшое число операций кодирования и декодирования, т.е., в сущности, делать W настолько разреженным, насколько возможно. Такие критерии оптимизации для ω могут быть эвристическими согласно, но не только, следующему:
- Минимизация ω•1, где 1 - это вектор-столбец из единиц или
- Минимизация набора ненулевых элементов в ω, или,
T
T
- Минимизация ω • ω, где  - это транспозиция вектор-матрицы.
k
k.
На стороне передающего устройства, чтобы сохранять сложность максимально низкой, к примеру, при определении ранга, реализация этого алгоритма может использовать результаты и обработанные версии матриц весовых коэффициентов из предыдущего цикла вычисления. Например, при использовании результата Гауссова исключения, выполняемого для последних циклов,  - это новый W, если пакет успешно принят пользователем Вычисление ранга нового  для следующего цикла может быть основано на форме Гауссового исключения  из предыдущего цикла с измененным предварительным кодовым вектором ω.
Аналогично стороне передающего устройства сторона приемного устройства может использовать результаты и обработанные версии матриц весовых коэффициентов из предыдущего приема передаваемого в режиме групповой передачи пакета данных. Например, может использоваться результат из предыдущего Гауссового исключения(й).
Способы кодирования
Пример кодирования, подходящего для настоящего изобретения, предпочтительно основан на побитовом кодировании по схеме XOR вследствие его простоты. Операция XOR соответствует весовым коэффициентам кодирования в единицу, как пояснено ранее.
Можно предположить множество различных способов для того, чтобы совместно XOR- кодировать и затем идентифицировать то, какие пакеты совместно кодированы.
Пример возможных форматов кодового кадра приводится со ссылкой на иллюстрации по фиг.5. В этом примере, два пакета данных (A) 1005 и (B) 1010 совместно кодированы, чтобы сформировать составной передаваемый в групповом режиме пакет 1015 данных. Рабочие данные могут быть подвергнуты операции XOR непосредственно, но средство идентификации того, какие отдельные пакеты кодированы совместно, должно быть предоставлено. В примерном способе кодирования по фиг.5, идентификаторы (к примеру, заголовки или поднаборы релевантной информации из отдельных заголовков пакета) участвующих совместно кодированных пакетов (здесь только два пакета показано, но идея может легко распространяться на большее количество пакетов) сообщаются в заголовке 1020 составного пакета. Идентификатор, например, может содержать адрес передающего устройства, адрес групповой передачи и порядковый номер пакета для каждого кодированного пакета. Кроме идентификаторов, заголовок составного пакета предпочтительно также сообщает формат составного передаваемого в режиме групповой передачи пакета, т.е. то, где пакеты размещены в составном передаваемом в режиме групповой передачи пакете. Например, если есть два пакета и один из пакетов содержит меньше битов, чем другой пакет, как на фиг.5, число битов, содержащихся в пакете с меньшим количеством битов, а также позиция первого бита более короткого пакета обычно также указывается. Когда число битов отличается, заполнение 1025 используется, как на фиг.5 для пакета B 1010. Поле формата заголовка 1020 составного пакета также может сообщать, что два пакета B и C конкатенированы один за другим (не показано) и затем кодированы, к примеру, с третьим пакетом A или дополнительными пакетами. Весь составной пакет, включающий в себя заголовок, затем предпочтительно кодируется согласно FEC.
После корректного декодирования FEC и обнаружения корректного CRC 1030 иллюстрируемый заголовок составного пакета обеспечивает простую идентификацию того, какие пакеты кодированы вместе. Приемное устройство затем может использовать эту информацию для того, чтобы выбирать заранее известный пакет из хранилища декодированных пакетов данных и извлекать другой(ие) пакет(ы). Следует отметить, что заголовок составного пакета также может содержать другую информацию. Другая версия формата пакета (не показана), отличная от проиллюстрированной выше, должна сообщать заголовок составного пакета в общем широковещательном сообщении, т.е. в определенном типе внеполосных служебных сигналов, при кодировании рабочих данных нескольких пакетов. Еще один дополнительный способ кодирования (не показан) может заключать в себе подход идентификации вслепую, т.е. тестирование гипотезы кодированных сообщений, где и заголовки, и рабочие данные пакетов кодируются вместе, в сравнении с базой данных априорной информации и использованием CRC-проверки для того, чтобы тестировать допустимость тестирования гипотезы.
m
Настоящее изобретение не ограничено использованием XOR-операций при кодировании составных пакетов данных. XOR-операция - это линейное суммирование по полю F(2) с элементами {0, 1}. Как упомянуто выше, автор изобретения выяснил, что, когда число приемных устройств возрастает, становится важным расширять поле дополнительными элементами, чтобы обеспечивать то, что ранг для матрицы каждого приемного устройства может увеличиваться в каждой передаче. Следовательно, поле может быть расширено до 3 элементов {0, 1, 2}, четырех элементов {0, 1, 2, 3} и так далее. В общем, как известно в общей теории кодирования, поля должны иметь p элементов, где p - это простое число, а m - это положительное целое число, чтобы быть четко определенным. Также известно, что поля одинакового размера являются изоморфными в том смысле, что не имеет значения, содержит ли поле различные элементы, скажем, {0, 1, 2} или {2, 3, 7}. В дополнение к идентификаторам (к примеру, заголовкам или поднаборам релевантной информации из отдельных заголовков пакета) участвующих совместно кодированных пакетов, значения векторов весовых коэффициентов, используемых, когда поле составляет больше, чем два элемента, как пояснено выше, предпочтительно также сообщаются в заголовке 1020 составного пакета.
Дополнительный пример операции кодирования, подходящей для использования в способе согласно изобретению, основан на операторе по модулю, оперирующем с сигнальными созвездиями, т.е. после FEC-кодирования и модуляции. Кодирование на символ сигнального созвездия рассматривается далее, и процедура может быть повторена для множества последовательных символов сигнального созвездия. Операция по модулю в этом примере выполняется и для действительной, и мнимой части независимо при обработке комплексных чисел и использует определение операции по модулю и следующее математическое наблюдение:
((A+B)
L - B)
L =
L
mod mod (A) mod ,
которое указывает, что сигнал B в форме действительных значений может быть наложен на сигнал A в форме действительных значений и обеспечивает неискаженное восстановление сигнала (до тех пор, пока сигнал A не превышает уровень квантования L), хотя амплитуда (и, следовательно, мощность) ограничивается в (нелинейно закодированном) составном сигнале.
1
2
i
2
2
1
На практике, это может использоваться следующим образом. Передающее устройство имеет символы S и S, которые в типичном варианте допускают различные значения. Например, в 16 QAM, S {-3,-1,1,3}+i{-3,-1,1,3}. Теперь, поскольку приемное устройство имеет сведения о последовательности данных D(n), оно также имеет сведения о соответствующем символе S (для каждого S). Затем для действительной части (и в равной степени для мнимой части) совместно кодированный сигнал в передающем устройстве следующий:
,
который затем принимается и уравнивается, т.е. компенсируется на предмет потерь в тракте передачи (при условии, что один масштаб используется и для принимаемого сигнала, и для сигнала, который вычитается) и комплексной фазы (при условии, что соответствующая синфазная ось и ось квадратурной фазы совмещены с сигналом, который вычитается), чтобы давать в результате принимаемый сигнал:
(Re)
где N - это член шума (и помех). Требуемый сигнал затем восстанавливается с помощью:
Кодирование также может осуществляться посредством квантования посредством более многомерной решетки, чем только одномерное квантование, как описано выше. В этом случае, квантование оперирует с вектором, а не скаляром.
Обычно, приемный узел может не иметь полной информации, требуемой для того, чтобы сразу полностью декодировать и извлекать собственные данные из составного передаваемого в режиме групповой передачи пакета данных, а должен ждать, чтобы принимать больше пакетов данных. Если это происходит, приемный узел может частично декодировать составной передаваемый в режиме групповой передачи пакет данных и сохранять результат, остаточный составной передаваемый в режиме групповой передачи пакет данных, для дополнительной обработки, когда дополнительная информация доступна. Это декодирование, для каждого приемного устройства, может быть выполнено посредством вычисления приведенной формы уровней строк в соответствии с текущей кодовой матрицей и осуществления обновленной приведенной формы уровней строк для каждого принимаемого нового пакета данных (обычного или составного). Альтернативно, составной передаваемый в режиме групповой передачи пакет данных сохраняется без попытки декодировать до тех пор, пока приемный узел не получил всю требуемую информацию. Информация, требуемая для декодирования основной части составного передаваемого в режиме групповой передачи пакета данных, может, например, содержаться в заголовке. Также это декодирование может быть выполнено посредством подхода приведенной формы уровней строк. Каждое приемное устройство, в сущности, заинтересовано в инвертировании кодовой матрицы (в пределах поля, которое оно использует) и умножения ее на принимаемые пакеты данных. Чтобы быть точным, это нужно сделать, в отношении операции кодирования, для каждой подстроки битов, на которые делится пакет данных.
Посредством использования обычных и составных пакетов данных и посредством разрешения передающему узлу (через информацию обратной связи) и приемному узлу использовать эту информацию, можно сокращать количество передач, требуемых для того, передавать определенный объем данных от одного узла в другой. Это увеличивает совокупную пропускную способность, а также пропускную способность отдельного пользователя (или эквивалентно, узла). Помимо этого, характеристики сквозной задержки улучшаются. Альтернативно, в зависимости от условий, уменьшенное количество передач может использоваться для того, чтобы повышать эффективность по мощности и энергии в системе связи с передающим устройством и несколькими приемными устройствами.
Следует понимать, что передающее устройство может использовать и применять всю доступную информацию обратной связи о принимаемых пакетах данных. В дополнение к информации обратной связи, поясненной выше, дополнительная информация, к примеру, информация по качеству обслуживания (QoS) и характеристики пакета данных, также может использоваться при формировании составных пакетов данных.
Фиг.6 - это принципиальная блок-схема, иллюстрирующая систему для групповой передачи пакетов данных от передающего устройства нескольким пользователям согласно предпочтительному примерному варианту осуществления изобретения.
Модули и блоки, описанные ниже, в зависимости от выбранной реализации, могут рассматриваться как функциональные части передающего и/или приемного узла в системе связи и не обязательно как физически отличительные объекты. Подключения, таким образом, могут интерпретироваться как линии связи между функциональными частями и не обязательно физические подключения.
Полная система основана на обмене данными передающим устройством 100 с определенным числом пользователей от 200-1 до 200-K через более или менее подверженные ошибкам каналы связи или линии связи.
Передающее устройство, такое как передающий узел 100, в основном содержит модуль 110 буфера данных, ACK-регистр 120, планировщик 130 групповой передачи, кодер 140 передаваемых в режиме групповой передачи пакетов, а также некоторую форму средства передачи, которое предоставляет необходимые функциональности для выполнения фактической групповой передачи.
Передающее устройство также может содержать средство для обработки информации об одноадресной передаче (не показано).
Модуль 110 буфера данных временно хранит пакеты данных для последующей планирования/кодирования и передачи пользователям/приемным устройствам 200.
Типично, как ранее пояснено, передающий узел 100 сначала передает один или более обычных пакетов данных. По мере того информация обратной связи становится доступной из приемных устройств, и составные передаваемые в режиме групповой передачи пакеты могут быть сформированы, передающий узел также может формировать и передавать один или более составных передаваемых в режиме групповой передачи пакетов данных.
Планировщик 130 групповой передачи учитывает пакеты данных, которые постоянно размещаются в модуле 110 буфера данных, и также учитывает информацию ACK от различных приемных узлов, сохраненную в ACK-регистре 120.
По сути, планировщик 130 групповой передачи выполняет планирование обычных пакетов данных, доступных в модуле 110 буфера данных, посредством определения набора весовых коэффициентов кодирования на основании обратной связи ACK в ACK-регистре 120. Планировщик 130 групповой передачи сообщает кодеру 140 передаваемых в групповом режиме пакетов данных, который формирует или кодирует составной передаваемый в режиме групповой передачи пакет данных как взвешенную линейную комбинацию обычных пакетов данных на основании выбранных весовых коэффициентов кодирования. Эта так называемое совместное планирование и кодирование проиллюстрирована подробно на фиг.7. Планировщик 130 групповой передачи имеет модуль для определения/адаптации весовых коэффициентов так, что новое линейно независимое кодирование может быть сформировано, как требуется и когда требуется. Как указано ранее, это кодирование в конкретном варианте осуществления может быть основано на наборе весовых коэффициентов кодирования (этот набор весовых коэффициентов также упоминается как вектор кодирования), который включает в себя, по меньшей мере, два ненулевых весовых коэффициента кодирования.
Планировщик 130 групповой передачи в типичном варианте выполнен с возможностью обработки операций обычной/традиционной групповой передачи ARQ.
Вспомогательные сведения также могут использоваться для планирования. Дополнительная информация может включать в себя, но не только: требования по QoS для возможности обслуживать аспекты планирования по QoS, а также состояние отдельных пакетов, такое как значение времени существования.
Приемное устройство, такое как приемный узел 200, в основном содержит средство приема, которое предоставляет необходимую функциональность для осуществления фактического приема, декодер 210 передаваемых в режиме групповой передачи пакетов данных с функциональностью обратной связи, а также модуль 220 буфера данных. Модуль буфера данных обычно выполнен с возможностью сохранения пакетов данных, которые еще не доставлены в k приемных модулей.
Когда составной пакет принят, декодер 210 приемного устройства 200 обычно идентифицирует то, какие пакеты кодированы вместе. Используя обычные передаваемые в режиме групповой передачи пакеты данных или составные передаваемые в режиме групповой передачи пакеты данных, или и то, и другое, сохраненные в модуле 220 буфера, декодер пытается декодировать составной передаваемый в режиме групповой передачи пакет, чтобы извлекать отдельные обычные пакеты данных. Декодер 210 также выполнен с возможностью выдачи и обработки сообщений обратной связи, в том числе сообщений по ARQ.
После того как приемное устройство 200 успешно приняло передаваемый в режиме групповой передачи пакет данных (обычный пакет данных или составной пакет данных), оно отправляет ACK-сообщение передающему устройству 100, чтобы подтверждать то, что оно приняло пакет, сразу или с небольшой задержкой. Задержка может быть полезной, чтобы не занимать ресурсы и не тратить бесполезно энергии вследствие служебной информации каждого пакета обратной связи. Обновление предпочтительно достигается через средство ARQ приемного устройства и средство ARQ передающего устройства.
Кроме того, отметим, что приемное устройство 200 также может выступать в качестве передающего устройства, если данные затем отсылаются. То же самое применимо к передающему устройству 60, т.е. оно также может выступать в качестве приемного устройства для других данных.
Вышеописанные варианты осуществления приведены просто в качестве примеров, и следует понимать, что настоящее изобретение не ограничено ими. Дополнительные модификации, изменения и усовершенствования, которые сохраняют основополагающие принципы, раскрытые и заявленные в данном документе, находятся в пределах объема изобретения.
ПРИЛОЖЕНИЕ A
Создано средство моделирования на основании алгоритма обязательности повышения ранга каждого передаваемого в режиме групповой передачи пакета данных для каждого пользователя, который увеличивается на один шаг в каждом цикле итерации.
Следующие конечные результаты моделирования представляют собой матрицы весовых коэффициентов для трех пользователей, которым пять передаваемых в режиме групповой передачи пакетов данных должны быть отправлены по i.i.d каналам со стиранием пакетов, где вероятность приема составляет p=0,1, а вектор весовых коэффициентов использует основание b=3. Отметим, что самое большее отдельная строка добавляется в каждом случае к данным матрицам, когда они создаются, и матрицы, показанные здесь, представляют собой случай первых пяти принимаемых передаваемых в режиме групповой передачи пакетов данных. Легко подтвердить, что каждая матрица весовых коэффициентов имеет полный ранг и что все кодированные пакеты данных могут быть извлечены для каждого пользователя.
b
Дополнительное моделирование с другим числом пакетов и числом пользователей экспериментально подтвердило, что полный ранг может всегда достигаться при условии, что основание вектора весовых коэффициентов выбирается достаточно большим для того, чтобы обслуживать достаточное число комбинаций, которые нужно проверить.
T=p
Следует отметить, что производительность примерно составляет T~p, когда p≠1 для всех K, независимо от числа пакетов. Изобретение предоставляет оптимальную пропускную способность для полностью надежной групповой передачи, т.е. , когда пропускная способность анализируется для бесконечного числа пакетов.
),
Схема изобретения является детерминированно декодируемой, т.е. в отличие от фонтанного кодирования (FCдля нее достаточно принимать ровно такое же число кодированных пакетов, чтобы извлекать такое же количество обычных пакетов данных. Производительность FC, определенная посредством коэффициента 1+ε, зависит от числа пакетов, которые отправляются. FC требует большого количества пакетов, порядка 1000 и больше, для того чтобы обеспечивать низкое ε. Такой зависимости в предложенном изобретении нет.
Источники информации
1. J. W. Byers, M. Luby, M. Mitzenmacher, and A. Rege "A digital fountain approach to reliable distribution of bulk data. In Proceedings of ACM", SIGCOMM, стр. 56-67, 1998 г.
2. J. Byers, M. Luby, and M. Mitzenmacher, "A digital fountain approach to asynchronous reliable multicast", IEEE Journal on Selected Areas in Communications, 20(8), октябрь 2002 г.
3. J. Sachs, M. Meyer, S. Wager, H. Huschke, M.W. Larsson, P. Larsson, "Method and devices for efficient data transmission link control in mobile multicast communication systems". Заявка на патент (США) 2006/0154603.
4. P. Larsson, N. Johansson, "Multi-User ARQ", In conference proceedings of VTC2006spring, Melbourne, 7-10 мая 2006 г.
5. Shen Yong, Lee Bu Sung, "XOR retransmission in multicast error recovery", (ICON 2000), Proceedings, IEEE International Conference on Networks, стр. 336-340, 2000 г.
6. M.A. Jolfaei, S.C. Martin, J. Mattfeldt, "A new efficient selective repeat protocol for point-to-multipoint communication", 1993. ICC 93. Geneva. Technical Program, Conference Record, IEEE International Conference on Communications, Volume 2, 23-26 мая 1993 года, стр. 1113-1117, том 2.
7. M. A. Jolfaei, U. Quernheim, "Effective Block Recovery Schemes for ARQ Retransmission Strategies" IEEE Int. Symposium on Personal, Indoor and Mobile Radio Communications, 1994. Wireless Networks - Catching the Mobile Future. 5-ый том, 3 издание, 18-23 сентября 1994 года, стр. 781-785, том 3.