DEVICE-TO-DEVICE COMMUNICATION WITH LONG-TERM RESOURCE ALLOCATION

TECHNICAL FIELD

The present disclosure relates to device-to-device (D2D) communications, and in particular to scheduling a D2D device on resource blocks (RBs) of existing cellular devices in a network that is scheduling both cellular and D2D devices and optimizing the capacity of D2D underlays on legacy cellular networks with simultaneous D2D and legacy wireless device transmissions.

BACKGROUND

In order to achieve high data rates, several technologies including Evolved Universal Mobile Telecommunications System (UMTS) terrestrial radio access (EUTRA) and EUTRA network (EUTRAN) have been developed in the Third Generation Partnership Project (3GPP) Long Term Evolution (LTE) set of standards. Furthermore, local service requirements have led to the development of newer technologies in LTE-Advanced and are being proposed for "5G" implementations.

In order to provide local services, one approach is to use license exempt spectrum of wireless local area networks (WLANs). Another approach is data transmission on a licensed band in a coordinated and planned network. Regarding this latter approach, device-to-device (D2D) communication has been studied extensively, where wireless devices in proximity to one another can transmit data directly to each other with reused cellular resource blocks. Thus, in a D2D communication scenario, two wireless devices, such as user equipments (UEs), directly communicate with each other without having the payload traverse the backhaul network. Due to its local communication nature, D2D communication can be provided with smaller fees compared to the fees for cellular communication. D2D communication provides many benefits that cannot be provided by uncoordinated communication.

D2D communications provide a number of advantages. These are summarized as follows:

• The overall network spectral efficiency can be improved significantly with an optimal configuration as compared with other communication technologies. • Low delay and low power consumption due to the proximity of wireless devices.

• Improved radio resource utilization because of resource reuse by both cellular wireless devices and D2D pairs simultaneously.

· Using one link for direct communication, instead of one uplink and one

downlink for communication through the base station, reduces resource usage.

• Offloading cellular traffic to D2D traffic reduces congestion in the backhaul network, benefiting existing cellular wireless devices in the network.

There are many current and prospective applications for D2D

communications. For example, D2D communications has been proposed for use in LTE-based public safety networks in the United States for its security and reliability. In addition, D2D communication is necessary for scenarios where the cellular transmission is not accessible.

In commercial networks, many social network applications require recognition of nearby wireless devices. Proximity wireless device recognition is usually handled in a centralized manner, where wireless devices are required to register their location information in a server such that the location information can be shared among the other wireless devices, e.g., in various social networking sites. With D2D, location registration is no longer required for the purpose of proximity discovery. Another prospective application for D2D communication is E-commerce, where nearby agencies need to transfer efficiently a large amount of private data.

One challenge of D2D communication is interference with coexisting cellular devices.

For a cellular network that includes D2D devices, interference needs to be carefully controlled because cellular devices and D2D devices share the spectrum. In order to manage the interference to the cellular devices in the same cell, several approaches have been proposed such as limiting D2D transmission power, for example, by employing a fixed booster factor and a back-off factor to adjust the D2D power.

In practical multi-cell networks, inter-cell interference (ICI) is a challenge that has not been addressed in the D2D literature. The ICI depends on the duplexing scheme used by cellular and D2D devices and the resources blocks shared between D2D and cellular devices.

Establishing direct communication between two nodes, or even among a set of nearby nodes in the Long Term Evolution (LTE) networks, is a way to enhance the spectral efficiency of the cellular network. Achieving potential improvements of D2D communication depends on efficiently addressing the resource and power allocation problems. Proposed solutions to these problems have proven inadequate. In a realistic cellular environment, there are multiple cellular devices and D2D pairs that attempt to access a shared resource pool. Normally, each node has access to multiple Resource Blocks (RBs) and also each RB is allocated to multiple interfering devices between cells (i.e., resource reuse among neighboring cells). Furthermore, either uplink or downlink resources can be used by D2D communication. Any realistic D2D resource allocation formulation should consider the aforementioned factors. No existing work has formulated all of these factors. Many studies propose simple heuristics that give highly sub-optimal performance, while the available optimal solutions are achieved under simplified cellular communication models.

D2D communication can cause significant ICI in neighboring cells. Current methods are not designed to maximize the combined sum rate of the cellular and D2D devices with a limit on the maximum ICI generated in the neighboring cell.

The D2D communication may be bi-directional communication where both devices receive and transmit in the same or different resources. However, D2D communication may also comprise scenarios in which one of the devices transmits and the other one receives the signals. There may also exist a point-to-multipoint (e.g. multicast, broadcast) scenario in which case a plurality of devices receive signals from the same transmitting device. This scenario is particularly useful for emergency services or public safety operation to spread vital information to several devices in an affected area. Of note, the terms D2D communication and D2D operation are interchangeably used herein.

Typically, wireless devices operate under the supervision of a radio access network with radio access nodes (e.g., base stations). However, in some scenarios the wireless devices themselves establish direct communication constituting the radio access network without the intervention of the network infrastructure. In cellular network assisted device-to-device communications (or simply network assisted D2D communications), wireless devices in the vicinity of each other can establish a direct radio link, i.e., a D2D bearer. While wireless devices communicate over the D2D "direct" bearer, they also maintain a cellular connection with their respective serving base station (eNB). This direct link is interchangeably denoted as a network (NW) link, or a D2D-NW link. The NW link is used for resource assignment for D2D communication as well as maintenance of radio link quality of D2D communication link. As such, D2D communication is a promising feature that can potentially scale the capacity of the cellular networks.

Three relevant coverage scenarios for D2D communication have been defined as shown in FIG. 1. FIG. 1 is a block diagram of a wireless communication system 10 that includes a base station 12 that serves wireless devices in a region of coverage of the base station 12. The wireless devices may include two D2D wireless devices 14a and 14b, which may share physical resource blocks ("PRBs"). Throughout this disclosure, the term "D2D wireless device 14" shall refer to an individual D2D wireless device, i.e., either wireless device 14a or wireless device 14b. The term "D2D wireless device 14 pair" shall refer to both wireless device 14a and wireless device 14b. FIG. 1 also shows a cellular wireless device 16 in communication with the base station 12 and possibly also in communication with a D2D wireless device 14b. Note that herein a base station is but one example of base stationl2.

Implementations are not limited solely to base stations.

FIG. 2 is a block diagram of the wireless communication system 10 showing multiple base stations 12 each having a separate coverage area 18. In FIGS. 1 and 2, the solid connecting lines depict desired cellular or D2D transmissions, and the dotted connecting lines depict examples of interference from other cellular and D2D wireless devices.

In coverage: In this coverage scenario, all communicating D2D wireless device 14 pairs are within the network coverage. For example, the D2D wireless device 14 pairs can receive signals from and/or transmit signals to at least one network node such as the base station 12. In this case, the D2D wireless device 14 pairs can maintain a communication link with the network 10. The network 10 in turn can ensure that the D2D communication does not cause unnecessary interference. In coverage is also interchangeably referred to as in-network (IN) coverage.

Out of coverage: In this scenario, D2D wireless device 14 pairs

communicating with each other are not under network node coverage. For example, the D2D wireless device 14 pairs cannot receive signals from and/or transmit signals to any of the network nodes. Typically the lack of coverage is due to complete absence of the network coverage in the vicinity of the D2D wireless device 14 pair. However, the lack of coverage may also be due to insufficient resources in the network nodes to serve or manage the D2D wireless device 14 pair. Therefore, in this scenario, the network cannot provide any assistance to the D2D wireless device 14 pairs. The out of coverage is also interchangeably referred to as out-of-network (OON) coverage.

Partial coverage: In this scenario, at least one communicating D2D wireless device 14 pair is within network coverage, and at least one other D2D wireless device 14 pair is not under network coverage, but is communicating with a D2D wireless device 14 that is under network coverage. As mentioned above, the D2D wireless device 14 not being under network coverage can be due to lack of any network node in its vicinity or due to insufficient resources in any of the network nodes in its vicinity. The partial coverage is also interchangeably called partial-network (PN).

SUMMARY

The present disclosure advantageously provides a method and system for scheduling a D2D device on resource blocks (RBs) of existing cellular devices in a network that is scheduling both cellular and D2D devices. This enables improvement in spectral efficiency over networks that schedule D2D devices and cellular devices on orthogonal resources. This disclosure describes a method to ostensibly improve the throughput of a D2D device while satisfying a long-term power constraint for the D2D device. It also ensures that the probability that the signal to noise-plus- interference ratio (SINR) being below a target threshold level is less than a pre- defined small value for a legacy cellular or wireless access network (WAN) device sharing the same physical resource blocks (PRBs) within the same cell or the neighboring cells, and, thus assuring a specific long-term Quality of Service (QoS) for the interfering cellular devices in the main cell and also neighboring cells.

According to one aspect of the disclosure, a method for scheduling a D2D wireless device using RBs of active cellular wireless devices in a wireless network is provided. In one embodiment, the method includes determining a power allocation for each of the RBs based on achieving a target rate for the D2D wireless device and the active cellular wireless devices, and scheduling the D2D wireless device based on the determined power allocation.

According to one embodiment of this aspect, the method further includes determining a cellular wireless device of the active cellular wireless devices to be matched with the D2D wireless device pair, allowing the D2D wireless device to share all RBs allocated to the cellular wireless device that is matched with the D2D wireless device pair, determining a power allocation for each RB of the allocated RBs based on achieving a target rate for the D2D wireless device and the cellular wireless device to which the D2D wireless device pair is matched, and scheduling the D2D wireless device based on the allocated RBs based on the determined power allocation.

According to another embodiment of this aspect, achieving the target rate for the D2D wireless device and the cellular device to which the D2D wireless device pair is matched satisfies constraints on a power of the D2D wireless device and a

SINR of interfering cellular wireless devices in one of a main cell and a neighboring cell. According to another embodiment of this aspect, the method further includes obtaining feedback information from each interfering cellular device in one of a main cell and a neighboring cell and at least one of forwarding the feedback information to the D2D wireless device and instructing the D2D wireless device to adjust power over each RB based on the feedback information.

According to another embodiment of this aspect, if the feedback information indicates conflicting power adjustments over each RB, the method further includes instructing the D2D wireless device to at least one of decrease power over each RB in order to satisfy constraints on a SINR of interfering cellular wireless devices in one of a main cell and a neighboring cell and increase power over each RB in order to satisfy constraints on a SINR of interfering cellular wireless devices in one of a main cell and a neighboring cell. According to another embodiment of this aspect, the feedback information is comprised of one data bit.

According to another embodiment of this aspect, adjusting the power over each RB includes one of increasing the power over each RB which satisfies constraints on power, and decreasing the power over each RB which satisfies constraints on a SINR of interfering cellular wireless devices in one of a main cell and a neighboring cell.

According to another embodiment of this aspect, the method further includes determining a sign of a subgradient value which is related to SINR constraints of interfering cellular wireless devices in one of a main cell and a neighboring cell, the determining based on the feedback information. According to another embodiment of this aspect, the method further includes using time averaging as an approximation for statistical mean to approximate the subgradient value.

According to another embodiment of this aspect, the method further includes calculating a target level of power over each RB of the allocated RBs to meet a time averaged signal to SINR for an interfering cellular wireless device in one of a main cell and a neighboring cell. According to another embodiment of this aspect, the target level of power is calculated to meet the time averaged SINR with a pre- specified probability.

According to another embodiment of this aspect, the method further includes using average channel measurements over a predetermined period of time to determine the cellular wireless device to be matched with the D2D wireless device pair.

According to another aspect of the disclosure, a network entity configured to schedule a D2D wireless device using RBs of active cellular wireless devices in a wireless network is provided. In one embodiment the network entity includes a communications interface, and processing circuitry including a memory and a processor, the memory in communication with the processor, the memory having instructions that, when executed by the processor, configure the processor to determine a power allocation for each of the RBs based on achieving a target rate for the D2D wireless device and the active cellular wireless devices, and schedule the D2D wireless device based on the determined power allocation.

According to an embodiment of this aspect, the processor is further configured to determine a cellular wireless device of the active cellular wireless devices to be matched with the D2D wireless device pair, allow the D2D wireless device to share all RBs allocated to the cellular wireless device that is matched with the D2D wireless device pair, determine a power allocation for each RB of the allocated RBs based on achieving a target rate for the D2D wireless device and the cellular wireless device to which the D2D wireless device pair is matched, and schedule the D2D wireless device based on the allocated RBs based on the determined power allocation.

According to another embodiment of this aspect, achieving the target rate for the D2D wireless device and the cellular device to which the D2D wireless device pair is matched satisfies constraints on a power of the D2D wireless device and a SINR of interfering cellular wireless devices in one of a main cell and a neighboring cell.

According to another embodiment of this aspect, the processor is further configured to obtain feedback information from each interfering cellular device in one of a main cell and a neighboring cell, and the communications interface is further configured to at least one of forward the feedback information to the D2D wireless device and instruct the D2D wireless device to adjust power over each RB based on the feedback information.

According to another embodiment of this aspect, if the feedback information indicates conflicting power adjustments over each RB, the processor is further configured to instruct the D2D wireless device to at least one of decrease power over each RB in order to satisfy constraints on a SINR of interfering cellular wireless devices in one of a main cell and a neighboring cell and increase power over each RB in order to satisfy constraints on a SINR of interfering cellular wireless devices in one of a main cell and a neighboring cell. According to another embodiment of this aspect, the feedback information is comprised of one data bit.

According to another embodiment of this aspect, adjusting the power over each RB includes one of increasing the power over each RB which satisfies constraints on power, and decreasing the power over each RB which satisfies constraints on a SINR of interfering cellular wireless devices in one of a main cell and a neighboring cell.

According to another embodiment of this aspect, the processor is further configured to determine a sign of a subgradient value which is related to SINR constraints of interfering cellular wireless devices in one of a main cell and a neighboring cell, the determining based on the feedback information. According to another embodiment of this aspect, the processor is further configured to use time averaging as an approximation for statistical mean to approximate the subgradient value.

According to another embodiment of this aspect, the processor is further configured to calculate a target level of power over each RB of the allocated RBs to meet a time averaged SINR for an interfering cellular wireless device in one of a main cell and a neighboring cell. According to another embodiment of this aspect, the target level of power is calculated to meet the time averaged SINR with a pre- specified probability.

According to another embodiment of this aspect, the processor is further configured to use average channel measurements over a predetermined period of time to determine the cellular wireless device to be matched with the D2D wireless device pair.

According to another aspect of this disclosure, a network entity configured to schedule a D2D wireless device using RBs of active cellular wireless devices in a wireless network is provided. In one embodiment, the network entity includes a communications module, a processing module, a power allocation module configured to determine a power allocation for each of the RBs based on achieving a target rate for the D2D wireless device and the active cellular wireless devices, and a scheduling module configured to schedule the D2D wireless device based on the determined power allocation.

BRIEF DESCRIPTION OF THE DRAWINGS

A more complete understanding of the present embodiments, and the attendant advantages and features thereof, will be more readily understood by reference to the following detailed description when considered in conjunction with the accompanying drawings wherein:

FIG. 1 is a block diagram of a wireless network supporting D2D

communications illustrating D2D wireless devices and cellular wireless devices served by a base station, sharing PRBs;

FIG. 2 is a block diagram of a wireless network supporting D2D

communications illustrating an example of D2D and cellular transmissions with neighboring cells;

FIG. 3 is a flowchart illustrating an exemplary process for matching a D2D wireless device pair with an active cellular wireless device utilizing principles of the present disclosure;

FIG. 4 is a flowchart illustrating an exemplary process for determining optimal power allocation for each resource block utilizing principles of the present disclosure;

FIG. 5 is a flowchart illustrating an exemplary process for implementing a heuristic long-term D2D rate improvement method using low-complexity dynamic time-averaging;

FIG. 6 is a block diagram of an exemplary network device configured to schedule a D2D wireless device;

FIG. 7 is a block diagram of an alternative network device configured to schedule a D2D wireless device;

FIG. 8 is a flowchart illustrating an exemplary process for scheduling a D2D wireless device; and

FIG. 9 is a flowchart illustrating another embodiment of an exemplary process for scheduling a D2D wireless device. DETAILED DESCRIPTION

The present disclosure includes embodiments which can be implemented in a network node and a network capable wireless device, such as a UE. The term

"network entity" will be used herein to refer to a network node or a network capable wireless device. The network entity herein can be the serving network node of the wireless device or any network node with which the wireless device can establish or maintain a communication link and/or receive information, e.g., via broadcast channel. Specifically, network entity 12 can be any kind of network node which may comprise of a radio network node such as base station, radio base station, base transceiver station, base station controller, network controller, evolved Node B (eNB), Node B, Multi-cell/multicast Coordination Entity (MCE), relay node, access point (AP), radio access point, Remote Radio Unit (RRU) Remote Radio Head (RRH), a core network node (e.g., Mobile Management Entity (MME), Self-Organizing Network (SON) node, a coordinating node, positioning node, MDT node, etc.), or even an external node (e.g., 3rd party node, a node external to the current network), etc.

As used herein, a wireless device is not limited to a UE. A wireless device is any type of device that is configured or configurable for communication through wireless communication. Examples of such wireless devices are sensors, modems, smart phones, machine type (MTC) devices a.k.a. machine to machine (M2M) devices, Personal Data Assistants (PDAs), iPADs, Tablets, smart phones, laptop embedded equipped (LEE), laptop mounted equipment (LME), Universal Serial Bus (USB) dongles, etc.

The embodiments described herein also use a generic term "D2D wireless device" which includes a D2D transmitting device and a D2D receiving device. Of course, the roles may reverse depending on which device is transmitting and which is receiving at any given time. A D2D transmitting device and a receiving device can be any types of wireless devices which are capable of communication at least through wireless communication. Examples include are sensors, modems, smart phones, machine type (MTC) devices a.k.a. machine to machine (M2M) devices, PDAs, iPADs, Tablets, laptop embedded equipped (LEE), laptop mounted equipment (LME), USB dongles, etc. Although terminology from 3GPP LTE (or Evolved Universal Terrestrial Access Network (E-UTRAN)) is used in this disclosure to describe the embodiments, this should not be seen as limiting the scope of the disclosure to only the

aforementioned system. Other wireless systems, including Wide Band Code Division Multiple Access (WCDMA), Universal Mobile Telecommunications System (UMTS) Evolved Terrestrial Radio Access (UTRA)-Frequency Division Duplexing (FDD), UTRA Time Division Duplexing (TDD), and Global System for Mobile

Communications (GSM) Edge Radio Access Network (GERAN)/EDGE, may also benefit from exploiting the ideas covered within this disclosure.

The embodiments are described when D2D wireless devices and cellular wireless devices are configured to be served by or operate with a single carrier (also known as single carrier operation of the wireless device) for communication or configured to use or operate a single carrier in a network node. However, the embodiments are also applicable for multi-carrier or carrier aggregation based communication.

This disclosure provides, in some embodiments, a method and arrangement for, as compared with known arrangements, efficiently scheduling a D2D wireless device on resource blocks (RBs) of existing cellular devices in a network that is scheduling both cellular wireless devices and D2D wireless devices. This enables improvement in spectral efficiency over networks that merely schedule D2D wireless devices and cellular devices on orthogonal resources.

This disclosure also provides, in some embodiments, a method and arrangement for, as compared with known arrangements, improving the throughput of a D2D wireless device while satisfying long-term power constraints for the D2D wireless device. The disclosure also ensures that the probability that the signal to noise-plus-interference ratio (SINR) level for a legacy cellular or wireless access network (WAN) device sharing the same physical resource blocks (PRBs) within the same cell or the neighboring cells is below a target threshold is less than a pre-defined small value and thus assure a specific long-term Quality of Service (QoS) for the interfering cellular wireless devices in the main cell and also neighboring cells.

The method and arrangements of such embodiments can be applied under the following assumptions. An idle D2D wireless device pair requests capacity in a network consisting of active cellular wireless devices and D2D wireless device pairs.

Due to the localized and low-power transmission of D2D wireless device pairs, the resource planning (resource allocation and power control) of existing wireless devices in the network is not modified.

The new D2D wireless device pair will be matched with one of the active cellular wireless devices in the network, which means that the D2D wireless device pair and the cellular wireless device share all RBs allocated to a selected cellular wireless device.

It is assumed that there are N active cellular wireless devices and each cellular wireless device has access to multiple RBs.

The following summarizes proposed methods and arrangements according to some embodiments of the present disclosure in comparison with known methods and arrangements:

A difference between some embodiments of the present disclosure and other known methods is that in such embodiments of the present disclosure long-term throughput of D2D wireless device pairs and cellular wireless devices under a long- term power constraint for D2D wireless device pairs is improved, which confines the battery consumption, and long-term individual power constraints over each RB is improved in order to achieve a probabilistic SINR guarantee for all cellular wireless devices that share the same RBs with the D2D wireless device pairs.

Another difference between some embodiments of the present disclosure and other known methods is that in the embodiments of the present disclosure, the sum- rate of cellular wireless devices and D2D wireless device pairs is improved while in some known methods only the D2D wireless device pair rate is improved.

Some known methods introduce a heuristic method in which using time averaging instead of statistical mean solved the primal optimization problem in order to improve D2D rate. In some embodiments of the present disclosure, two more heuristic methods are introduced in which the time averaging approximation to the subgradient method is applied in the dual domain. Furthermore, some embodiments of the present disclosure disclose that by only using the sign of the approximated subgradient, the same performance results can almost be achieved. It should be noted that the concept of all three heuristic methods can be applied to both sum-rate and also D2D rate improvement approaches.

Some known methods only consider a single-RB scenario. In contrast, the methods and arrangements according to some embodiments disclosed herein assume that each node has access to a number of RBs. Some known methods only consider a single-cell scenario, while the methods and arrangements according to some embodiments disclosed herein consider constraints on the SINR of interfering wireless devices in the neighboring cells.

Some known methods attempt to compute the power allocation for a D2D wireless device and the corresponding cellular device at the same time. By contrast, the methods and arrangements according to some embodiments disclosed herein do not modify the scheduling of the cellular devices. Thus, the complexity of optimization arrangement may be substantially lower than with existing solutions.

There are also known arrangements that use game theory approaches for resource allocation. In contrast to the methods and arrangements according to some embodiments disclosed herein, those known arrangements propose methods that do not ensure that any network related metric will be optimized. Also, the disclosure herein considers a single-antenna, multi-RB system, while other known methods cover a multi antenna, single-RB system. Thus, the formulations of the two are distinct.

The following definitions are employed in the methods and arrangements according to some embodiments described herein. Q is defined as the set of all RBs dedicated to the I ^th cellular wireless device available to match with the D2D wireless device pair and C = Q . For the 7 ^th RB, Sj is defined as the set of all cellular wireless device located in the neighboring cells that are employing the 7 ^th RB. The notations which are used throughout this disclosure are defined in Table I.

≤ b is defined.

E{x} and x are used interchangeably.

E„{x} is defined as the time average over n consecutive samples, i.e., {x _lt Pseudo Code for Finding the Best Cellular Match

For matching a D2D wireless device pair with one or more of the cellular wireless devices, the following steps are employed: The power allocation for each RB is found such that the sum-rate is improved satisfying constraints on the sum-power of the D2D wireless device pair and also the SINR of the interfering cellular wireless device in the main cell and neighboring cells. This optimization is done by using expected values for all related channels.

The first step is done for all available cellular wireless devices in the network.

Based on calculated achievable rates, the best cellular match is found.

The input of Algorithm la below is average "long term" channel

measurement, which may be used to find the best cellular match. With respect to "long term,"in general, when describing the response of a wireless channel, there is a notion of "coherence time" which is the interval over which the channel response (typically amplitude and phase) remains relatively constant. The term usually employed in communication theory is that the channel is "stationary" (i.e. the statistics or probability distribution of the channel random variables do not change over a given interval). One example related to the amplitude of the channel response is the time interval over which one would not expect a fade. The coherence time has no definitive value, but is typically defined as the time in which the average statistics change less than 20 or 30%. Typical channel coherence times are on the order of msec.

As used herein, the term "long term" means an interval of many "coherence times," i.e., tens of seconds or minutes or even hours over which the short term statistics can be averaged out and a "longer term" statistic can be employed. For example, the long term average of a signal SINR could be 10 dB, but the short term instantaneous SINR could be -5 dB, or +15 dB due to fading. Examples of the practical use of "long term" as described in this disclosure include being able to assure a certain quality of service over time (i.e., 10 dB SINR, 99% of the time) or to predict wireless device battery performance over the long duration. For example, on average, the current drain will be X milli-amps/hour to maintain an average transmit power level of Y.

Algorithm la

Step 1.

For I = 1 to N do

If jed Vj≤ Ρ£∞ then For all j E C set p _t ^D - = rfj.

else

Using the bisection method, find ^- and > 0 such that eC _j Vx,j ⁼ ^max ^an d

end if

R. =∑y _eCl log ( ! + ¾¾). end for

Step 2. Find the best cellular wireless device for the D2D wireless device pair to match, using I* = arg max R _t .

FIG. 3 illustrates an exemplary process (step S300) performed by a network entity implementing Algorithm la, shown above. Initially, system parameters e and ω are input into the system (step S305). A counter, I is initially set to 1 (step S310) and it is determined if I is greater than the number of cellular wireless devices N, at step S320. If I is not greater than N, then if ∑jeci Wj— ^max [ ⁿ⁺ l] then the optimal power allocation is set as p^j = r j . Otherwise, the optimal power allocation is found by using equation (23) below (step S330). The total achievable D2D rate is calculated when it is matched with the Zth cellular wireless device, Rsub I, using equation (24) below (step S340). The counter I is incremented to 1+ 1 (step S350), and the process reverts back to step S320. If, at step S 120 it is determined that counter/is greater than N, then the best cellular wireless device for the D2D wireless device pair to match with is found using I * = arg (maxi Ri) (step S360).

In an alternate embodiment, Algorithm lb may be implemented by the network entity. The input of Algorithm lb below is average channel measurement, which may be used to find the best cellular match.

Algorithm lb

Step 1.

For ¹ = ¹ to ^N do

For all ^e , calculate

Define c = {j≡c _l \b _j >c _]

D

ϊί^'^' ¹ max

- then

For all ^{j e} ' , set For all ^{je C} < ^XC <' ,

else

Usi > ^> 0 ^υ _S s _l u _lr ch _{h t} th _hi a _lt t Σ^ ' ° and

end if

+biP

Calculate " ' ^/λ .

Z^Z + 1

end for

Step 2. Find the best cellular wireless device for the D2D wireless device pair to match, using ^-gmax^— .

Pseudo Code for Implementing a D2D Ergodic Rate Maximization Algorithm

(Algorithm for Finding a Solution for the Optimization Problem P3, as identified in Equations 13-15 below)

The power allocation for each RB is found such that the sum-rate is improved satisfying constraints on the sum-power of the D2D wireless device pair and also the SINR of the interfering cellular wireless devices in the main cell and neighboring cells. To implement the long-term sum-rate improvement method, the following steps are employed.

In this algorithm, it is assumed that the best cellular match from Algorithm lb is known. The values of Lagrange multipliers are estimated using the subgradient method.

Using the full statistics of involved channels, the subgradient values are estimate using the subgradient method.

The power allocation for each RB is found such that the achievable sum-rate is improved, satisfying the constraints on the sum-power of the D2D wireless device pair and also the SINR of the interfering cellular wireless devices in the main cell and neighboring cells. In this step, the Lagrange multiplier values and the optimal subgradient values which have been obtained in the previous step are used.

The network entity implements Algorithms 2a and 2b satisfy long-term sum- power and per RB individual power constraints for D2D wireless device pairs in order to control battery-usage and assure a specific QoS level for other cellular wireless devices. Then network entity implements Algorithms 2a and 2b to perform convex optimization ("convexifying") of the formulation through, in one embodiment, the use of the Chernoff bound, to assure the existence of a unique solution and to make possible a solution based on methods such as the subgradient approach. In another embodiment, the network entity implements Algorithm 2a and 2b to perform convexifying of the formulation through first, high SINR approximation of the sum rate and, and second, the Chernoff bound to assure the existence of a unique solution and to make possible a solution based on known methods such as the subgradient approach.

Algorithm 2a below provides an optimal solution for the convex problem of optimization problem P2 (as identified in equations 9-11 below) below. P3 also provided below, is an approximation of the original optimization problem PI (as identified in equations 1-4 below) below, after application of the Chernoff bound.

In Algorithm 2a below, T is the number of LTE frames over which a stationary channel environment for the D2D wireless device can be assumed.

Algorithm 2a:

Stepl. Use Algorithm 1 to find . Step2. Input e and a). Initialize μ[0] and A [0] (for all j £ C ₍ *). Set iteration number K, step sizes ≤ _μ and s _¾ .

For k = 1 to K do

1) Solve the following convex optimization problem and find

p _t ^D ;(A [n], [n])(for ally £ C _r ):

\ h \ ² Vt '

t - M _' ^M) = ^{AR§ MAX LO§} ( ¹ + -j^r - N ¾ -

V"j ^{≥0 1}

2) Calculate g[k] using equation (17).

3) Calculate δμ^] = P£ _ax -∑ _jeC] E {p¾ ^* ( _j [k], μ[1φ}.

4) Calculate dA, [/c] = e - E^^P ^j W^Wl- ^ij) } (for all j £ C _r ).

5) Set μ[λ: + 1] = (μ[λ:] - s^[/e]) ₊ and _j [k + 1] = (A _; - [/ ] - s^dA^/e]) _† (for all j £ C _r ).

end for

Step3. Calculate k' = arg min g[k]. Set A = _j [k'] (for all y £ Q*) and μ ^* = μ[&'] .

For n = 1 to T do

1) Solve the following convex optimization problem and find the optimal power allocation

(for all j £ C _r ): p _t ^D [n] = arg max log ( 1

end for

FIG. 4 illustrates an exemplary process (S400) performed by the network entity implementing by Algorithm 2a, shown above. The best cellular match is found using Algorithm 1, described above (step S410). System parameters e and ω are input. Lagrange multiplier values μ[0] and A/[0] for all y £ C ₍ * are initialized, and the proper iteration number K, and step sizes and s _¾ are set for the subgradient method (step S420). Beginning with counter k set to 1 (step S430), it is determined if counter k is greater than K (S440). If counter k is not greater than K, optimal power allocation p _t ^D /( / [/ ]^[/e]) is solved using equation 7 (below) (step S450) and the subgradient value d j [k] = e - i^^ ^j ^ ^j W^W ⁾ -' ^]) ) , i _s calculated for all j £ C (step S460). The Lagrange multiplier j [k + 1] is found using equation (14) below, for all j £ C ₍ * and the Lagrange multiplier μ[& + 1] is found using equation (15) below (step S465).

Counter k is incremented to k+l (step 470) and step S440 is repeated. If it is determined at step S440 that k is greater than K, then k' = arg min g [k] is calculated where Xj -Aj [k' and μ ^* -μ[^] and n 1 (step S475). If it is determined that n>T (step S480) the process ends. However, if it is determined that n is not greater than T, then optimal power allocation p J [n] is found by solving the optimization equation (16) below (step S485), counter n is increased to n + 1 (step S490) and the process reverts to step S480.

Alternately, Algorithm 2b may be used.

Algorithm 2b

Stepl. Use Algorithm 1 to find ^ .

Step2. Input ^ε and initialize ^ω ' and ^ , for all ^ ' ^* , and . Set a proper iteration number R ( R = 1 for fixed ^COj ) and K and proper step sizes ^Sfl and Define «, =<* ² ^ ⁺ ^ '\ S-^ ⁺ W. Set g ^bsa = +oo

for r = 1 to R do

for k = 1 to K do

1) Solve the convex optimization problem in (37) and find ^ ¹ '' ⁽ ^ ^j ^ _^ j≡ c ¹ .

2) Calculate S k using (38). 3) If S ^bes ' > §m , _S et = 8W , = MW _and = W _{, for all} ^ , Mk] = P -∑ _]£C E{pZa _} lklW])}

4) Calculate '

5) Calculate ^ ] = ε - Ε ' _ίθΐ all ^{J C} < .

6) Set [k + ll ^ ( ik] - s _/l d [k]) _{+ aM} λ + 1] = (Λ ] - s,dA _] [k]) ₊ ^ j≡ c .

7^ 7) & <— & + 1

end for a) Set , for all ' , and V ^~ V . b) Estimate mean, ^m ' , and variance, ^V ' , of the random variable ^ ¹ '' ^> ' ^

^J i

m .

ίϋ =

c) Update the value of ' , for all ' ^* , as ^{1 '} . d) ^{r r +} 1.

end for

Step3.

for " = ¹ to T do

1) Solve the convex optimization problem in (39) and find the optimal power allocation, for all j≡ c '* .

2) n <— n + 1

end for

Pseudo Code for Implementing Ergodic Sum-Rate Improvement Algorithm (A Heuristic Sub-Optimal Solution for the optimization problem P3)

To implement the heuristic long-term D2D rate improvement method the following steps may be employed:

In this algorithm, it is assumed that the best cellular match from Algorithms la and lb is known.

In one embodiment, the Lagrange multipliers are calculated using the subgradient method. Time-averaging is used as an approximation for statistical mean to approximate the subgradient values. Using the history of consumed powers over each RB, the constraints in each fading state is updated such that the long-term constraints to be satisfied.

The optimal power allocation for each RB is found such that the achievable sum-rate is improved, satisfying the constraints on the sum-power of the D2D wireless device pair and also the SINR of the interfering cellular devices in the main cell and neighboring cells. In this step, the subgradient values which have been obtained in the previous step are used.

In addition to the features of Algorithms 2a and 2b, the network entity implements Algorithm 3a to approximate the long-term constraints through the use of time-averaging instead of statistical mean. Algorithm 3a is a sub-optimal algorithm, but the computational complexity is less than Algorithm 2a.

In addition to the features of Algorithm 2b, the network entity implements Algorithm 3b to approximate the value of subgradients through the use of time- averaging instead of statistical mean. Algorithm 3b is a sub-optimal algorithm, but the computational complexity is less than the optimal algorithm, i.e., Algorithm 2b.

In Algorithm 3a, T is the number of LTE frames over which a stationary environment for the D2D wireless device can be assumed.

Algorithm 3a

Stepl. Use Algorithm la to find .

Step2. Input e and ω.

For n = 1 to T do

1) Calculate _m ^D _ax [n] = ° _ax - (n - 1)Ε _η→ {∑ _]ε€ρ p¾}.

2) Calculate η' . [n] = η η] + - log ( ne - (n - 1)Ε _η _ ₁ {β ^{ω (ρ} ¾ ^" ¾ ⁾ }) (for

J

ally e C _r ).

3) If∑ec _r i7' N ≤ ¾ ^D axN then

For all j £ C _(% set p _t ^D* [n] = η' . [n].

else

Using the bisection method, find ° ^* [n] and μ[ ^η ] > 0 such that∑ e _{Cj tj} ⁼ ^max and end if

end for

FIG. 5 illustrates an exemplary process (S500) performed by the network entity implementing Algorithm 3a, above. Initially, Algorithm la above is implemented by the network entity to find the best cellular match (step S510).

System parameters e and ω are input (step S520). A counter n, is initialized to 1 (step S530) and it is determined if n is greater than T (step S540). If n is not greater than T, the sum-power limit ¾¾ _x [n] is updated using equation (19) below (step S550). The individual power limit η' . [n + 1] is updated using equation (20) below (step S560). If jeC _] ^" n' _j [n + 1]≤ Ρ^ _χ [η + 1], the optimal power allocation is set as ρ¾ ^* [η] = η'■ [n + 1]. Otherwise, the optimal power allocation p ^* [n] is found by using equation (21) below (step S570). The counter n is incremented (step S580) and the process starting with step S540 repeated.

Alternately, algorithm 3b may be used. In Algorithm 3b, T i _s the number of LTE frames over which we it can be assumed that there is a stationary environment for D2D wireless device.

Algorithm 3b

Step 1. Use Algorithm lb to find ^ .

Step 2. Input ^ε and ^ω ' . Initialize and , for all ^ ' ^* . Set proper step sizes ^Sfl and ^s * .

_Define a _j (σ ² + 7 ₇ °)(σ ² + /,) b _} (σ ² + /°) I _} I ² c _} (σ ² + for " = ¹ to T do

1) Solve the following convex optimization problem in (58) and find ^H , for all ' .

2) Calcul

3) Calculate ^W ^ - ^E "{ ^{j ¾ "} } , for all ^{J' G} μ[η + 1] = (μ[η] - _μ 3μ[η]) _j [n + l] = { _j [n] - s _A d _j [n}) ₊

4) Set ⁺ and ' , for all j C,

end for

Pseudo Code for Implementing Ergodic Sum-Rate Maximization Algorithm (A Heuristic Sub-Optimal Solution for the optimization problem P3 using one-bit feedback information)

To implement long-term sum-rate improvement method, the following steps are employed:

In this algorithm, it is assumed that the best cellular match from Algorithm 1 is known.

The Lagrange multipliers are calculated using the subgradient method. Time- averaging is used as an approximation for statistical mean to approximate the subgradient values. Furthermore, feedback information is used from the interfering cellular device to determine the sign of the subgradient which is related to SINR constraints for the interfering cellular devices.

The optimal power allocation for each RB is found such that the achievable sum-rate is improved satisfying the constraints on the sum-power of the D2D wireless device pair and also the SINR of the interfering cellular wireless devices in the main cell and neighboring cells. In this step, using the obtained values in the previous step, the subgradients are updated.

The details of the proposed algorithm are given in Algorithm 4.

In addition to the features of Algorithm 2b and Algorithm 3b, the network entity implements Algorithm 4 to approximate the value of subgradients through the use of time-averaging instead of statistical mean. Algorithm 4 is a sub-optimal algorithm, but the computational complexity is less than the optimal algorithm, i.e., Algorithm 2b and also the amount of needed feedback for it is less than Algorithm 3b.

In Algorithm 4, T i _s the number of LTE frames over which a stationary environment for D2D wireless device pairs is assumed. Algorithm 4

Step 1. Use Algorithm lb to find ^ .

Step 2. Input ^ε and ^ω > . Initialize and , for all ^ ' ^* . Set step sizes ^s μ" and ¾ . Define ^a > = ^(σ * ⁺ ^ ⁺ , ^b > = ^{(σ* +} ^ ^{1 +} W .

for n = 1 to T do

1) Solve the following convex optimization problem in (58) and find ^H , for all j≡ c '* 2

2) Calculate ^;eC ' 3) Calculate ^" ^^"^ , for all ^ ' ^* , based on received feedback

information from the interfering cellular wireless devices. Considering the fact that Ρ ^χ ^ ^η ^ is a decreasing function of ^^"^ , ^& ^8 ⁿ (^^ ^j W) ^ determined such that there is only an increase in the power over the corresponding RB when the SINR constraint is satisfied for all of the interfering cellular wireless devices.

4) Set ί ^η + ί] = (μ[ ^η ] ~ _/i d [n ) ₊ - s _A sign(dA _j [n]j) _{+ for}

all j≡ c ' _t .

5^ n<r- n + l

end for

Pseudo Code for Implementing Optimal Ergodic Sum-Rate Maximization Algorithm (Algorithm for Finding the Optimal Solution for the Optimization Problem in P5)

To implement long-term sum-rate improvement method, the following steps are employed:

In this algorithm, it is assumed that the best cellular match from Algorithm 1 is known.

The values of Lagrange multipliers are estimated using the subgradient method. The power allocation for each RB is found such that the achievable sum-rate is improved satisfying the constraints on the sum-power of the D2D wireless device pair and also the SINR of the interfering cellular devices in the main cell and neighboring cells. In this step, the Lagrange multiplier values which have been obtained in the previous step are used.

The details of the proposed algorithm are given in Algorithm 5.

The features of Algorithm 5 are similar to Algorithm 2b.

In Algorithm 5, T i _s the number of LTE frames over which a stationary environment for D2D wireless device pairs can be assumed.

Algorithm 5

Step 1. Use Algorithm 1 to find ^ .

Step 2. Input ^ε and initialize ⁰³ ' and ^ , for all ^ ' ^* , and . Set a proper iteration number R ( R = 1 for fixed ^COj ) and K and proper step sizes ^Sfl and ^S . Define «^ + ^ +',) _, b^ + I^ h, c^ + I^l) ^

for r = 1 to R do

for ^k = ¹ to K do

1) Solve the convex optimization problem in (92) and find

j≡ c _t

¹

2) Calculate using (38).

3) If set = ^beS ' = W _and ^λ = ^λ ^ _{ίθΐ ΆΪΪ}

4) Calculate ^;e '

5) Calculate ^] = ε - Ε[ ^β ' " ' _{ίθϊ all} ^{J C} , 6) Set [k + ll^( ik]-s _M d [k]) _{+ aM} λβ + \] = (λ ]- s _A d _] [k]) ₊ j≡ c ¹ .

7) k —k + l

end for

X ^~ . = z ^hest j≡c _t ,.*

a) Set J J , for all ' , and V ^~ V . b) Estimate mean, ^J , and variance, ^; , of the random variable

c) Update the value of ^ω > , for all ^ ' ^* , as ^Vj . d) ^{r r} + 1. end for

Step 3.

for n = 1 to T do

1) Solve the convex optimization problem in (39) and find the optimal power ocation, for all j≡ C

all ' .

2) n <— n + 1

end for

Detailed Formulation and Solution

Ergodic Sum-Rate Maximization

In this section, it is assumed that the ^ th cellular wireless device is the solution for the problem of finding the best cellular match. The resource allocation problem for finding the optimal resource allocation for the new D2D wireless device pair, in order to improve the sum rate, is as follows:

PI: max E{ ]}

or, alternatively as,

PI. max _E {∑ _jeCl log(l+¾¾ (1.1) subject to E{∑ P }≤

Ci (2) σ ' ¹ ' /':. ⁷ (3) where p _tj is the D2D transmitted power, p _{r j} is the received power of the ith cellular wireless device, p is the received power of the kth wireless device over the jth RB where j £ C; and k £ S _j , h _j is the D2D channel coefficient over the j ^th RB (for the new D2D wireless device), I _j is the received interference power from all interfering wireless devices to the new D2D wireless device, and σ ² is noise power, which is assumed is the same over all RB's. In the above, I _j ' and I'[ ^k ^ are defined such that p _j lj and ρ^ ^"* are the received interference power from the new D2D wireless device for the cellular wireless device which uses the j ^th RB and for the k ^th neighboring cellular wireless device (k £ S _j ), respectively. Furthermore, 1° and I?'^ are the interference power the cellular wireless device which uses the j ^th RB and the kth neighboring cellular wireless device (k £ S _j ) receive before admitting the new D2D wireless device, respectively.

It should be noted that Equation 1 above maximizes the sum rate of the D2D wireless device and cellular wireless device and thus has two log terms in the PI formulation. The embodiment of Equation 1.1 above only maximizes the D2D wireless device rate and thus only has a single log term as in the PI a formulation.

The long-term constraint on the sum-power, i.e. (2), may be viewed as a constraint on the battery usage of the D2D wireless device.

The constraints in (3) and (4) ensure that the probability that the SINR is below a target threshold is less than a pre-defined small value, thus assuring a specific long-term QoS for the cellular wireless devices in the main cell and also neighboring cells that use the same RBs as the D2D wireless device pair. Using Markov's inequality: E{S/NR,}

PriS/NR . > C }≤—— —

On the other hand, from the SINR constraint in (3) then

Er(S-V* ₍ > <*Z,m-e _The¾ „ _{cmbe∞nduded} ^EISBfl^d-*).

E.\SINR^ 1 > (1— £)C ⁱ ~ ^k ^

Using the same method it can be shown that ' ^{~ 7,mm} .

Furthermore, the constraints can be simplified to

equivalent to max E{∑ [log(l +

^D ,≥o} .c _; σ +I _j +p _t l _{j j Cl} σ +/,.

or, alternatively, for PI a

ma _{0 E(¾C]} ,„ _{g(1 +} ¾¾ ί iife/eci to E{∑ pf _j }≤

(7)

(8) It should be noted that Equation 6 above maximizes the sum rate of the D2D wireless device and cellular wireless device and thus has multiple log terms in the PI formulation, whereas the embodiment of Equation 6.1 above only maximizes the D2D wireless device rate and thus only has a single log term as in the PI a formulation.

For sufficiently small values of ^ε and large values of ^7,mm (such that = ^jm , t ^m n »i ^ _can b _e approximated as follows: P2: max E{∑log(^ ^ )} subject to E{∑ °

(10) w _here a, =(σ ² + /°)(σ ² ₊ I,) b, =(σ ² + / J) I Λ, I ² _{> c} , =(σ ² + /,)/; _ last constraint in (11) is not a convex constraint. Using the Chernoff bound,

(12)

The inequality is valid for any ' . By adjusting the value of ' , the inequality can be tight. If we have ^{1 ;} then the constraint in (11) will be assured. Thus, the following optimization problem can be proposed:

P3: max E{∑log(^ ^ )}

{p° j≡c _t ^a j ^{+ c} jPt

(13) 3: _{ max E{∑ _eCl log ( 1 + ¾¾} (13.1) subject to E{∑>°

Ci (14) or, alternatively, for P3a

subject to E{∑ _eC; p¾}≤ ^D _ax (14.1)

E{e > > }<ε, je C _{r (15)}

Ε{θ ^ω(ρ ¾ ^" ¾ ⁾ }≤ e, y ^' eC, (15.1)

It should be noted that Equations 13, 14 and 15 relate to maximizing the sum rate of the D2D wireless device and cellular wireless device in the P3 formulation, whereas the embodiment of Equations 13.1, 14.1, and 15.1 above only maximize the D2D wireless device rate, in the P3a formulation.

{p ^D . >0)

The objective function of (13), for · ⁷ , can be upper-bounded as follows

a, +b _i p° _i l ^0g( a +c ° ^}

The inequality comes from the fact that the function ^α ' ί^ ^ι ·ί , for b < c » ^D >0

1 ¹ and ^1,7 , is a decreasing (and convex) function. The upper-bound is b < c ^{D —} 0 ^{D —} 0

achievable if and only if for ^{j < C j} ,^ ^t,j . In other words, ^ ¹ ' ⁷ is the optimal b < c

solution when ^{1 1} if and only the constraint in (14) is satisfied. The sum-power constraint is satisfied if:

E{∑P } =∑ ( ^Pr ^; ^{≥ C} J ^{1 b} j ^{≥ C} J } + ^Pr ^; < ^c ; ) ^E ^W ^{1 ¾} ; < ^c ; »

The individual power constraints are satisfied if : \b _j <c _y }

= Pr{6 _y > c _y I b _j ≥ c _j } + Pr{6 _y < c _y }Ε{β ^~ω ' ^η ' \ b _j < c _y }

< ^■ . (18) Thus, (13) is equivalent to the following optimization problem: subject to ∑P _J E{p?

(20)

P _y E{e ^ι · ⁷ " l¾ _y > _Cy }<i- je _; ,

1) where ^P > 1. \ov(—L LLli )

a _l_ Q n b > c p -Ϊ U

Note that the function ' ' ^t '' , for ^{1 1} and · ⁷ , is a concave

(and increasing) function, thus the Lagrange method can be used to solve (19).

p°. = 0

It can be shown that any solution for (19) is feasible by applying · ⁷ b < c °■ ⁼ 0 b < c when ^{1 1} , for the problem (13). Also, again by applying · ⁷ when ^{1 ]} , the objective function of the two problems are the same. Thus, the two problems (13) and (19) are equivalent. The La range function of (19) can be written as

b < c p°■ = 0

By knowing that for ^{1 1} we have · ⁷ , the Lagrange function also can be written as follows:

U{p°},U _j },M) =∑E{log( ^a j> ^+b j ' , » μ ΐ _Λ .

In an alternate embodiment, the inequality is valid for any ω > 0. If < _e then the constraint (Equation 11) will be assured. Thus, the following optimization problem can be proposed:

subject to tj}≤

'eC;

(22b)

_Ε{θ ^ω(ρ ¾-¾)} < _e , e Q. (22c) The optimization problem in (a) through (c) is a convex optimization problem. The Lagrange multiplier function of (a) through (c) can be written as

/ = y jeci ^e {!°g ^{( 1} + ¾ σ Γ +¥ Ij )}

Wmax -Y E{ _Pt ^D .}) + Aj (€

= V E {log ( 1 + J¾¾ - μρ¾ - ^e ^» <"¾^>}

The Lagrange dual function can be defined as"

g({A _j } , ) = max Ι_({ °. } , μ . } ,//).

≥ ⁰ⁱ (23)

D ^

To find optimal ^ ¹ · ⁷ , for fixed values of > and ^ and for ^ ^e ' , in (23), the following optimization problem needs to be solved for each J :

/> _T ^D _Y (Λ, , //) = arg max log(^ ^J — ) - μρ° - e ' > ' .

J J ^t -J (24) or, alternatively, ρ°/(λ,, ) = arg max log ( 1 + ¾2&) - μρ¾ - λ^Γ^. (24.1) where ^ ¹ · ⁷ ^ is the optimal power allocation for ^ ^J ^ . Note that (24) is only valid for ^{~ Cj} and for ^{< Cj} we have ^ ¹ ·· ⁷ ' ^ ^ . The problem in (24) is a convex optimization problem, and thus the optimal value can be found very efficiently.

Note that equations 24 and 24.1 have slightly different notation in that equation 24 is recast with slightly different variables than the optimization problem set forth in equation 24.1. As a first order approximation of the solution, the approximation

^ ^{+ a)} j{Pt,j Vj) _can ^ _{e use(} j Using this approximation and setting the differentiation of (24) to zero,

ah, -a,c ,

( — — / ><' ' = ⁽ 0A

<" ^{( /} ' ^ »<" "- ^ »

or, alternatively,

\hj\ ² . .

a ² +Ij+\hj\ ² p»j ^ ]

Note that equations 25 and 25.1 have slightly different notation in that equation 25 is recast with slightly different variables than equation 25.1.

In other words,

(<y./t. + )b _j c _j (p? _j ) ² + (<y./t. - ) ⁽ iAb _: -C:)p ^,, _: +((<y./t. + -"A-",' ^' ,) or

*M) ² +fi _JP + > ⁰ equivalently

^A b , +c ; ^Δ b -c ;

y5 _{i =} — ->0 ->0

i and ^ . Summation of the roots of this equation is

! which is negative so there is at least one negative root. Thus, only the greater root can be accepted or otherwise the solution for (24) is zero. Thus:

Note that equations 26 and 26.1 have slightly different notation in that equation 26 is recast with slightly different variables than equation 26.1.

The optimal value for ' and ^ can be found using the following convex optimization problem: min 8({λΛ,μ) subject to A _j > 0, ye C,

μ≥0.

To solve (27), the Subgradient Method can be exploited. To achieve the subgradients, it is noted that:

₈ {{λ },μ) = max L({ _A ° },{λ },μ)> 1({ρ%(^,μ)},{^},μ')

(30)

= ₈ ( _{ λ _ι },μ) ₊ (λ' _ι - _j Xe' _j -P _j Eie"^^ \b, >c _j} ) + ( '- )(P» _ca -P _J E{∑p? ^* (A _J , )\b _J ≥c _J }). Alternatively,

9Wj = ^m n ^ax ^({ ¾}, '·}, ')≥^({ρ^(λ·, )}, '·}, ')

= gifyl ) +∑jeM - + (μ' - μ)(Ρ£ _αχ -

Note that equations 30 and 30.1 have slightly different notation in that equation 30 is recast with slightly different variables than equation 30.1.

By considering the definition of subgradients: dA _J =£ _J ^f - _J E[e"^^ ⁾ \b _J ≥c _J } jeC„

From (17) and (18) the subgradients can be re-written as

Thus, the value of Lagrange multipliers can be updated as follows: A _j [k + l] = (A _j [k] - s dA _j [k]) ₊

M[k + l] = ( i[k] - s dM[k]) ₊ .

(36)

Where k is the iteration number and ^λ and ^μ are step sizes.

Based on the equation in (24), the optimal power allocation in the ^th step can be updated as follows:

_A ^D _y (/l _y [£],//[£]) = arg _m a _X log

(37) and the value of dual function can be updated as follows: y fl + C _y /? _t ^U _y (/l _y [&],//[&])

After solving the equation (37)-(38) for a number of iterations, i.e., K iterations, ^ ^{_ ar} gmiiu g[k] _can ^ _e f _oun( j _an( j (-jjg _va i _{ue G} f optimal Lagrange multipliers may be set as ^ , for all ^ ' ^* , and ^ ^~ ^ . Then, in each channel state, the following optimization problem can be solved to find the optimal power allocation: p, [n] = arg _ma x log(-^ ^J - _^ ) - μ p _y - λ e ^{1 1} .

a _{y + Cy >y}

(39)

Note that considering (33) and (34), the above formulation can only be applied over the time it can be assumed the channel for D2D wireless device pairs is stationary.

Optimizing the value of ^ω ' : The optimal value for ^ω ' may be found such that there is the tightest bound in (12). Thus,

ΡΗ Α ,-≥7 }≤minE{e } < E{e '^·' }

(40) To find the optimal ^{d c0} i (41)

The random variable is defined as ^Xj . The distribution of ^x > is not known before solving the optimization problem. If it is assumed that ^υ ₅ then: + _™ 1

E{x e ^{1 1} } = \ xe ¹ i _^ =e ¹ dx

^J - ₍ 42)

The integral in (42) is the mean value for the Gaussian random variable _y _; . (C0jVj + mj , Vj ) optimal value for ^ω > can be found as

m ,.

J' =

y (43)

Since the distribution of ^j is not known, an iterative method can be proposed

CD =[<¾¾, ί9 ₂ ,· - ; J _ic

in which, starting from an initial point for ' , in each step the

(tn V )

value of ^ω is updated for the next step by estimating ¹ ' ¹ s using the available information in the current step.

An Upper-Bound for the Original Optimization Problem

As discussed above, the Chernoff bound provides a lower bound for the original optimization problem in (9). The provided lower bound can be found by solving a convex optimization problem, i.e., (13). To see how good the lower bound is, a proper upper bound needs to be found for the optimization problem in (9) and the gap between the lower and upper bound considered. In this section, a method for reaching a proper upper bound is provided. Lemma 1 : For any nonnegative integrable random variable z and any positive

Pr{z<a}>l-^- value ^a , ^a .

Pr{z >«}<¾-

Proof: From Markov's inequity it is known that ^a , thus

1 = Pr{z > a} + Pr{z <a}< + Pr{z < a) .

a (44)

Proof: ^{Vr[p ≥} 1> ^} = ^" ^)≤ 0} = Pr^^ ⁷ ^ < 1 } _From

Lemma 1:

Vr{e ⁷ <1}>1

By combining with the Chernoff Bound, for any ^ω > ^{' >} , there is the following: l_E{e ^' " '}<maxl-E{e ^' }≤ Pr{ p°.≥ η . }≤ ,.(p?.

mm E{e }≤E{e

The optimization problem for finding the upper bound can be written follows:

P4: max E{∑log^

{p° j≡c _t ^a j ^{+ c} jPt subject to E{ ^ p } < Ρ _τ D

(48)

-οΡί"(ρ?-η.)

E{ l-e ^{7 l} ' ^{7 7} }≤ε, jeC,.

(49)

Because the power constraint for the upper-bound problem is a concave constraint, the optimization is not a convex problem anymore. A dual problem analysis can be used to find the upper bound. The La range multiplier function of (47) can be written as:

(50)

The Lagrange dual function can be defined as:

g({ _j } ,M) = max L({ _A ^D . } , { 1. } ,//).

^{p ° (51)

D ^

To find optimal ^ ¹ · ⁷ , for fixed values of ⁷ and ^ and for ^e ' , in (51), the following optimization problem needs to be solved for each J :

P,°; a,„)

Note that (52) is not a convex optimization problem. Thus, an extremum- search method needs to be applied to find the global optimum point. After finding the global maximum point, to solve (51), the subgradient method can be exploited.

Optimizing the value of ^ω ' : To find the o timal ^ω ' ^> for the u er bound,

X■ — D — 71■ x

The random variable is defined as ⁷ · ^{7 7} . The distribution of ⁷ is not

) known before solving the optimization problem. If it is assumed that ^{7 ' 7} ' ⁷ , then,

. -ω . -ω

2υ ² +∞ 1 2υ ²

= e ¹ y _/ ^=£ ¹ dy = 0. The integral in (54) is the mean value for the random variable

y j . N(m _; f _rom (54) _s the optimal value for ^ω > can be found as: m .

ώ° ^ρ ' = - -.

(55)

X

Since the distribution of > is not known, an iterative method can be proposed

Δ

ω ₌ [<¾¾ , <¾¾ ,· · ·, D _{LC L} ] ^T

in which, starting from an initial point for ' , in each step the

(tn V )

value of ^ω is updated for the next step by estimating ¹ ' ¹ s using the available information in the current step.

Heuristic Solutions: Time Averaging Instead of Statistical Mean

Calculating the subgradients in (33)-(34) needs statistical averaging over large number of communication channels which is highly computationally complex. To avoid high computational complexity, embodiments of the present disclosure use time averaging instead of statistical mean to calculate the subgradients. To do so, is defined as the time average over ⁿ consecutive samples, i.e. , ^ ^x> ' ¹ ' ^" ' ^x " ' . Using the definition of time averaging, an approximate of the subgradients in (33)-(34) is as follows: dA _j [n] = s - E _n {e ' ^Vi ' ^r ' } j e C _t ,

(56)

n ^D * » ^D* r _n l

where time-averaging is done over random ^1,7 and we define ^1,7 as

a . + b . p.

p° ^* [n] = arg _ma x logH ¾ - μ[η] p°. - λ _} [n]e ' .

„D _> o a . + c . p"

Ρ'· ^{7 1 1 t} (58)

Again, the Lagrange multipliers are updated as (35)-(36).

Heuristic Solutions: One Bit Feedback Information

To calculate the approximation in (56), information from all interfering cellular devices needs to be received. To decrease the amount of feedback information, each interfering cellular device can send one bit feedback information to show that up to the time of sending the feedback the SINR constraint is satisfied or violated. Based on this feedback information, a D2D wireless device can increase its power over the corresponding RB in order to maximize the objective function or decrease its power in order to satisfy the SINR constraint for interfering cellular devices. When the received feedback information is suggesting different power change directions, the priority goes to decreasing power over the corresponding RB to be sure that all of the SINR constraints are satisfied. In other words, considering the fact that P ^t J ^ ^j ' ^ i _{s a} decreasing function of , the following updating process can be used for the value of Lagrange multipliers:

A _j [n + l] = (A _j [n] - s &ign(dA _j [n])) ₊ j e C, . ^

Using (59), sign information is used to decide about the direction of change in the power over each RB. The updating process for ^ is the same as (36).

The, idea of the heuristic method to apply time-averaging approximation in the primal domain can be applied to solve the problem proposed in this disclosure, i.e.,

(1)·

Heuristic Solution

Algorithms for Finding the Best Cellular Match

Calculation of subgradients has a very high complexity and needs full information about the statistics of the channels between D2D wireless device pairs and also all interference channels. Instead of using the subgradient method to solve the dual problem, Lagrange multipliers can be directly found by approximating the primal problem. Considering the fact that μ is related to the constraint E{∑- _eC; ρ ≤

^max' ^{m eacn ste} P ^η + 1] ^can be found by connecting it to E _n+1 {∑ ec _; Pt } — ^max- It can be shown that E _n+1 {x} = ^-j- (x[n + 1] + nE _n {x}). Thus, the sum power constraint in (11) can be written as

Similarly, the individual power constraints in (33) can be approximated as p _t °/ [n + 1]≤ j [n + 1] +—log ( (n + l)e

(61)

- ηΕ _η {θ ^ω ^Γ^}) = η' . [η + 1].

If∑e _/ ' j [n + 1] ≤ Pmax [ ⁿ + 1] it ^can be shown that the optimal solution is P _t M ⁼ ' j i ⁿ + 1]· Otherwise, after applying the KKT optimality condition to the primal problem:

Note that μ[ ^η ] may be which can be achieved using the bisection method.

Algorithms for Finding the Best Cellular Match

For the proposed method in the previous section, it is assumed that it is known that each D2D wireless device pair is matched with a specific cellular wireless device and that the power allocation problem has been solved based on this assumption. To obtain a complete scheduling method, another algorithm for choosing the best cellular match is proposed. Using the optimal method proposed in the previous sections, the best cellular match can be chosen through solving separate optimization problems for all cellular wireless devices in the cell. However, this has a high computational complexity and needs full statistics of all involved channels. In reality, complete information about the channel realizations is often not known beforehand, and, also, time constraints may limit the ability to gather full channel statistics. Thus, to find the best cellular match, a sub-optimal algorithm based on solving the following optimization problem is

subject to a; £ {0,1}, ϊ = 1,2, · ·· , Ν (63-2) N

i _P » ≤P» _ax (63-4) i=i jeci (63-5)

In (63-1) through (63-5), average values are used to find the best cellular match for the D2D wireless device pair. It is a reasonable choice due to the lack of full statistics of all channels. It is defined that η = ηΊ +— log ( e), for all j £ Q.

Assuming the Z ^th cellular wireless device is the best cellular match, the solution for the optimization problem in (19) can be found using a KKT optimality condition as:

Case 1)∑ _jeCl rf]≤ P° _ax : p¾ = η] (for ally £ Q).

Case 2)∑ _jeQ η÷ > P° _ax :

where > 0 may be found such that ec _; Pt ⁼ ^max- Because pj is a decreasing function of μ^ ⁰ -*, the bisection method can be used to efficiently find the optimal μ (° If the new D2D wireless device pair is matched with the Z ^th cellular wireless device, the achievable rate for the new D2D wireless device pair will be:

After finding R _h for all I £ {1,2,· · ·, N], the D2D wireless device pair is matched with the P" ¹ cellular wireless device, where = arg max ff ₍ .

In accordance with the disclosure:

The long-term throughput of D2D wireless device pairs is improved under a long-term sum-power constraint and long-term individual power constraints over each RB.

A long-term constraint on the sum-power of D2D wireless device pairs is assured, which is directly related to the battery energy consumption of D2D wireless device pairs. For cellular wireless devices that share RBs with the D2D wireless device pair, by applying individual power constraints, a specific SINR level is achieved with a preset probability.

The method and arrangements according to some embodiments of the present disclosure are applicable to a realistic cellular environment, i.e., multiple cellular and D2D nodes in the network, resource reuse factor (effects from/to the neighboring cells), and access to multiple RBs.

The method and arrangements according to some embodiments of the present disclosure are applicable to both uplink and downlink resource sharing at the same time. Due to the localized nature of D2D communication, as well as low power transmission for D2D wireless device pairs, only the resource allocation problem for D2D wireless device pairs is solved. The resource allocation and power control of existing wireless devices in the network are not modified.

The method and arrangements according to some embodiments of the present disclosure provide an efficient sub-optimal algorithm for finding the best cellular match for the D2D wireless device transmissions.

FIG. 6 is a block diagram of an exemplary network entity 20 configured to schedule a D2D device using RBs for existing cellular devices 16 in wireless network. In one embodiment, network entity 20 is a base station that has been modified to implement the features and functions described herein. In one or more embodiments, network entity 20 includes processing circuitry 22, memory 24, a processor 26, and a communications interface 28. Memory 24 contains instructions that, when executed by processor 26, configure processor 26 to perform one or more functions described with respect to FIGS. 8 and 9 and herein. In addition to a traditional processor and memory, processing circuitry 22 may comprise integrated circuitry for processing and/or control, e.g., one or more processors and/or processor cores and/or FPGAs (Field Programmable Gate Array) and/or ASICs (Application Specific Integrated Circuitry). Processor 26 may be configured to access (e.g., write to and/or reading from) memory 24, which may comprise any kind of volatile and/or non- volatile memory, e.g., cache and/or buffer memory and/or RAM (Random Access Memory) and/or ROM (Read-Only Memory) and/or optical memory and/or EPROM (Erasable Programmable Read-Only Memory). Such memory 24 may be configured to store code executable by processor 26 and/or other data, e.g., data pertaining to communication, e.g., configuration and/or address data of nodes, etc.

Processing circuitry 22 may be configured to control any of the methods and/or processes described herein and/or to cause such methods and/or processes to be performed, e.g., by network entity 20. Corresponding instructions may be stored in the memory 24, which may be readable and/or readably connected to processor 26. In other words, processing circuitry 22 may comprise a microprocessor and/or microcontroller and/or FPGA (Field-Programmable Gate Array) device and/or ASIC (Application Specific Integrated Circuit) device.

Memory 24 includes instructions that, when executed by processor 26, configure processor 26 to determine a power allocation for each of the RBs based on achieving a long term target rate for the D2D wireless device 14. This determination may be performed by power allocation calculator 30 along with processor 26.

Processor 26 may also be configured to schedule the D2D wireless device 14 based on the determined power allocation. This scheduling function may be performed by scheduler 32 along with processor 26.

In one or more embodiments, processor 26 is further configured to determine a cellular wireless device 16 of the active cellular wireless devices to be matched with the D2D wireless device 14 pair, allow the D2D wireless device 14 to share all RBs allocated to the cellular wireless device 16 that is matched with the D2D wireless device 14 pair, determine a power allocation for each RB of the allocated RBs based on achieving a long term target rate for the D2D wireless device 14 and the cellular wireless device 16 to which the D2D wireless device 14 pair is matched, and schedule the D2D wireless device 14 based on the allocated RBs based on the determined power allocation.

In one or more embodiments, achieving the long term target rate for the D2D wireless device 14 and the cellular device 16 to which the D2D wireless device 14 pair is matched satisfies constraints on a long term power of the D2D wireless device 14 and a SINR of interfering cellular wireless devices 16 in one of a main cell and a neighboring cell.

In one or more embodiments, processor 26 is further configured to obtain feedback information from each interfering cellular device 16 in one of a main cell and a neighboring cell, and communications interface 28 is further configured to at least one of forwarding the feedback information to the D2D wireless device 14 and instructing the D2D wireless device 14 to adjust its power over each RB based on the feedback information.

In one or more embodiments, if the feedback information indicates conflicting power adjustments over each RB, processor 26 is further configured to instruct the D2D wireless device to at least one of decrease power over each RB in order to satisfy constraints on a SINR of interfering cellular wireless devices 16 in one of a main cell and a neighboring cell and increase power over each RB in order to satisfy constraints on a SINR of interfering cellular wireless devices 16 in one of a main cell and a neighboring cell. In one or more embodiments, the feedback information is comprised of one data bit.

In one or more embodiments, adjusting the power over each RB includes one of increasing the power over each RB which satisfies constraints on long term power, and decreasing the power over each RB which satisfies constraints on a SINR of interfering cellular wireless devices 16 in one of a main cell and a neighboring cell.

In one or more embodiments, processor 26 is further configured to determine a sign of a subgradient value which is related to SINR constraints of interfering cellular wireless devices 16 in one of a main cell and a neighboring cell, the determining based the feedback information.

In one or more embodiments, processor 26 is further configured to use time averaging as an approximation for statistical mean to approximate the subgradient value. In one or more embodiments, processor 26 is further configured to calculate a target level of power over each RB of the allocated RBs to meet a time averaged, SINR for an interfering cellular wireless device 16 in one of a main cell and a neighboring cell. In one or more embodiments, wherein the target level of power is calculated to meet the time averaged SINR with a pre-specified probability. In one or more embodiments, processor 26 is further configured to use average channel measurements over a predetermined period of time to determine the cellular wireless device 16 to be matched with the D2D wireless device 14 pair.

FIG. 7 is a block diagram of an alternative network device configured to schedule a D2D wireless device using RBs for existing cellular devices 16 in a wireless network. A network entity 30 is configured to schedule a D2D wireless device 14 using RBs of active cellular wireless devices 16 in a wireless network. In one embodiment, network entity 30 includes a communications module 38 and a processing module 34. Network entity 30 also includes a power allocation module 36 configured to determine a power allocation for each of the RBs based on achieving a long term target rate for the D2D wireless device 14 and the active cellular wireless devices 16 and a scheduling module 38 configured to schedule the D2D wireless device 14 based on the determined power allocation.

FIG. 8 is a flowchart illustrating an exemplary process (S800) for scheduling a D2D wireless device 14 using RBs of active cellular wireless devices 16 in a wireless network, according to the principles of the present disclosure. The method includes determining a power allocation for each of the RBs based on achieving a long term target rate for the D2D wireless device 14 and the active cellular wireless devices 16 (block S810) and scheduling the D2D wireless device 14 based on the determined power allocation (block S820). These functions may be performed by processor 26 of network entity 20.

FIG. 9 is a flowchart illustrating another embodiment of an exemplary process (S900) for scheduling a D2D wireless device 14 using RBs of active cellular wireless devices 16 in a wireless network according to the principles of the present disclosure. In FIG. 9, it is determined, by processor 26, that a cellular wireless device 16 of active cellular wireless devices is to be matched with a D2D wireless device 14 pair (block S910). The D2D wireless device 14 is allowed to share all RBs allocated to the cellular wireless device 16 that is matched with the D2D wireless device 14 pair (block S920). This can also be performed by processor 26 of network entity 20. Power allocation calculator 30 either alone or in conjunction with processor 26 determines the power allocation for each RB of the allocated RBs based on achieving a target rate for the D2D wireless device 14 and the cellular wireless device 16 to which the D2D wireless device 14 pair is matched (block S930). Scheduler 32 either alone or in conjunction with processor 26 schedules the D2D wireless device 14 based on the allocated RBs based on the determined power allocation (block S940).

In one or more embodiments of the processes illustrated in FIG. 8 and FIG. 9, achieving the target rate for the D2D wireless device 14 and the cellular device 16 to which the D2D wireless device 14 pair is matched satisfies constraints on a power of the D2D wireless device 14 and a SINR of interfering cellular wireless devices 16 in one of a main cell and a neighboring cell.

In one or more embodiments, the process further includes obtaining feedback information from each interfering cellular device 16 in one of a main cell and a neighboring cell, and at least one of forwarding the feedback information to the D2D wireless device 14 and instructing the D2D wireless device 14 to adjust power over each RB based on the feedback information. This function may be performed by processor 26 of network entity 20.

In one or more embodiments, if the feedback information indicates conflicting power adjustments over each RB, the process further includes instructing the D2D wireless device 14 to at least one of decrease power over each RB in order to satisfy constraints on a SINR of interfering cellular wireless devices 16 in one of a main cell and a neighboring cell and increase power over each RB in order to satisfy constraints on a SINR of interfering cellular wireless devices 16 in one of a main cell and a neighboring cell. This function may be performed by processor 26 of network entity 20. In one or more embodiments, the feedback information is comprised of one data bit.

In one or more embodiments, the power over each RB includes one of increasing the power over each RB which satisfies constraints on power, and decreasing the power over each RB which satisfies constraints on a SINR of interfering cellular wireless devices 16 in one of a main cell and a neighboring cell. This function may be performed by processor 26 of network entity 20.

In one or more embodiments, the process further includes determining a sign of a subgradient value which is related to SINR constraints of interfering cellular wireless devices 16 in one of a main cell and a neighboring cell, the determining based on the feedback information. In one or more embodiments, the process further includes using time averaging as an approximation for statistical mean to approximate the subgradient value. These functions may be performed by processor 26 of network entity 20.

In one or more embodiments, the process further includes calculating a target level of power over each RB of the allocated RBs to meet a time averaged SINR for an interfering cellular wireless device 16 in one of a main cell and a neighboring cell. In one or more embodiments, the target level of power is calculated to meet the time averaged SINR with a pre-specified probability. In one or more embodiments, the process includes using average channel measurements over a predetermined period of time to determine the cellular wireless device 16 to be matched with the D2D wireless device 14 pair. These functions may be performed by processor 26 of network entity 20.

Although the disclosure describes implementing the process using a processor and a memory, embodiments are not limited to such. It is contemplated that embodiments performing the functions and calculations can be implemented using programmable gate arrays (PGAs), application specific integrated circuits (ASICs), and the like. Further, although embodiments are described using a base station, it is contemplated that the process steps can be performed in other network entities and even distributed across multiple network entities.

As will be appreciated by one of skill in the art, the concepts described herein may be embodied as a method, data processing system, and/or computer program product. Accordingly, the concepts described herein may take the form of an entirely hardware embodiment, an entirely software embodiment or an embodiment combining software and hardware aspects all generally referred to herein as a "circuit" or "module." Furthermore, the disclosure may take the form of a computer program product on a tangible computer usable storage medium having computer program code embodied in the medium that can be executed by a computer. Any suitable tangible computer readable medium may be utilized including hard disks, CD-ROMs, electronic storage devices, optical storage devices, or magnetic storage devices.

Some embodiments are described herein with reference to flowchart illustrations and/or block diagrams of methods, systems and computer program products. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer (to thereby create a special purpose computer), special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks.

These computer program instructions may also be stored in a computer readable memory or storage medium that can direct a computer or other

programmable data processing apparatus to function in a particular manner, such that the instructions stored in the computer readable memory produce an article of manufacture including instruction means which implement the function/act specified in the flowchart and/or block diagram block or blocks.

The computer program instructions may also be loaded onto a computer or other programmable data processing apparatus to cause a series of operational steps to be performed on the computer or other programmable apparatus to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide steps for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks.

It is to be understood that the functions/acts noted in the blocks may occur out of the order noted in the operational illustrations. For example, two blocks shown in succession may in fact be executed substantially concurrently or the blocks may sometimes be executed in the reverse order, depending upon the functionality/acts involved. Although some of the diagrams include arrows on communication paths to show a primary direction of communication, it is to be understood that

communication may occur in the opposite direction to the depicted arrows.

Computer program code for carrying out operations of the concepts described herein may be written in an object oriented programming language such as Java® or C++. However, the computer program code for carrying out operations of the disclosure may also be written in conventional procedural programming languages, such as the "C" programming language. The program code may execute entirely on the user's computer, partly on the user's computer, as a stand-alone software package, partly on the user's computer and partly on a remote computer or entirely on the remote computer. In the latter scenario, the remote computer may be connected to the user's computer through a local area network (LAN) or a wide area network (WAN), or the connection may be made to an external computer (for example, through the Internet using an Internet Service Provider).

Many different embodiments have been disclosed herein, in connection with the above description and the drawings. It will be understood that it would be unduly repetitious and obfuscating to literally describe and illustrate every combination and subcombination of these embodiments. Accordingly, all embodiments can be combined in any way and/or combination, and the present specification, including the drawings, shall be construed to constitute a complete written description of all combinations and subcombinations of the embodiments described herein, and of the manner and process of making and using them, and shall support claims to any such combination or subcombination.

It will be appreciated by persons skilled in the art that the embodiments described herein are not limited to what has been particularly shown and described herein above. In addition, unless mention was made above to the contrary, it should be noted that all of the accompanying drawings are not to scale. A variety of modifications and variations are possible in light of the above teachings without departing from the scope of the following claims.