Vi anser att den välstuderade radionätsmodellen: en synkron modell med en graf G = (V, E) med  på V = n där varje nod i varje omgång antingen sänder ett paket, med längd B =  och (log n) bitar, eller lyssnar. Varje nod får ett paket iff som den lyssnar på och exakt en av sina grannar sänder. Vi anser att problemet med k- meddelandesändning, där k- meddelanden, var och en med B- bitar, placeras i en godtycklig noder av grafen och målet är att leverera alla meddelanden till alla noder. Vi presenterar ett enkelt bevis som visar att det finns ett radionät med radie 2 där för alla k, sändning k meddelanden kräver minst  och (k log n) rundor. Det vill säga, i detta nätverk, oavsett algoritm, den maximala möjliga sändningsgenomströmningen är O( 1 log n ). Vi anser att den välstuderade radionätmodellen, först inkränkt av Chlamtac och Kutten [2]. Dessa anslutningar i denna modell presenteras med en graf G = (V, E) med  på V = n. Dessutom är modellen synkroniserad, dvs exekveringarna fortsätter i lås-steg-rundor. I varje omgång skickar varje nod antingen ett paket, med längd B =  och (log n) bitar, eller lyssnar. Varje nod får ett paket iff den lyssnar och exakt en av sina grannar sänder ett paket. Vi anser att k-meddelandet sänder problem, där k-meddelanden, var och en bestående av  på B-bitar, placeras i en godtycklig delmängd av noderna i grafen och målet är att leverera alla dessa meddelanden till alla noder. Vi kräver inte att paketen som noderna överför (över kanalen) är ett av dessa meddelanden. Med andra ord begränsar vi inte algoritmen till att vara en routingalgoritm, och i synnerhet kan det vara en nätverkskodningsalgoritm [4], där vart och ett av de överförda paketen är en kombination av några av meddelandena. Vi visar följande teorem. Teorem 2.1. Det finns ett radionät med radie 2 där det för alla k, sändning k meddelanden kräver minst  på (k log n) rundor. Det huvudsakliga tillvägagångssättet för vårt bevis liknar beviset för.log 2 n) nedre gränsen för Alon, Bar-Noy, Linial och Peleg [1] på tiden för att sända ett enda meddelande i radionät med radien 2. Vi noterar att Theorem 2.1 också är en följd av det skvaller som ligger längst ner i Gasienec och Potapov [3], vilket i sig uppnås genom en minskning till  och 2 n) nedre gränsen av [1]. Vårt bevis är direkt och betydligt kortare och enklare än beviset på [1]. För att bevisa Theorem 2.1, arbetar vi först med bipartite nätverk G = (V, E) där V = S  på R, S på R = ∅, och det finns ingen kant mellan två noder av S, eller mellan två noder av R. Vi kallar noderna i S avsändare och noderna i R mottagare. Vi visar följande teorem om tvåpartsradionät. Det här är Lemma 2.2. Det finns en bipartite nätverk H med mindre än n noder sådan att i varje runda, oavsett vilka noder överföra, högst O( 1 log n ) mottagare får ett paket.
Ghaffari m.fl. REF visade en lägre gräns för  en (k log n) för detta problem, även när nätverkskodning är tillåten, som håller även för centraliserade algoritmer.
A Bound on the Throughput of Radio Networks
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}