Skip to main content
Erschienen in: Designs, Codes and Cryptography 1/2017

14.05.2016

Asynchronous channel hopping systems from difference sets

verfasst von: Xiaotian Chen, Yue Zhou

Erschienen in: Designs, Codes and Cryptography | Ausgabe 1/2017

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In cognitive radio networks, the process for any two unlicensed (secondary) users (SU) to establish links through a common channel is called a rendezvous. It is hard to employ a common control channel to solve the rendezvous problem, because of the bottleneck of the single control channel. Asynchronous channels hopping (ACH) systems have been proposed and investigated to guarantee rendezvous without requirement of global synchronization and common control channels. An ACH system with N channels can be mathematically interpreted as a set of sequences of the same period T on the alphabet \(\{0,1,\ldots , N-1\}\) satisfying certain rotation closure properties. For each \(l\in \{0,1,\ldots , T-1 \}\), each \(j\in \{0,1,\ldots , N-1 \}\) and any two distinct sequences \(\mathbf u\), \(\mathbf v\) in an ACH system H, if there always exists i such that the i-th entries of \(\mathbf u\) and \(L^{l}(\mathbf v)\) are both identical to j where \(L^{l}(\mathbf v)\) denotes the cyclic shift of \(\mathbf v\) by l, then H is called a complete ACH system, which guarantees rendezvous between any two SUs who share at least one common channel. In this paper, we prove some properties of such systems. Moreover, we investigate the complete ACH systems, in each of which all SUs repeat the same (global) sequence associated with the system. One challenging research problem is to construct such ACH systems of period \(T=\beta N^2 + o(N^2)\) such that \(\beta \) is as small as possible. By applying mathematical tools such as group rings and (relative, relaxed) difference sets from combinatorial design theory, we obtain two constructions of them in which \(\beta =1,2\) respectively. Finally, we also present a simple and powerful approach to combining known ACH systems to produce new ones.
Literatur
1.
Zurück zum Zitat Baumert L.D.: Cyclic Difference Sets. Springer, Berlin (1971). Baumert L.D.: Cyclic Difference Sets. Springer, Berlin (1971).
2.
Zurück zum Zitat Beth T., Jungnickel D., Lenz H.: Design Theory. Vol. I. f Encyclopedia of Mathematics and Its Applications, vol. 69, 2nd edn. Cambridge University Press, Cambridge (1999). Beth T., Jungnickel D., Lenz H.: Design Theory. Vol. I. f Encyclopedia of Mathematics and Its Applications, vol. 69, 2nd edn. Cambridge University Press, Cambridge (1999).
3.
Zurück zum Zitat Bian K., Park J.-M.: Asynchronous channel hopping for establishing rendezvous in cognitive radio networks. In: 2011 Proceedings IEEE INFOCOM, pp. 236–240 (2011). Bian K., Park J.-M.: Asynchronous channel hopping for establishing rendezvous in cognitive radio networks. In: 2011 Proceedings IEEE INFOCOM, pp. 236–240 (2011).
4.
Zurück zum Zitat Bian K., Park J.-M.: Maximizing rendezvous diversity in rendezvous protocols for decentralized cognitive radio networks. IEEE Trans. Mob. Comput. 12(7), 1294–1307 (2013). Bian K., Park J.-M.: Maximizing rendezvous diversity in rendezvous protocols for decentralized cognitive radio networks. IEEE Trans. Mob. Comput. 12(7), 1294–1307 (2013).
5.
Zurück zum Zitat Bose R.C.: An affine analogue of Singer’s theorem. J. Indian Math. Soc. (N.S.) 6, 1–15 (1942). Bose R.C.: An affine analogue of Singer’s theorem. J. Indian Math. Soc. (N.S.) 6, 1–15 (1942).
6.
Zurück zum Zitat Bosma W., Cannon J., Playoust C.: The MAGMA algebra system I: the user language. J. Symb. Comput. 24(3–4), 235–265 (1997). Bosma W., Cannon J., Playoust C.: The MAGMA algebra system I: the user language. J. Symb. Comput. 24(3–4), 235–265 (1997).
7.
Zurück zum Zitat Chuang I.-H., Wu H.-Y., Kuo Y.-H.: A fast blind rendezvous method by alternate hop-and-wait channel hopping in cognitive radio networks. IEEE Trans. Mob. Comput. 13(10), 2171–2184 (2014). Chuang I.-H., Wu H.-Y., Kuo Y.-H.: A fast blind rendezvous method by alternate hop-and-wait channel hopping in cognitive radio networks. IEEE Trans. Mob. Comput. 13(10), 2171–2184 (2014).
8.
Zurück zum Zitat Ćustić A., Krčadinac V., Zhou Y.: Tiling groups with difference sets. Electron. J. Comb. 22(2), P2.56 (2015). Ćustić A., Krčadinac V., Zhou Y.: Tiling groups with difference sets. Electron. J. Comb. 22(2), P2.56 (2015).
9.
Zurück zum Zitat Davis J.A., Jedwab J.: A unifying construction for difference sets. J. Comb. Theory, Series A 80(1), 13–78 (1997). Davis J.A., Jedwab J.: A unifying construction for difference sets. J. Comb. Theory, Series A 80(1), 13–78 (1997).
10.
Zurück zum Zitat Elliott J.E.H., Butson A.T.: Relative difference sets. Ill. J. Math. 10, 517–531 (1966). Elliott J.E.H., Butson A.T.: Relative difference sets. Ill. J. Math. 10, 517–531 (1966).
11.
Zurück zum Zitat Gu Z., Hua Q.S., Wang Y., Lau F: Nearly optimal asynchronous blind rendezvous algorithm for cognitive radio networks. In: 2013 10th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON), pp. 371–379 (2013). Gu Z., Hua Q.S., Wang Y., Lau F: Nearly optimal asynchronous blind rendezvous algorithm for cognitive radio networks. In: 2013 10th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON), pp. 371–379 (2013).
12.
Zurück zum Zitat Hiramine Y.: On (2n,2,2n,n) relative difference sets. J. Comb. Theory Ser. A 101(2), 281–284 (2003). Hiramine Y.: On (2n,2,2n,n) relative difference sets. J. Comb. Theory Ser. A 101(2), 281–284 (2003).
13.
Zurück zum Zitat Hungerford T.W.: Algebra. Springer, New York (2012). Hungerford T.W.: Algebra. Springer, New York (2012).
14.
Zurück zum Zitat Jia J., Zhang Q., Shen X.: HC-MAC: A hardware-constrained cognitive MAC for efficient spectrum management. IEEE J. Select. Areas Commun. 26(1), 106–117 (2008). Jia J., Zhang Q., Shen X.: HC-MAC: A hardware-constrained cognitive MAC for efficient spectrum management. IEEE J. Select. Areas Commun. 26(1), 106–117 (2008).
15.
Zurück zum Zitat Jiang J.R., Tseng Y.C., Hsu C.S., Lai T.H: Quorum-based asynchronous power-saving protocols for IEEE 802.11 ad hoc networks. In: Proceedings of the 2003 International Conference on Parallel Processing, pp. 257–264 (2003). Jiang J.R., Tseng Y.C., Hsu C.S., Lai T.H: Quorum-based asynchronous power-saving protocols for IEEE 802.11 ad hoc networks. In: Proceedings of the 2003 International Conference on Parallel Processing, pp. 257–264 (2003).
16.
Zurück zum Zitat Jungnickel D.: Finite Fields: Structure and Arithmetics. B.T. Wissenschaftsverlag, Mannheim (1993). Jungnickel D.: Finite Fields: Structure and Arithmetics. B.T. Wissenschaftsverlag, Mannheim (1993).
17.
Zurück zum Zitat Jungnickel D., Pott A: Perfect and almost perfect sequences. Discret. Appl. Math. 95, 331–359 (1999). Jungnickel D., Pott A: Perfect and almost perfect sequences. Discret. Appl. Math. 95, 331–359 (1999).
18.
Zurück zum Zitat Jungnickel D., Schmidt B: Difference sets: an update. In: Geometry, Combinatorial Designs and Related Structures (Spetses, 1996), London Mathematical Society. Lecture Note Series, vol. 245, pp. 89–112. Cambridge University Press, Cambridge (1997). Jungnickel D., Schmidt B: Difference sets: an update. In: Geometry, Combinatorial Designs and Related Structures (Spetses, 1996), London Mathematical Society. Lecture Note Series, vol. 245, pp. 89–112. Cambridge University Press, Cambridge (1997).
19.
Zurück zum Zitat Jungnickel D., Schmidt B: Difference sets: a second update. Rendiconti del Circolo Matematico di Palermo. Serie II. Supplemento. 53, 89-118 (1998). Jungnickel D., Schmidt B: Difference sets: a second update. Rendiconti del Circolo Matematico di Palermo. Serie II. Supplemento. 53, 89-118 (1998).
20.
Zurück zum Zitat Kondareddy Y., Agrawal P., Sivalingam K: Cognitive radio network setup without a common control channel. In: IEEE Military Communications Conference, 2008 (MILCOM 2008), pp. 1–6 (2008). Kondareddy Y., Agrawal P., Sivalingam K: Cognitive radio network setup without a common control channel. In: IEEE Military Communications Conference, 2008 (MILCOM 2008), pp. 1–6 (2008).
21.
Zurück zum Zitat Lander E.S.: Symmetric Designs: An Algebraic Approach. Cambridge University Press, Cambridge (1983). Lander E.S.: Symmetric Designs: An Algebraic Approach. Cambridge University Press, Cambridge (1983).
22.
Zurück zum Zitat Lidl R., Niederreiter H.: Finite Fields. Encyclopedia of Mathematics and Its Applications, vol. 20, 2nd edn. Cambridge University Press, Cambridge (1997). Lidl R., Niederreiter H.: Finite Fields. Encyclopedia of Mathematics and Its Applications, vol. 20, 2nd edn. Cambridge University Press, Cambridge (1997).
23.
Zurück zum Zitat Liu H., Lin Z., Chu X., Leung Y.W.: Jump-stay rendezvous algorithm for cognitive radio networks. IEEE Trans. Parallel Distrib. Syst. 23(10), 1867–1881 (2012). Liu H., Lin Z., Chu X., Leung Y.W.: Jump-stay rendezvous algorithm for cognitive radio networks. IEEE Trans. Parallel Distrib. Syst. 23(10), 1867–1881 (2012).
24.
Zurück zum Zitat Luk W.S., Wong T.T: Two new quorum based algorithms for distributed mutual exclusion. In: Proceedings of the 17th International Conference on Distributed Computing Systems, pp. 100–106 (1997). Luk W.S., Wong T.T: Two new quorum based algorithms for distributed mutual exclusion. In: Proceedings of the 17th International Conference on Distributed Computing Systems, pp. 100–106 (1997).
25.
Zurück zum Zitat Ma L., Han X., Shen C.C: Dynamic open spectrum sharing MAC protocol for wireless ad hoc networks. In: 2005 First IEEE International Symposium on New Frontiers in Dynamic Spectrum Access Networks (DySPAN 2005), pp. 203–213 (2005). Ma L., Han X., Shen C.C: Dynamic open spectrum sharing MAC protocol for wireless ad hoc networks. In: 2005 First IEEE International Symposium on New Frontiers in Dynamic Spectrum Access Networks (DySPAN 2005), pp. 203–213 (2005).
26.
Zurück zum Zitat Ma S.L., Schmidt B.: On \((p^a, p, p^a, p^{a-1})\)-relative difference sets. Des. Codes Cryptogr. 6(1), 57–71 (1995). Ma S.L., Schmidt B.: On \((p^a, p, p^a, p^{a-1})\)-relative difference sets. Des. Codes Cryptogr. 6(1), 57–71 (1995).
27.
Zurück zum Zitat Mullen G.L., Panario D.: Handbook of Finite Fields. Chapman and Hall/CRC, Boca Raton (2013). Mullen G.L., Panario D.: Handbook of Finite Fields. Chapman and Hall/CRC, Boca Raton (2013).
28.
Zurück zum Zitat Perez-Romero J., Sallent O., Agusti R., Giupponi L: A novel on-demand cognitive pilot channel enabling dynamic spectrum allocation. In: 2nd IEEE International Symposium on New Frontiers in Dynamic Spectrum Access Networks (DySPAN 2007), pp. 46–54 (2007). Perez-Romero J., Sallent O., Agusti R., Giupponi L: A novel on-demand cognitive pilot channel enabling dynamic spectrum allocation. In: 2nd IEEE International Symposium on New Frontiers in Dynamic Spectrum Access Networks (DySPAN 2007), pp. 46–54 (2007).
29.
Zurück zum Zitat Pott A.: Finite geometry and character theory. Lecture Notes in Mathematics, vol. 1601. Springer, Berlin (1995). Pott A.: Finite geometry and character theory. Lecture Notes in Mathematics, vol. 1601. Springer, Berlin (1995).
30.
Zurück zum Zitat Pott A., Wang Q., Zhou Y.: Sequences and functions derived from projective planes and their difference sets. In: Özbudak F., Rodríguez-Henríque, F. (eds.) Arithmetic of Finite Fields. Lecture Notes in Computer Science, vol. 7369, pp. 64–80. Springer, Berlin (2012). Pott A., Wang Q., Zhou Y.: Sequences and functions derived from projective planes and their difference sets. In: Özbudak F., Rodríguez-Henríque, F. (eds.) Arithmetic of Finite Fields. Lecture Notes in Computer Science, vol. 7369, pp. 64–80. Springer, Berlin (2012).
31.
Zurück zum Zitat Schmidt B.: Cyclotomic integers and finite geometry. J. Am. Math. Soc. 12(4), 929–952 (1999). Schmidt B.: Cyclotomic integers and finite geometry. J. Am. Math. Soc. 12(4), 929–952 (1999).
32.
Zurück zum Zitat Schmidt K.U., Zhou Y.: Planar functions over fields of characteristic two. J. Algebraic Comb. 40(2), 503–526 (2014). Schmidt K.U., Zhou Y.: Planar functions over fields of characteristic two. J. Algebraic Comb. 40(2), 503–526 (2014).
33.
Zurück zum Zitat Shin J., Yang D., Kim C.: A channel rendezvous scheme for cognitive radio networks. IEEE Commun. Lett. 14(10), 954–956 (2010). Shin J., Yang D., Kim C.: A channel rendezvous scheme for cognitive radio networks. IEEE Commun. Lett. 14(10), 954–956 (2010).
34.
Zurück zum Zitat Theis N., Thomas R., DaSilva L.: Rendezvous for cognitive radios. IEEE Trans. Mob. Comput. 10(2), 216–227 (2011). Theis N., Thomas R., DaSilva L.: Rendezvous for cognitive radios. IEEE Trans. Mob. Comput. 10(2), 216–227 (2011).
35.
Zurück zum Zitat Wu K., Han F., Han F., Kong D: Rendezvous sequence construction in cognitive radio ad-hoc networks based on difference sets. In: 2013 IEEE 24th International Symposium on Personal Indoor and Mobile Radio Communications (PIMRC), pp. 1840–1845 (2013). Wu K., Han F., Han F., Kong D: Rendezvous sequence construction in cognitive radio ad-hoc networks based on difference sets. In: 2013 IEEE 24th International Symposium on Personal Indoor and Mobile Radio Communications (PIMRC), pp. 1840–1845 (2013).
36.
Zurück zum Zitat Xiang Q.: Recent progress in algebraic design theory. Finite Fields Their Appl. 11(3), 622–653 (2005). Xiang Q.: Recent progress in algebraic design theory. Finite Fields Their Appl. 11(3), 622–653 (2005).
Metadaten
Titel
Asynchronous channel hopping systems from difference sets
verfasst von
Xiaotian Chen
Yue Zhou
Publikationsdatum
14.05.2016
Verlag
Springer US
Erschienen in
Designs, Codes and Cryptography / Ausgabe 1/2017
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-016-0221-8

Weitere Artikel der Ausgabe 1/2017

Designs, Codes and Cryptography 1/2017 Zur Ausgabe