Interconnection algorithm of a wide range of pervasive devices for the Internet of things

Abstract

With the rapid development of wireless communications for network of things, more and more models for such networks-on-chip architectures have been created and used in a wide range of applications. In this article, the behaviors of wireless communications for such networks-on-chip architectures are analyzed at two layers. The physical layer behaviors consist of what frequency is used, how and when signals are transmitted, and how transceivers’ responses are decoded. The medium access control layer behavior consists of how to provide a reliable link between two peer medium access control entities. For the optimization objective of each layer, the specific problems surrounding the design of combined radio frequency identification/Bluetooth/Wi-Fi chips are considered at their respective layer, and then, corresponding optimization methods are carried out. The problem of optimization is defined as a linear programming problem in which each active transceiver is assigned to a channel on condition that all the constraint is met on every link. Each optimization procedure proposed in this article is performed through the adaptation of its objective, from each one of these layers, in order to minimize interference previously specified. In principle, the optimization can be made layer by layer separately. The optimization criteria consist of a specification of the behaviors of wireless communications (radio frequency identification, Bluetooth, Wi-Fi) and a set of constraints and goals. Our approach is to perform it independently within the given task, where the given task can be achieved with its sequencing graph entities, including automate selection, binding, and scheduling. We have implemented our algorithms on a field-programmable gate array and applied them to some off-the-shelf products. This methodology looks promising, not only for the results presented and obtained through computer simulations but also for its generality concerning to the kind of wireless network system used. Therefore, such methodology is expandable either to multi-core networks-on-chip architecture or also to the off-the-shelf products.

Introduction

According to EPS (U.S. Environmental Protection Agency), the high-speed advance in low-power design of data centers has led the wide design of a multi-core chip. An increasing number of new wireless products are quickly adding multi-cores on a chip for multiple wireless connectivities in order to provide a broad range of services and applications. One of the key challenges in the widespread adoption of such multi-core chips is the need for high performance, robustness, and non-interference. How to achieve these goals for the best performance can be a very hard problem, in particular, the overall communication architecture. In the work, Pande et al.^1,2 proposed a networks-on-chip (NoC) paradigm, which utilizes a communication backbone through massively integrated computing in multi-core system-on-chips. Shacham et al. ³ first elaborated a multiprocessors chip for a photonic NoC. Similarly, Joshi et al. ⁴ proposed a complete photonic NoC, which generates four representative components from the vertices of integration as a single silicon chip. Meanwhile, when the number of cores on a chip is increasing, especially different communication cores on one chip, interference problems such as in frequency domain and in time domain will be significantly aggravated. Such wireless multi-core NoC architectures have enormous potential for optimization and synthesis, but none of the obtained synthesis modes can be directly used in the current specified NoC products. However, conventional frequency planning used only one kind of mutual interference for describing each channel state of the NoC, which leads to the weak representation and high computation power. Therefore, conventional frequency planning cannot be used for such heterogeneous NoC architecture. The goal of this article is to present a multilayer optimization approach for wireless multi-core NoC architectures. In our optimization solutions, there exist some different approaches to optimization. Several of the optimization algorithms consider multilayer issues, in respect to both higher and lower layers. Joint scheduling with medium access control (MAC) control is an example. So far, most optimization algorithms have been designed to give an acceptable solution for a specified chip.

Unlike wired communications, the transmission medium for wireless signals is unreliable, with a low-bandwidth and broadcast feature. Due to the fact that changing frequency continuously is an important feature in wireless communications, our optimization is based on multilayer optimization. Each one of these layers represents the optimization tasks performed by each layers such as physical (PHY) layer and MAC layer. Each optimization procedure proposed in this article is performed through the adaptation of its objective, from each one of these layers, in order to minimize interference previously specified. In principle, the optimization can be made layer by layer separately. In the process of optimization for each layer, we will go further into the specific problems that have been chosen to characterize the key issue at each layer. The study focuses on the optimization for the specific multi-cores-on-chip (a combined radio frequency identification (RFID)/Bluetooth (BT)/Wi-Fi cores) where different kinds of transceivers communicate in different ways using different protocols. Our optimization criteria consist of a specification of the behaviors of wireless communications (RFID, BT, Wi-Fi) and a set of constraints and goals. Our approach is to perform it independently within the given task, which the given task can be achieved with its sequencing graph entity including automate selection, binding, and scheduling.

In order to optimize such wireless multi-core products, the multilayer optimization model shown in Table 1 should be optimally implemented. The goal of our multilayer design was building a solution to optimize wireless communications in such NoC architectures, rather than designing a new standard or validating an existing one.

Table 1.

The PHY/MAC optimization model for wireless multi-core NoC architectures.

IEEE 802.11/ISO 18000 Standards			Optimized object
RFIDMAC	802.11bMAC	BTMAC	Logical link controller
RFIDPHY	802.11bPHY	BTPHY	Physical RF channel

PHY: physical; MAC: medium access control; NoC: network-on-chip; RFID: radio frequency identification; BT: Bluetooth.

To study the behavior of wireless communications for NoC architectures, the specific problems surrounding the design of combined RFID/BT/Wi-Fi chips are addressed at their respective layer level and then corresponding algorithms are presented to settle these problems. First, we analyze the minimum interference frequency assignment problem at radio frequency (RF) PHY layer. Assume that transmission rages are limited, and beyond this no interference is caused. This allows the problem to be transformed into a graph-theoretical problem, that is, a physical channel is represented as a directed graph described in the next section. In order to determine how much spacing on the frequency should be assigned for all the different kinds of transceivers at the same time when they work together, a dynamic channel allocation algorithm by minimizing channel interference between different transceivers is described in detail. In addition, the simulations were carried out with certain realistic scenarios consisting of the RFID, BT, and Wi-Fi transceivers forming a hybrid radio network.

Second, we discuss the reliable link between two peer MAC entities problem at the MAC layer. Although our model is more realistic, it is even more complex and is based on the physical interference model, using the signal-to-interference ratio (SIR). In our work, only when the received power is sufficient compared to the noise and all interfering signals (from simultaneously transmitting transceivers), a link can be constructed. Using this model, scheduling can be transformed into the selection of the links in a graph, which can be solved with an additional heuristic strategy–joint time slot assignment algorithm.^5–7 This model thereby makes it simple to create a time slot assignment with a minimum scheduler for multilink network. And then, a comparison under the assumption of traffic sensitivity will be studied, and a different result can show that link assignment can achieve higher throughout than random selection for scheduling.

Our NoC architecture is the on-chip communication infrastructure comprising the PHY layer, the data link layer, and the network layer of protocol stack. We have implemented our algorithms on a field-programmable gate array (FPGA) and applied it to some off-the-shelf products. This methodology looks promising, not only for the results presented and obtained through computer simulations but also for its generality concerning to the kind of wireless network system used. Therefore, such methodology is expandable either to multi-core NoCs architecture or also to the off-the-shelf products.

In the context of optimization approach for wireless multi-core NoC architectures, we have developed several models and algorithms to improve the network performance. One of our contributions is a channel interference quantity, which denotes the amount of interference of overlapping channels for the multi-cores (RFID, BT, Wi-Fi) hybrid wireless communication infrastructure. The other of our contributions is a linear programming–based channel allocation algorithm, which preserves the channel features of such NoC architecture by minimizing channel interference. Second, a time slot assignment with a minimum scheduler model is presented for multilink shared channel in such multi-core NoC architectures, and the optimization model is solved by an additional heuristic strategy–joint time slot assignment algorithm.

The remainder of this article is organized as follows. In the next section, a RF channel assignment with minimum interference for PHY channel layer is given. In section “Time slot assignment with a minimum scheduler at the MAC layer,” a time slot assignment with minimum scheduler for MAC layer problem is given. In section “FPGA-based solutions,” two FPGA-based solutions are presented. We draw conclusion in section “Conclusion and future work.”

RF channel assignment with minimum interference at the PHY channel layer

When there exist several cores for wireless communication such as RFID core, BT core, and/or Wi-Fi core on one chip, the need for coexistence of such transceivers with different protocols leads to much more complexity in the frequency assignment. From the available number of frequencies and exactly one frequency assigned to one transceiver, significant there is a high probability that interference may occur between two transceivers in the same channel or adjacent one. To avoid intolerable interference, a minimum carrier separation between the transceivers with different protocols within the same chip is studied in this section. First, we present a minimum interference frequency assignment problem to assign optimal channels to each transceiver on one chip while maintaining overall performance of radio network and to provide some ideas about which properties that are important when we design a multi-core NoC chip. Second, we will propose a dynamic channel allocation solution to solve the specific problem mentioned above. We will also describe a dynamic channel allocation algorithm by minimizing channel interference between transceivers in multi-core communication scenarios. Our algorithm assigns channels in a way that minimizes overlapping channel interference resulting in higher throughput. Finally, the simulations were carried out with certain realistic scenarios consisting of RFID, BT, and Wi-Fi transceivers forming a hybrid radio network.

Minimum interference frequency assignment problem

Although the RFID, BT, and Wi-Fi transceivers transmit/receive in different ways using different protocols, there remain the same parameters qualifying the transceivers, that is, transmit power, receiver sensitivity, and receiver selection. Therefore, the interference can occur when all the transceivers operate in the same frequency. Due to different design requirements for RFID transceiver, BT transceiver, or Wi-Fi transceiver, it is necessary to imply different frequency separation that allow for good performance even in the presence of the interference. For example, in the RFID system, interrogators need to transmit more output power of a radio since they both power up and communicate with tags within their range. These signals from the interrogator are often reflected against the receiver antenna of BT or Wi-Fi and will lead to a noise or interference to a receiver of BT or Wi-Fi. Strong interference could even make them lose connectivity. In order to reject power from the RFID transceiver, a minimum carrier spacing on frequencies is considered in this section.

The minimum interference frequency assignment can be stated as follows:

Definition 1

A channel graph is a physical channel which can be assigned to each transceiver (RFID transceiver, BT transceiver, or Wi-Fi transceiver). This graph can be defined as a weighted directed acyclic graph, $G_{\mathrm{channel}}=(V_{\mathrm{frequency}},E_{\mathrm{frequency}})$ consisting of a set of nodes among which there are some relationships. A node in the channel graph represents channel’s frequency parameters such as central frequency and bandwidth. The edges in the channel graph define some relationships, that is, overlapping and spacing on frequencies.

Definition 2

A transceiver graph is a weighted directed graph, $G_{\mathrm{transceiver}}=(V_{\mathrm{transceiver}},E_{\mathrm{transceiver}})$ with each vertex $v_{\mathrm{transceive}{r}_i}\in V$ representing a transceiver of RFID, BT, or Wi-Fi. The directed edge $(v_{\mathrm{transceive}{r}_i},v_{\mathrm{transceive}{r}_j})$ , denoted as $e_{\mathrm{transceive}{r}_{\mathrm{ij}}}\in E$ , represents the interference between the transceiver $v_{\mathrm{transceive}{r}_i}$ and $v_{\mathrm{transceive}{r}_j}$ , that is, between RFID transceiver and BT transceiver, or between RFID transceiver and Wi-Fi transceiver, or between Wi-Fi transceiver and BT transceiver. The weight of the edge $e_{\mathrm{transceive}{r}_{\mathrm{ij}}}$ represents the average interference from $v_{\mathrm{transceive}{r}_i}$ to $v_{\mathrm{transceive}{r}_j}$ and receiver selection of their respective transceivers.

Definition 3

A mapping graph is a directed graph, $G_{\mathrm{map}}=(V_{\mathrm{map}},E_{\mathrm{map}})$ with a set of mapping edges $E_{\mathrm{map}}$ between $G_{\mathrm{channel}}=(V_{\mathrm{frequency}},E_{\mathrm{frequency}})$ and $G_{\mathrm{transceiver}}=(V_{\mathrm{transceiver}},E_{\mathrm{transceiver}})$ . In particular, $V_{\mathrm{map}}=V_{\mathrm{frequency}}\cup V_{\mathrm{transceiver}}$ , $E_{\mathrm{map}}=E_{\mathrm{frequency}}\cup E_{\mathrm{transceiver}}\cup E_{\mathrm{map}}$ , and $E_{\mathrm{map}}=V_{\mathrm{frequency}}\times V_{\mathrm{transceiver}}$ for satisfying some constraints.

In order to describe a concrete mapping, the term activation nodes and edges of a mapping graph is defined. Based on the definition, allocation, binding, and scheduling will be defined as follows.

Definition 4

The activation of a mapping graph $G_{\mathrm{map}}=(V_{\mathrm{map}},E_{\mathrm{map}})$ is a function $\alpha :V_{\mathrm{map}}\cup E_{\mathrm{map}}\to 0,1$ that assigns to each edge $e\in E_{\mathrm{map}}$ and each node $v\in V_{\mathrm{map}}$ the value 1 (activated) or 0 (not activated).

Definition 5

An allocation $\alpha$ of a mapping graph is the subset of all activated nodes and edges of the dependence graphs, that is, $\alpha ={\alpha }_V\cup {\alpha }_E$ , ${\alpha }_V=v\in V_{\mathrm{map}}|\alpha (v)=1$ , ${\alpha }_E=e\in E_{\mathrm{map}}|\alpha (e)=1$ .

Definition 6

A binding $\beta$ is the subset of all activated mapping edges, that is, $\beta =e\in E_{\mathrm{map}}|\alpha (e)=1$ .

Definition 7

Given a mapping graph $G_{\mathrm{map}}$ and an allocation $\alpha$ , a feasible binding $\beta$ is a binding that satisfies the following criteria: (1) each activated edge $\rho \in \beta$ starts and ends at an activated node and (2) for each activated node $v\in {\alpha }_V$ with $v\in V_{\mathrm{frequency}}\cup V_{\mathrm{transceiver}}$ exactly one outgoing edge $e\in E_{\mathrm{map}}$ is activated.

Given a mapping graph $G_{\mathrm{map}}$ , a feasible binding $\beta$ , separation requirements for each pair of transceivers, the physical channel assignment with minimum interference for RFID transceiver, BT transceiver, or Wi-Fi transceiver is to assign exactly one frequency to each transceiver such that no requirements are violated, and the total cumulative interference is minimized.

Minimize $g(\alpha ,\beta ,\tau )$ subject to $\alpha$ is a feasible allocation, $\beta$ is a feasible binding, $\tau$ is a schedule, $g_i(\alpha ,\beta ,\tau )\ge 0,\forall i\in 1,2,...$

The physical channel assignment involves three sub-problems: selection of appropriate channel, binding and scheduling of the transceivers, and the performance evaluation. Our approach is an iteration loop of three steps, and the optimization objective is to minimize the total cumulative interference, while still providing the required radio network performance.

Solution method for minimum interference frequency assignment problem

The physical channel assignment problem belongs to the class of nondeterministic polynomial time (NP)-complete problem, which means that the problem probably cannot be solved in polynomial time. There exist two major approaches to deal with this problem in radio network: fixed channel assignment (FCA) and dynamic channel assignment (DCA). In the following, we concentrate on the solution methods for DCA. There exist several version of DCA, that is, the asymptotic bounds model for DCA, ⁸ using neural networks in DCA, ⁹ based on the SIR for DCA ¹⁰ and an integer linear programming for DCA. ¹¹

The simple way to settle the NP-complete problems is to apply different heuristic methods. Our heuristic approach is a dynamic channel allocation algorithm by minimizing channel interference between transceivers, based on the iteration with the objective to minimize overlapping channel interference, which means that channel should be assigned to the transceivers such that overlapping channel interference is minimized. The overlapping channel may be assigned to two transceivers if the overlapping channel interference signal detected by each transceiver is less than a given threshold. Since use of overlapping channels degrades network throughput, overlapping channels assigned to the transceivers must be chosen carefully.

To quantify the channel interference, an overlapping channel interference factor, ${\omega }_{\mathrm{ij}}$ , is defined as the relative percentage increase in interference

$${\omega }_{\mathrm{ij}}=\{\begin{array}{cc}1-|G_{\mathrm{channe}{l}_i}-G_{\mathrm{channe}{l}_j}|\times \epsilon \hfill & \begin{array}{cc}\mathrm{if}\hfill & {\omega }_{\mathrm{ij}}\ge 0\hfill \end{array}\hfill \\ \multicolumn{1}{c}{0}& \mathrm{otherwise}\hfill \end{array}$$

(1)

where $G_{\mathrm{channe}{l}_i}$ shown in definition 1 is the channel assigned to the transceiver _i and $\epsilon$ is the overlapping channel factor. For example, assumed that 5 is the maximum number of overlapping channels in 802.11b/g, $\epsilon$ is 1/5; In BT, $\epsilon$ is 1/6 where 6 is the maximum number of overlapping channels; in RFID, $\epsilon$ is 1/10 where 10 is the maximum number of overlapping channels.

Using an overlapping channel interference factor as heuristic conditions, our DCA can be formulated as follows

$$\begin{array}{cc}\underset{\mathrm{Interference}}{min}\hfill & g(\alpha ,\beta ,\tau )\hfill \end{array}\ge 0$$

(2)

$$\begin{array}{cc}s.t.\hfill & \mathrm{Interferenc}{e}_{\mathrm{ij}}=\frac{{\omega }_{\mathrm{ij}}{P}_j}{\mathrm{Pathloss}(d_{\mathrm{ij}},m)}\hfill \end{array}$$

(3)

$$\begin{array}{cc}s.t.\hfill & {\omega }_{\mathrm{ij}}=\{\begin{array}{cc}1-|G_{\mathrm{channe}{l}_i}-G_{\mathrm{channe}{l}_j}|\times \epsilon \hfill & \mathrm{if}{\omega }_{\mathrm{ij}}\ge 0\hfill \\ \multicolumn{1}{c}{0}& \mathrm{otherwise}\hfill \end{array}\hfill \end{array}$$

(4)

Objective (2) minimizes the total interference at each transceiver. Constraint (3) defines the interferences between transceiver _i and transceiver _j . Constraint (4) defines the overlapping channel interference factor between transceiver _i and transceiver _j , which have been assigned channels $G_{\mathrm{channe}{l}_i}$ and $G_{\mathrm{channe}{l}_j}$ , respectively. Each transceiver would periodically (or when the amount of interference is above a threshold) run the above given DCA. Each transceiver would in turn pick its own channel that would minimize that amount of interference it receives from its neighbors. As long as one transceiver changes its own channel, it would impact the interference on the neighboring transceivers.

Principle of allocation strategy

The proposed approach begins with the allocation strategy, which selects a set of activated transceivers (on working) from a transceiver graph.

This step is critical since computational results for the physical channel assignment are different when selecting different transceivers. To achieve the minimum interference frequency assignment, one has to address the question as how to handle infeasible allocation. Obviously, if allocations may be randomly chosen, a lot of them can be infeasible. These considerations have led to the following strategy: in each mode, the given channel has several candidates (different transceivers) with priority features, which can be expressed by an allocation priority list (APL). The randomly generated allocations can be revised using an allocation with APL algorithm (see Algorithm 1).

Algorithm 1.

An allocation algorithm with APL.

Require: A MMS with an Allocation Priority List (APL)Ensure: The allocation $\alpha$  1:   $\alpha \leftarrow \{\}$  2:  for each node v in MMS do 3:   if $\alpha \left[\tilde{v}\right]=1$ then 4:     $\alpha \leftarrow \alpha \cup \left\{\tilde{v}\right\}$  5:   end if 6:  end for 7:  for each $v_{\mathrm{frequenc}{y}_i}$ in $V_{\mathrm{frequency}}$ do 8:   calculate $\mathrm{Interferenc}{e}_{\mathrm{ij}}$ and ${\omega }_{\mathrm{ij}}$  9:   order by $\sum \mathrm{Interferenc}{e}_{\mathrm{ij}}$ 10:   put $v_{\mathrm{frequency}}$ into set $\mathrm{indable}(\alpha )$ 11: end for12:   $V_{\alpha }\leftarrow \mathrm{indable}(\alpha )$ 13:   $v\leftarrow \mathrm{APL}[0]$ 14:  while $V_{\alpha }\ne \mathrm{NULL}$ do15:  if $V_{\alpha }\ne \mathrm{indable}(\alpha \cup \left\{v\right\})$ then16:     $\alpha \leftarrow \alpha \cup \left\{v\right\}$ , $V_{\alpha }\leftarrow \mathrm{indable}(\alpha )$ 17:  end if18:    $v\leftarrow \mathrm{APL}[i+1]$ 19:  end while20:  return $\alpha$

Note that an APL can be obtained according to $\mathrm{Interferenc}{e}_{\mathrm{ij}}$ and ${\omega }_{\mathrm{ij}}$ , a different APL may result in a different allocation.

The binding algorithm bound on the initiation internals

The next step is to bind the channel graph to the selected transceivers. In order to minimize the time consumption of the System on Chip (SoC), simultaneous binding of the physical channels to the transceivers with different protocols, that is, RFID, BT, and Wi-Fi, is crucial in real-time application. Since the problems of binding and scheduling are correlated, our algorithms reflect the tight interdependency between them. The binding algorithm proceeds in an iteration for each allocated transceivers until all the transceivers’ constraints are met. Before the first iteration of the binding, the current allocation $\alpha$ is traversed. For each allocation transceivers, all precedence (used for the connected transceivers) constraints and resource constraints must be fulfilled, and all its successor (used for the connecting transceivers) constraints also must be met.

In our work, we realize that system synthesis intend to fail when allocations and binding are randomly chosen. Therefore, three grades of allocation granularity (RFID, BT, and Wi-Fi) are presented according to the time constraints of the given task and run-time behavior of the different cores.

Algorithm 2.

The binding algorithm with scheduled time.

Require: A MMS, a TG, and the allocation $\alpha$ Ensure: The binding $\beta$  1:   $\beta \leftarrow \{\}$  2:  for each $v_{\mathrm{transceiver}{s}_i}$ in $V_{\mathrm{transceiver}}$ do 3:   put $v_{\mathrm{transceive}{r}_i}$ into set TRANSCEIVERS 4: end for 5:  for each $v_{\mathrm{transceive}{r}_i}$ in set TRANSCEIVERS do 6:   while $v_{\mathrm{frequenc}{y}_i}\in V_{\mathrm{frequency}}$ do 7:    calculate $\mathrm{Interferenc}{e}_{\mathrm{ij}}$ and ${\omega }_{\mathrm{ij}}$  8:   order by $\sum \mathrm{Interferenc}{e}_{\mathrm{ij}}$  9:    put $v_{\mathrm{frequency}}$ into set $\alpha$ 10:   if $(v_{\mathrm{frequenc}{y}_i},v_{\mathrm{transceive}{r}_j})\in E_{\mathrm{map}}\cap \alpha$ then11:      $\mathrm{channe}{l}_i=(v_{\mathrm{frequenc}{y}_i},v_{\mathrm{transceive}{r}_j})$ 12:   end if13:    put $\mathrm{channe}{l}_i$ into set CHANNELS14:    updata $G_{\mathrm{channel}}$ , $V_{\mathrm{frequency}}$ 15:   end while16:  assign a transceiver to multi-channels in CHANNELS17:   put $(v_{\mathrm{frequency}},v_{\mathrm{transceiver}})$ into set $\beta$ 18:  end for19:  create frequency-set for all unused frequency20:  for each $\mathrm{channe}{l}_i$ in frequency-set do21:   if $(v_{\mathrm{frequenc}{y}_i},v_{\mathrm{transceiv}{e}_j})\in E_{\mathrm{map}}\cup \alpha$ then22:    put $(v_{\mathrm{frequenc}{y}_i},v_{\mathrm{transceive}{r}_j})$ into set $\beta$ 23:  end if24:   record start and end time of Binding25:  end for26:  return $\beta$

The performance evaluation step

The third step is the performance evaluation. For the performance evaluation of the multi-core wireless communication architecture, three comparison criteria are considered: (1) the number of simultaneous operating transceivers with different ways, (2) the complexity of frequency assignment, and (3) interference. Due to the simultaneous binding of local image segments in a fixed multi-core wireless communication architecture, the most important global constraint is minimum interference. Since each optimization goal depends on the given frequency, the object of the system is to reduce the overall interference. Therefore, the quality of each optimization can be evaluated as the number of the transceivers and the complexity of frequency assignment.

If no requirements are violated and the total cumulative interference is minimized, it can end the iteration. Otherwise, it restarts the iteration until all desired optimal points are selected.

Numerical results for physical channel assignment

The simulations were carried out with certain realistic scenarios consisting of the RFID, BT, and Wi-Fi transceivers forming a hybrid radio network. First, all the transceivers are assigned to co-channel or adjacent channel. Second, given the transmit power of the RFID transceiver, the BT transceiver, and the Wi-Fi transceiver, the receiver sensitivity threshold, the path-loss exponent, and the total interference caused on each transceiver from other transceivers in the hybrid radio network can be calculated. There are different types of the interference matrices used based on the frequency band, which are given in the form of transceiver to transceiver interferers. The interference matrices are $N\times N$ matrices, with N equals the number of transceivers in the network. Besides, the interference matrices are the co-channel interference matrix and the adjacent channel interference matrix, which are used as a benchmark to compare with our DCA algorithm.

The simulations were performed for 50 runs using our DCA algorithm while recording the interference and channel assignment for each run. The total interference is calculated in dBm for our algorithm and compared with benchmark interference matrix. The total interference ranges between −37 and −22 dBm for the DCA algorithm while all transceivers were assigned again. Figure 1 shows the results of total interference in dBm for the DCA compared to the random assignment.

Figure 1.

Total interference using the dynamic channel assignment algorithm comparing with random channel assignment.

Table 2 shows the channel assignment map for a hybrid radio network after running the DCA algorithm for 50 runs and the interference values in dBm for each transceiver after DCA. The algorithm converged to a unique solution under 13 iterations on average. This experiment shows how the transceivers can choose the channels by using the DCA.

Table 2.

Interference calculated at the transceivers after running dynamic channel assignment algorithm.

Transceiver type	Assignment results
	Frequency assignment (GHz)	Interference (dBm)	Lasting time (s)
RFID	2.471	–31.7856	31
RFID	2.445	–28.7621	28
RFID	2.4245	–23.6732	19
RFID	2.457	–27.0845	32
Bluetooth	2.407	–20.6549	17
Bluetooth	2.444	–27.0123	21
Bluetooth	2.439	–25.7921	23
Wi-Fi	2.452	–23.4335	219
Wi-Fi	2.422	–24.6164	225
Wi-Fi	2.462	–25.9625	432
Wi-Fi	2.437	–21.0332	543
Wi-Fi	2.412	–26.9548	523

RFID: radio frequency identification.

Time slot assignment with a minimum scheduler at the MAC layer

Since the wireless medium is inherently a shared resource, the role of a MAC protocol becomes a central theme that determines the fundamental capacity of the radio network and has a dramatic impact on system complexity and cost. In the MAC layer of radio network, communication is broadcasted over a logical network and there are several kinds of one-to-many network topologies between the physical channel and the logical channel. Examples of the technology at this level include activation/deactivation of the radio transceiver, link quality indicator for receiver packet and data transmissions. Especially, link controller is important to researchers as well as system designers. It is a strict barrier that cannot overcome by any means while maintaining a good network performance in such wireless multi-core NoC architectures. In the case of the Nordic nRF24LE1 product, the MultiCeiver^TM technology has been implemented to provide a one-to-many topological architecture as shown in Figure 2. MultiCeiver^TM contains a set of six parallel data pipes with unique addresses, and each data pipe is a logical channel (like a link) in the same physical RF channel (multilinks in one frequency channel). Using MultiCeiver^TM, up to six RF transceivers can communicate with one RF transceiver in one frequency channel. In such link-oriented assignment, a link is assigned one or several time slots for one-to-many communication. One of the key challenges in effectively link controller is the need for optimal assignment of the time slots between transceivers at run-time. How to assign the time slots such that the best overall network performance can be achieved is a very hard problem. It is up to the sophisticated designer to analyze the resource state and assign every time slot to all proper links. The scheduler is implemented as part of the MAC layer and there is a rich body of literatures on the packet-level stability of scheduling algorithms. We are interested in the throughput-optimal scheduling in radio networks when RFID, BT, and Wi-Fi cores exist in one chip.

Figure 2.

PRX using MultiCeiver^TM.

In this section, we first put forward the reliable link between two peer MAC entities problem for the wireless multi-core NoC architectures in data link layer, and then, we describe our model for multilink of the radio network considered. In essence, it is an interference-based model of the radio network, which consists of a number of radio links. Our model is more realistic and even more complex, which is based on the physical interference model, using the SIR. In this case, a link is assumed to be error-free if the received signal strength is sufficient compared with the noise and all interfering signals (from simultaneously transmitting transceivers). Using this model, scheduling can be transformed into the selection of the specific multilinks in a graph, which can be solved with a heuristic strategy–joint assignment algorithm. This model thereby makes it simple to create a time slot assignment with a minimum scheduler for multilink network. Finally, a comparison under the assumption of traffic sensitivity will be studied, and a different result can show that link assignment can achieve higher throughput than random selection for scheduling.

Our approach is purely link layer in the sense that it treats packets as opaque, not depending on the transmission control protocol (TCP) (or even Internet protocol (IP)) specification or implementation. In addition, our resulting MAC is based on master/slave transactions.

Minimum scheduler time slot assignment problem

The radio network mentioned consists of a number of radio links. Unlike a wired network’s topology, a radio network’s topology is a logical topology. If the received signal power from one radio unit is sufficient compared in relation to noise and interfering signal power in the radio network, it is assumed that any two radio units can communicate, that is, establish a link.

Definition 8

A radio network link is a directed acyclic graph $G_{\mathrm{link}}=(V_{\mathrm{transceiver}},A_{\mathrm{link}})$ , where the node set V represents the transceivers, and the arc set A represents the communication links, that is, $\mathrm{link}(i,j)$ representing a link from $\mathrm{transceive}{r}_i$ to $\mathrm{transceive}{r}_j$ . In the radio network, the communication link is also available when its signal-to-noise ratio (SNR) is greater or equal to a given threshold

$$\mathrm{SN}{R}_{i,j}=\frac{P_i·\mathrm{Gain}(i,j)}{N_r}\ge {\gamma }_{\mathrm{SNR}}$$

(5)

$P_i$ is the transmitting power of $\mathrm{transceive}{r}_i$ , $\mathrm{Gain}(i,j)$ is the link gain between $\mathrm{transceive}{r}_i$ and $\mathrm{transceive}{r}_j$ , $N_r$ is the noise power in the receiver, and $\gamma$ is the threshold.

For the link level, several assumptions are made as follows:

• All antennas are isotropic.

• The different kinds of transceivers, that is, RFID, BT, or Wi-Fi, use different transmission power and have different threshold.

• A transceiver cannot transmit and receive simultaneously.

• A primary transceiver can receive data from at most one secondary transceiver at any time.

• When there are multiple links simultaneously, the total interference value can be accumulated as follows

$$\mathrm{Tota}{l}_{\mathrm{Interference}(i,j)}=\sum _{k\in K,k\ne i}{P}_k·\mathrm{Gain}(k,j)$$

(6)

K is the set of links that are in simultaneous transmission. The term $\sum P_k·\mathrm{Gain}(k,j)$ is the accumulated interference with respect to $\mathrm{link}(i,j)$ .

Furthermore, assumed that a link is error-free if and only if the SIR is above a threshold, the SIR-criterion is defined as follows

$$\mathrm{SI}{R}_{i,j}=\frac{P_i·\mathrm{Gain}(i,j)}{(N_r+\mathrm{Tota}{l}_{\mathrm{Interference}(i,j)})}\ge {\gamma }_{\mathrm{SIR}}$$

(7)

However, due to interference and limited information, conflict-free schedules are very difficult to create and uphold. In order to make comparisons for simultaneous transmission links, a conflict graph for multilink communications in the radio networks is defined.

Definition 9

A conflict graph for multilink communications in the radio networks is a weighted directed graph, $G_{\mathrm{conflict}}=(A_{\mathrm{link}},E_{\mathrm{conflict}})$ with each vertex $\mathrm{link}(i,j)\in A$ representing a communication link from $\mathrm{transceive}{r}_i$ to $\mathrm{transceive}{r}_j$ . The directed edge $(\mathrm{link}(i,k),\mathrm{link}(j,k))$ , denoted as $e_{\mathrm{conflict}}\in E$ , representing that there is a conflict between $\mathrm{link}(i,k)$ and $\mathrm{link}(j,k)$ , that is, simultaneous transmissions over communication links $\mathrm{link}(i,k)$ and $\mathrm{link}(j,k)$ are not successful. When two links share a primary transceiver, these links must be assigned different time slots in order to avoid the conflict.

The time slots’ assignment with minimum scheduler problem can be described in the following.

Given the set of transceivers N, the link gain between every pair of transceivers, the transmitting power of each transceiver, the noise effect, and the threshold, the objective of the time slots assignment is to find a minimum-length schedule, such that every link receives at least one time slot, and such that the following constraints are satisfied.

• Two links that share a primary transceiver, irrespective of the link directions, must be assigned different time slots.

• A time slot can be assigned to a link only if the SIR constraint for the link is satisfied.

Given that a conflict graph for multilink communications in the radio networks and

$$x_{\mathrm{ijt}}=\{\begin{array}{cc}1\hfill & \mathrm{timeslot}(t)\to \mathrm{link}(i,j)\hfill \\ \multicolumn{1}{c}{0}& \mathrm{otherwise}\hfill \end{array}$$

(8)

$$y_t=\{\begin{array}{cc}1\hfill & \mathrm{used}(\mathrm{timeslot}(t))\hfill \\ \multicolumn{1}{c}{0}& \mathrm{otherwise}\hfill \end{array}$$

(9)

$$v_{\mathrm{it}}=\{\begin{array}{cc}1\hfill & \mathrm{timeslot}(t)\to \mathrm{transceive}{r}_i\hfill \\ \multicolumn{1}{c}{0}& \mathrm{otherwise}\hfill \end{array}$$

(10)

The objective of the time slots assignment is to find a minimum scheduler, such that it can meet all the constraints

$$Z=min\sum _{t\in T}{y}_t$$

(11)

$$\begin{array}{c}s.t.\sum _{t\in T}{x}_{\mathrm{ijt}}\ge 1,\forall \mathrm{link}(i,j)\in A\hfill \\ x_{\mathrm{ijt}}\le y_t,\forall \mathrm{link}(i,j)\in A,\forall t\in T\hfill \\ \sum _{j:(i,j)\in A}{x}_{\mathrm{ijt}}+\sum _{j:(i,j)\in A}{x}_{\mathrm{jit}}\le 1,\forall i\in N,\forall t\in T\hfill \\ x_{\mathrm{ijt}}\le v_{\mathrm{it}},\forall \mathrm{link}(i,j)\in A,\forall t\in T\hfill \\ \frac{P_i·x_{\mathrm{ijt}}}{N_r·L_{\mathrm{ij}}}+{\gamma }_{\mathrm{SIR}}(1+M_{\mathrm{ij}})(1-x_{\mathrm{ijt}})\ge {\gamma }_{\mathrm{SIR}}(1\hfill \\ +\sum _{k\in N,k\ne i,j}\frac{P_k·v_{\mathrm{kt}}}{N_r·L_{\mathrm{kj}}},\forall \mathrm{link}(i,j)\in A,t\in T\hfill \\ x_{\mathrm{ijt}}=0/1,\forall \mathrm{link}(i,j)\in A,\forall t\in T\hfill \\ v_{\mathrm{it}}=0/1,\forall i\in N,\forall t\in T\hfill \\ y=0/1,\forall t\in T\hfill \end{array}$$

(12)

Solution method for minimum scheduler time slot assignment problem

The time slot assignment problem is also a NP-complete problem, and a variety of heuristic algorithms for the time slot assignment can be found in the literature, that is, minimizing the frame length for link-oriented scheduling in the studies of Chang and Lee ¹² and Rayeni et al. ¹³ minimizing the number of colors used in the graph in the literatures.^14–16 Our heuristic strategy–joint assignment is a time slot assignment with transmission rights (TSATR). When a link is assigned a time slot, the transceiver first checks whether there is a packet to transmit on that link. If there is no such packet, any other link with the same transmitting transceiver might be used if the transceiver has a packet to transmit. The following will illustrate how it works in more detail.

The approach begins with an allocation algorithm of communication rights, which produces a link priority set, $\mathrm{LIN}{K}_{\mathrm{prio}}[]$ . According to the link priority set, the link with highest priority can be first assigned to a time slot.

Second, we suggest a novel assignment strategy that achieves the advantages of simultaneous assignment. Our proposed strategy, the TSATR algorithm, is the use of the SIR. This strategy is based on a link schedule, but in which transmission rights are extended. In this case, interference-based scheduling can be implemented for all scheduling, and the time slot assignment strategy will be transformed into a search for optimal solution.

An allocation algorithm of communication rights

An allocation algorithm of communication rights is based on full knowledge of the interference environment, where the needed information for the Transmitter (TX)/Receiver (RX) mode of a transceiver, that is, received power (including interference), local schedule, and priorities must be obtained as shown in Figure 3 to simplify the problem.

Figure 3.

The needed information for the TX/RX mode of a transceiver.

Received power

To achieve conflict-free scheduling on $\mathrm{link}(i,j)$ , the received power from each of the other transmitters need be considered. If the received power level from a transmitter is below a value, it is assumed that such links do not affect one another. This assumption can be used to determine whether its transmission will cause problems for other links. Since received power can be obtained by measurements on the channel, this value of the threshold is dependent on some parameters, that is, receiver sensitivity, transmitting power, and the interference threshold.

The choice of these thresholds is dependent on several factors, such as the actual modulation method of the signal, properties of the receiver noise, data rate, and required bit error ratio (BER).

Local schedule

In the multilinks communication as shown in Figure 3, the PRX (primary receiver) needs to know the local schedule and how much more interference can be handled by itself in each time slot. The local schedule is used to determine whether the PRX can handle all existing interferences. A link can be assigned the time slot if $P_i·\mathrm{Gain}(i,k)<\mathrm{MA}{X}_{\mathrm{Interference}}(\tau )$ for all assigned primary transceivers (PTRs) in time slot $\tau$ . Instead of the actual SIR, the local schedule and received power are used to assign the time slot for all links.

Priorities

Since we do not hope two transmitters to be transmitting simultaneously in the same channel, the transmitter needs such information from the entire local neighborhood. The transmitter needs to know when it should start transmitting and also needs to know if the others are transmitting. Therefore, priority order is needed in multilink communication. The link priority decides in which order the links may attempt to assign themselves a time slot, which depends on the number of time slots the link is assigned and the traffic of the link. The traffic of the link can be estimated by the higher layers,^17–19 that is, the MAC layer. Since both these values are changing, the link priority is constantly changing. The link with the highest priority will receive more than one time slot before any of other links receive one slot.

In short, our allocation algorithm can be described by the following steps:

• A link is created—this creates a new link process (or restarts an earlier process); assumed that $\mathrm{Rights}[\mathrm{link}(i,j)]$ for the new link is set to a value greater than zero, which results in a priority value of zero. This means that the link will assign itself a time slot if one is available.

• A link break—this stops the link process, and all assigned time slots will be deal-located. This will lead to similar consequences as when a link gives up a time slot due to interference.

• A new transceiver is added to the network—this can be seen as several links that are added simultaneously. It can also change traffic in the network.

• A transceiver disappears from the network—this can be seen as the removal of several links at once. It can also change traffic in the network.

• Assumed that a link that needs many time slots will have high priority more often than a link with a time slot.

Algorithm 3.

An allocation algorithm of communication rights.

Require: A list containing all of the link sets (LINK) and an empty list $\mathrm{Rights}[]$ Ensure: The link sets with the priorities $\mathrm{LIN}{K}_{\mathrm{prio}}$  1:   $\mathrm{LIN}{K}_{\mathrm{prio}}[]\leftarrow \{\}$  2:  for each link in LINK do 3:   record received power $R_i$ , transmitting power $P_i$ , 4:     $\mathrm{Gain}(i,j)$ , and the interference threshold ${\gamma }_{\mathrm{ij}}$  5:    $\mathrm{Rights}[\mathrm{link}]\leftarrow 0$  6:   order by the link throughput into X_LINK 7:  end for 8:  for each link $\mathrm{lin}{k}_i$ in X_LINK do 9:   if $\mathrm{lin}{k}_i$ is unique then10:     $\mathrm{LIN}{K}_{\mathrm{prio}}\leftarrow \mathrm{LIN}{K}_{\mathrm{prio}}\cup \left\{\mathrm{lin}{k}_i\right\}$ 11:     $\mathrm{Rights}[\mathrm{lin}{k}_i]++$ 12:    else13:     while each link $\mathrm{link}(i,k)$ in X_LINK do14:      calculate $\sum P_i·\mathrm{Gain}(i.k)$ 15:       if $\sum P_i·\mathrm{Gain}(i.k)>{\gamma }_i$ then16:         $\mathrm{LIN}{K}_{\mathrm{prio}}\leftarrow \mathrm{LIN}{K}_{\mathrm{prio}}\cup \left\{\mathrm{lin}{k}_i\right\}$ 17:         $\mathrm{Rights}[\mathrm{lin}{k}_i]++$ 18:       end if19:      end while20:     end if21:  if $\mathrm{lin}{k}_i$ is removal and $\mathrm{lin}{k}_i$ is unique then22:    $\mathrm{LIN}{K}_{\mathrm{prio}}\leftarrow \mathrm{LIN}{K}_{\mathrm{prio}}/\left\{\mathrm{lin}{k}_i\right\}$ 23:    $\mathrm{Rights}[\mathrm{lin}{k}_i]=0$ 24:  end if25:  if $\mathrm{lin}{k}_i$ is removal and $\mathrm{lin}{k}_i$ is not unique then26:    while each link $\mathrm{link}(i,k)$ in X_LINK do27:      $\mathrm{LIN}{K}_{\mathrm{prio}}\leftarrow \mathrm{LIN}{K}_{\mathrm{prio}}\backslash \left\{\mathrm{lin}{k}_i\right\}$ 28:      $\mathrm{Rights}[\mathrm{lin}{k}_i]=0$ 29:   end while30:  end if31:  order by $\mathrm{Rights}[]$ into $\mathrm{LIN}{K}_{\mathrm{prio}}[]$ 32:  return $\mathrm{LIN}{K}_{\mathrm{prio}}[]$

According to link set priority, the link with highest priority first will be assigned to the transmission rights.

The TSATR algorithm

The next step is the TSATR, which is run in parallel for every link with transmission rights. ²⁰ Considering that links can transmit simultaneously, the algorithm creates a routing tree for every link. The TSATR is described as follows:

• Initiate by choosing the link with highest priority as a root.

• Every link has three states: this means that between link-state changes (active, waiting, or asleep) our algorithm may use the routing protocol for its updates regarding assignment of slots. But when a change takes place, our algorithm must first work out its new local neighborhood with the old routing information before the routing protocol adapts to the change.

• Links with highest priority assigns itself a time slot.

• When a new link has highest priority, the local schedule is then updated.

• Links can transmit simultaneously: The term SIR is used to determine whether a link can transmit simultaneously with all other assigned links.

• This process is continued until all slots are occupied.

Our assignment strategy can achieve the advantages of simultaneous assignment, using the SIR. This strategy is based on a link schedule, but in which transmission rights are extended. Assume that $\mathrm{LINK}$ is a set of $\mathrm{link}(i,j)$ such that they can transmit simultaneously according to equation (13)

$$\underset{\mathrm{LINK}}{\Pi }\mathrm{link}(i,j)\ge {\gamma }_{\mathrm{SIR}},\forall \mathrm{link}(i,j)\in \mathrm{LINK}$$

(13)

Furthermore, assume that the transmitting transceivers of $\mathrm{LIN}{K}_{\mathrm{Re}}$ present their transmissions to other receiving transceivers than scheduled in the initial link schedule and that $\mathrm{LIN}{K}_{\mathrm{non}-\mathrm{Re}}$ is the rest of the links, that is

$$\mathrm{LIN}{K}_{\mathrm{non}-\mathrm{Re}}=\mathrm{LINK}\backslash \mathrm{LIN}{K}_{\mathrm{Re}}$$

(14)

If $\mathrm{LIN}{K}_{\mathrm{non}-\mathrm{Re}}$ is to be conflict-free, the following inequality must be valid

$$\underset{\mathrm{LINK}}{\Pi }\mathrm{link}(i,j)\ge {\gamma }_R\begin{array}{ccc}\mathrm{for}\hfill & \mathrm{all}\hfill & \mathrm{link}(i,j)\hfill \end{array}\in \mathrm{LINK}$$

(15)

In this case, interference-based scheduling can be implemented for all scheduling, and the time slot assignment strategy will be transformed into a search for optimal solution.

Algorithm 4.

The time slot assignment with transmission rights algorithm.

Require: The link sets with the priorities $\mathrm{LIN}{K}_{\mathrm{prio}}$ , and an empty list (ELINK)Ensure: The set of time-slot[i], i = 1, 2, …, T where T is the period of the schedule 1:   $i\leftarrow 0$  2:   $\mathrm{timeslot}[]\leftarrow \{\}$  3: for each link in $\mathrm{LIN}{K}_{\mathrm{prio}}$ do 4:    ${\tau }_i\leftarrow 0$  5:   calculate the number of time slots that this link must be guaranteed 6:  end for 7:   $i\leftarrow 0$  8:  for each link $\mathrm{lin}{k}_i$ in $\mathrm{LIN}{K}_{\mathrm{prio}}$ do 9:    $\mathrm{timeslot}[i]\leftarrow \mathrm{timeslot}[i]\cup \mathrm{lin}{k}_i$ 10:   if $\mathrm{lin}{k}_i$ can transmit simultaneously11:     $\mathrm{LIN}{K}_{\mathrm{prio}}\leftarrow \mathrm{LIN}{K}_{\mathrm{prio}}\backslash \mathrm{lin}{k}_i$ 12:     $\mathrm{ELINK}\leftarrow \mathrm{ELINK}\cup \mathrm{lin}{k}_i$ 13:     ${\tau }_i\leftarrow 0$ 14:   else15:     $\mathrm{timeslot}[i]\leftarrow \mathrm{timeslot}[i]\backslash \mathrm{lin}{k}_i$ 16:     ${\tau }_i\leftarrow {\tau }_i+1$ 17:   end if18:  end for19:   $i\leftarrow 0$ 20:  for each link $\mathrm{lin}{k}_i$ in ELINK do21:   if $\mathrm{lin}{k}_i$ not in timeslot[ ]22:     $\mathrm{timeslot}[i]\leftarrow \mathrm{timeslot}[i]\cup \mathrm{lin}{k}_i$ 23:     if $\mathrm{lin}{k}_i$ can transmit simultaneously24:      ${\tau }_i\leftarrow 0$ 25:    else26:     $\mathrm{timeslot}[i]\leftarrow \mathrm{timeslot}[i]\backslash \mathrm{lin}{k}_i$ 27:     ${\tau }_i\leftarrow {\tau }_i+1$ 28:  end if29:   end if30: end for31:  return timeslot[ ]

This algorithm is run in parallel for every link

Numerical results for time slot assignment with minimum scheduler

The experiments described in this section use packet loss rate as the evaluation of wireless links, which is easy to measure and reflect the link quality experienced by higher layers. We have considered two scenarios to evaluate our time slot assignment: a baseline scenario and a hybrid scenario. To minimize the impact of environmental factors, the baseline experiments were performed just before the hybrid experiments.

Baseline scenario

We considered three experiments to evaluate our methodology in the baseline scenario. In the first experiment, baseline tests for the Wi-Fi links, such as packet loss rate, the average delay and throughput, have been performed. In each baseline test, 1000 byte packets were transferred from the Wi-Fi access point for 60 s, and all the Wi-Fi stations were sequentially activated. The packet reception rates at all stations were measured, and then, the average delay and throughput were calculated. In the second experiment, baseline tests for BT link pairs have been performed. In the third experiment, baseline tests for RFID link pairs have been performed. In analogous fashion to the Wi-Fi link baseline tests, again all testing was carried out with BT link pairs or RFID link pairs.

Hybrid scenario

To test the algorithm in the wireless multi-core architecture, we performed the following experiment. We use the settings that we used in the baseline scenario and consider all the link pairs including RFID, BT, and Wi-Fi working at the same time.

The entire test was repeated 30 times using our time slot assignment algorithm while recording the link loss rate, the latency, and the throughput for all link pairs in each run. The average loss rate, the average latency, and the average throughput were calculated. Table 3 shows the average link loss rate after running the time slot assignment algorithm for 30 times and the average link loss rate after assigning randomly. The results demonstrate that the time slot assignment algorithm reduce the average link loss rate in the baseline tests and has no evident effect on the hybrid system. The reason is as follows: it needs to know the traffic knowledge from higher layer.

Table 3.

The average link loss rate after running the time slot algorithm and the average link loss rate after assigning randomly.

	The average link loss rate using the time slot algorithm (%)	The average link loss rate by assigning random (%)
Wi-Fi link pairs test	3.1	17
BT link pairs test	3.8	22
RFID link pairs test	5.2	29
All link pairs mixed	29.7	53

BT: Bluetooth; RFID: radio frequency identification.

FPGA-based solutions

In order to address the problem stated in section “RF channel assignment with minimum interference at the physical channel layer” and show how the dynamic channel allocation algorithm is applicable for the network of things, we present two solutions: the frequency spectrum–sharing solution and the protocol-based solution. The former gives a design framework for the implementation of four-way orthogonal RF transform. This framework is built upon FPGA and provides the functions of spreading spectrum and frequency-hopping at 2.4 GHz. The latter analyzes local time–frequency distribution features of the off-the-shelf products and implements the dynamic channel allocation algorithm on FPGA chip, in which each interval is assigned to only one different transceiver.

Frequency spectrum–sharing solution: design framework for the implementation of the orthogonal RF transform

Our design framework is inspired by RF modulation recognition, wherein the FPGA unit is used for planning and allocating the available frequency spectrum to different transceiver to target the control of frequency-hopping at 2.4 GHz. The framework consists of three-stage interconnections: modulation (or demodulation), hopping, and mixer. FPGA is the core of modulation and hopping, and realize the functions of spreading spectrum and frequency-hopping, respectively (Figure 4).

Figure 4.

Framework for the implementation of the orthogonal RF transform.

In the modulation stage, the four-way orthogonal base-band signals are built, which can be divided into the following steps:

• Step 1. Build the base-band data set generated from our dynamic channel allocation algorithm.

• Step 2. Encode the base-band sample based on the base-band data set obtained in Step 1. To create such a base-band sample, we randomly choose the elements of each base-band data set.

• Step 3. Modulate the base-band sample in FPGA to control the data distribution service (DDS) kernel in the AD9856. To eliminate the amplitude and phase error between channels, we complete the orthogonal modulation of such a base-band sample where the orthogonal components of the signal can be obtained after multiplying the orthogonal carriers.

In the hopping stage, the local oscillator signal “2380 MHz” is provided by the phase-locked loop (PLL)+voltage-controlled oscillator (VCO), wherein the frequency of the data values is kept without losses. The hopping can be divided into the following steps:

• Step 1. Control the PLL frequency synthesizer ADF4113 by the signal timing of the FPGA;

• Step 2. Compared the frequency of ADF4113 reference crystal oscillator to that of VCO, the voltage is converted into the corresponding linear voltage output;

• Step 3. After the high-frequency interference is filtered by the low-pass filter (LPF), a stable voltage is obtained to control the oscillation frequency output of the VCO.

In the mixer stage, the mixer is modulated to 2.4 GHz RF, and RF output frequency can be obtained between 2.4 and 2.5 GHz.

Protocol-based solution: FPGA implementation of a fast customized channel design using the off-the shelf products

Our protocol-based infrastructure is protocol compatible with existing IEEE 802.11 and BT standards as well as existing RFID standards. We construct BT and IEEE 802.11 protocols compatible with RFID in FPGA by retaining the frame structures and channel access mechanisms but adding the capability of back-scatter radiation and amplitude-shift keying (ASK) carrier modulation to the RFID front-end. Figure 5 displays the hardware setup of RFID combined with IEEE 802.11b/BT infrastructure. The setup is essentially a FPGA solution that can operate within the standardized RFID communication specifications but also can operate the IEEE 802.11b and BT standards.

Figure 5.

Protocol-based solution.

The hybrid FPGA infrastructure consists of two signal generators: RFID signal generation using back-scatter radiation mode and IEEE 802.11/BT signal generation using RX/TX communication mode. The infrastructure can maintain protocol compatibility by switching the antenna impedance in synchronization with a BT/IEEE 802.11 frame organized bit stream. The infrastructure focuses on the protocol-based coexistence, and all the transceivers use the off-the-shelf products, that is, the nRF24LE1 chip as an RFID module, the TiWi-BLE module as a Wi-Fi module, and the Broadcom BCM2046 chip as a BT module.

First, the hybrid infrastructure can be automatically switched to back-scatter radiation mode and then emits a continual radio wave energy in a frequency-hopping pattern. Through their antenna, RFID tags will be fed with the continual radio wave that represents wake up command. Once a tag wakes up, it can keep communication with the infrastructure by means of radio waves. In order to improve their level of coexistence between RFID and IEEE 802.11/BT networks, an asynchronous wake up mode is designed where the RF signal on the infrastructure antenna is utilized to trigger RFID chip, IEEE 802.11 chip, or BT chip, and then, the system will record their responses. It is noted that the performance of all the wireless devices can be observed using the described setup.

Summary

Our proposed solutions are aimed at identifying the ability of the dynamic channel allocation algorithm to carry out the wireless coexistence at two different level solutions: a chip-level solution and a board-level synthesis. These solutions are operated independently, aiming to provide their different services to users. The former uses a chip-level synthesis and is designed from the RF channel; the latter uses a board-level synthesis and is designed from the network layer (due to the adoption of the off-the-shelf products, RF and MAC need not be considered). Table 4 demonstrates that the frequency spectrum–sharing solution is much more effective than the protocol-based solution. Moreover, we consider the competition between the two solutions, which are the very attractive candidates in implementing the wireless communication coexistence.

Table 4.

Comparison between frequency spectrum–sharing solution and protocol-based solution.

Solution	Frequency spectrum–sharing solution	Protocol-based solution
Objective	Spreading spectrum and frequency-hopping	Dynamic channel allocation
Speed	Fast	Middle
Negotiation	No	Yes
Implementation complexity	Simple	Complex
Accuracy	High	Middle
Efficiency	High	Middle

Conclusion and future work

Assigning optimal channels to different transceivers is a crucial process for combined RFID/BT/Wi-Fi chips. Unless carefully planned, such heterogeneous NoC architecture increases the level of interference. Thus, overlapping channel interference has to be reduced by efficient spectrum planning schemes. We have studied the minimum carrier spacing on frequencies for such combined RFID/BT/Wi-Fi chips and then developed a mathematical model that captures the amount of interference between overlapping channels for such NoC architectures. The physical channel assignment problem is NP-hard. However, by minimizing channel interference, we have developed a dynamic channel allocation algorithm for such NoC architecture. We have also presented a time slot assignment with a minimum scheduler model for multilink shared channel in order to provide a reliable link between two peer MAC entities.

Several conclusions can be drawn from our computational study. First of all, the minimum carrier spacing on frequencies for combined RFID/BT/Wi-Fi chips yields very tight bounds. These bounds are very useful for RF channel assignment. Applying the minimum carrier spacing on frequencies often leads to optimal or near-optimal solutions that can assign optimal channels to all different transceivers. Second, assumed that total interference power is the sum of the powers received from the individual interferers, the mathematical model that captures the amount of interference between overlapping channels need to distinguish between the actual different interferers such as RFID transceiver, BT transceiver, or Wi-Fi one. Moreover, the PHY/MAC optimization algorithms performed well for some of the cases in our experiments. For the physical channel assignment experiments, the total interference using the DCA algorithm is less than 31% comparing with random channel assignment. For the reliable link between two peer MAC entities experiments, the average link loss rates after running the time slot algorithm can be significantly reduce (up to 29.7%). The main advantage of these algorithms is its simplicity, which makes it an interesting candidate for such multi-core NoC architectures.

There are several directions for further research. One specific topic is system-level synthesis, where the primary performance measure is the network throughput. This topic is currently under investigation. Another very interesting topic is to develop a combined RFID/BT/Wi-Fi cores in a single chip, where different kinds of transceivers with different protocols operate in the same area. So far, optimization methods are mainly useful as reference methods because they require all information about the network, and it takes a long time to calculate the schedules, especially for hybrid networks. Finding the best schedule with a given frame length is still very difficult. ²¹