The US equity exchange market is organized as a National Market System, enforcing price priority across exchanges, but otherwise allowing competition for order flow among exchanges. This flexibility has naturally evolved to a market where exchanges have varying quality and cost of execution. To meet the obligation for best execution, a broker must employ a strategy for selecting the exchange to which limit orders are placed. We consider a market consisting of exchanges with different pricing and priority schemes, and derive a theoretical model to estimate the delay until execution of limit orders. We estimate model parameters from quote and trade data of stocks in the Russell 1000 index, and use them to evaluate expected delay per exchange. We show that inverted cost exchanges and price-size priority exchanges offer improved performance over short time intervals, while traditional and price-time priority exchanges offer improved performance over longer time intervals. We observe that while exchanges with large market share may have high market order liquidity, they may in fact have low limit order liquidity. Low limit order liquidity in turn leads to low execution quality of algorithmic orders. For time-sensitive algorithmic orders, we show a trade-off between execution quality and cost, and show exchanges on an efficient frontier for each stock that achieves good trade-off performance given current exchange pricing.

In Dedicated Short Range Communications (DSRC) based vehicular networking, each vehicle periodically broadcasts control updates (that contain location and speed information etc.) to its neighbors, as a key component of traffic management and safety applications. The effectiveness of such a broadcast feature can be measured by two metrics: (1) the efficiency, or the average rate (number of nodes per sec) to which a source can deliver its broadcast packets, and (2) the reliability, or the average number of nodes that receive a specific transmission successfully. We demonstrate theoretical limits to and achievable tradeoffs between efficiency and reliability for a linear network under Rayleigh fading links. We then provide power control and congestion control strategies that maximize broadcast efficiency. A strategy that achieves near-optimal broadcast efficiency when the network nodes have high mobility is also described. Ns-2 simulations are used to validate our analytical results.

Timer-based mechanisms are often used in several wireless systems to help a given (sink) node select the best helper node among many available nodes. Specifically, a node transmits a packet when its timer expires, and the timer value is a function of its local suitability metric. In practice, the best node gets selected successfully only if no other node's timer expires within a `vulnerability' window after its timer expiry. In this paper, we provide a complete closed-form characterization of the optimal metric-to-timer mapping that maximizes the probability of success for any probability distribution function of the metric. The optimal scheme is scalable, distributed, and much better than the popular inverse metric timer mapping. We also develop an asymptotic characterization of the optimal scheme that is elegant and insightful, and accurate even for a small number of nodes.

Reliable and timely multi-hop propagation of messages among vehicles is essential for a safer and greener transportation system. Various broadcast-based forwarding strategies are envisioned for infrastructure-less vehicle-to-vehicle (v2v) communications. This paper proposes a prioritized broadcast contention control (PBCC) module/layer that provides reliable and low latency multi-hop connection. The PBCC forwarding algorithm optimizes the back-off distribution to improve the probability of successful broadcast and prioritizes forwarders based on location information. This module can be implemented in WAVE devices with minimum system modification. We integrate simple vehicular mobility models into ns-2 and implement a WAVE/802.11p communication protocol stack. Extensive simulations demonstrate PBCC's superiority in multi-hop delay.

In a vehicular network, every vehicle broadcasts update messages that contain location and speed information periodically to its one hop neighbors. The broadcast efficiency measures the average rate at which a vehicle receives these packets from any of its neighbors. As the node density increases, heightened interference lowers broadcast efficiency if congestion control mechanism is not used. In this paper, we analyze the broadcast efficiency under Rayleigh fading channel, and provide congestion control and power control strategies that maximize the efficiency. A worst-case guaranteed strategy achieving at least 95% of the optimal is also provided for cases when the network nodes have high mobility. Ns-2 simulations show that our analytical results accurately predict the system dynamic.

Timer-based mechanisms are often used to help a given (sink) node select the best helper node from among many available nodes. In these, a node transmits a packet when its timer expires. The timer value is a monotone non-increasing function of its local suitability metric, which ensures that the best node is the first to transmit and is selected successfully if no other node's timer expires within a 'vulnerability' window after its timer expiry and so long as the sink can hear the available nodes. In this paper, we show that the optimal metric-to-timer mapping that (i) maximizes the probability of successful selection or (ii) minimizes the average selection time subject to a minimum constraint on the probability of success, maps the metric into a set of discrete timer values. We specify, in closed-form, the optimal scheme as a function of the maximum selection duration, the vulnerability window, and the number of nodes. An asymptotic characterization of the optimal scheme turns out to be elegant and insightful. For any probability distribution function of the metric, the optimal scheme is scalable, distributed, and performs much better than the popular inverse metric timer mapping. It even compares favorably with splitting-based selection, when the latter's feedback overhead is accounted for.

Relay selection for cooperative communications promises significant performance improvements, and is, therefore, attracting considerable attention. While several criteria have been proposed for selecting one or more relays, distributed mechanisms that perform the selection have received relatively less attention. In this paper, we develop a novel, yet simple, asymptotic analysis of a splitting-based multiple access selection algorithm to find the single best relay. The analysis leads to simpler and alternate expressions for the average number of slots required to find the best user. By introducing a new `contention load¿ parameter, the analysis shows that the parameter settings used in the existing literature can be improved upon. New and simple bounds are also derived. Furthermore, we propose a new algorithm that addresses the general problem of selecting the best Q ¿ 1 relays, and analyze and optimize it. Even for a large number of relays, the scalable algorithm selects the best two relays within 4.406 slots and the best three within 6.491 slots, on average. We also propose a new and simple scheme for the practically relevant case of discrete metrics. Altogether, our results develop a unifying perspective about the general problem of distributed selection in cooperative systems and several other multi-node systems.

A common and practical paradigm in cooperative communication systems is the use of a dynamically selected "best" relay to decode and forward information from a source to a destination. Such systems use two phases - a relay selection phase, in which the system uses transmission time and energy to select the best relay, and a data transmission phase, in which it uses the spatial diversity benefits of selection to transmit data. In this paper, we derive closed-form expressions for the overall throughput and energy consumption, and study the time and energy trade-off between the selection and data transmission phases. To this end, we analyze a baseline non-adaptive system and several adaptive systems that adapt the selection phase, relay transmission power, or transmission time. Our results show that while selection yields significant benefits, the selection phase's time and energy overhead can be significant. In fact, at the optimal point, the selection can be far from perfect, and depends on the number of relays and the mode of adaptation. The results also provide guidelines about the optimal system operating point for different modes of adaptation. The analysis also sheds new insights on the fast splitting-based algorithm considered in this paper for relay selection.

A common and practical paradigm in cooperative communications is the use of a dynamically selected 'best' relay to decode and forward information from a source to a destination. Such a system consists of two core phases: a relay selection phase, in which the system expends resources to select the best relay, and a data transmission phase, in which it uses the selected relay to forward data to the destination. In this paper, we study and optimize the trade-off between the selection and data transmission phase durations. We derive closed-form expressions for the overall throughput of a non-adaptive system that includes the selection phase overhead, and then optimize the selection and data transmission phase durations. Corresponding results are also derived for an adaptive system in which the relays can vary their transmission rates. Our results show that the optimal selection phase overhead can be significant even for fast selection algorithms. Furthermore, the optimal selection phase duration depends on the number of relays and whether adaptation is used.

Relay selection for cooperative communications has attracted considerable research interest recently. While several criteria have been proposed for selecting one or more relays and analyzed, mechanisms that perform the selection in a distributed manner have received relatively less attention. In this paper, we analyze a splitting algorithm for selecting the single best relay amongst a known number of active nodes in a cooperative network. We develop new and exact asymptotic analysis for computing the average number of slots required to resolve the best relay. We then propose and analyze a new algorithm that addresses the general problem of selecting the best Q ges 1 relays. Regardless of the number of relays, the algorithm selects the best two relays within 4.406 slots and the best three within 6.491 slots, on average. Our analysis also brings out an intimate relationship between multiple access selection and multiple access control algorithms.

Relays play an important role for increasing rate and reducing energy consumption of wireless networks. In this paper we consider a three-node network (source, relay, destination) in which we want to minimize total energy consumption for a given transmission rate. We analyze and optimize the Split-Combine-Relaying (SCR) protocol that for many typical parameter settings performs better than traditional decode-and- forward. SCR splits a data packet into two fragments, which are then transmitted in two phases. In the first phase of transmission, the source sends the first fragment to the relay. In the second phase of the transmission, the source sends the second fragment to the destination, while, at the same time, the relay forwards the first fragment to the destination. We provide an optimization framework to decide the amount of data in each fragment, the amount of time spent in each of the phases, and the corresponding transmission powers. We also show that an extension of SCR that employs Slepian-Wolf coding of the fragments leads to further reduction of energy consumption.

Many wireless applications demand a fast mechanism to detect the packet from a node with the highest priority (ldquobest noderdquo) only, while packets from nodes with lower priority are irrelevant. In this paper, we introduce an extremely fast contention-based multiple access algorithm that selects the best node and requires only local information of the priorities of the nodes. The algorithm, which we call variable power multiple access selection (VP-MAS), uses the local channel state information from the accessing nodes to the receiver, and maps the priorities onto the receive power. It is based on a key result that shows that mapping onto a set of discrete receive power levels is optimal, when the power levels are chosen to exploit packet capture that inherently occurs in a wireless physical layer. The VP-MAS algorithm adjusts the expected number of users that contend in each step and their respective transmission powers, depending on whether previous transmission attempts resulted in capture, idle channel, or collision. We also show how reliable information regarding the total received power at the receiver can be used to improve the algorithm by enhancing the feedback mechanism. The algorithm detects the packet from the best node in 1.5 to 2.1 slots, which is considerably lower than the 2.43 slot average achieved by the best algorithm known to date.

Contention-based multiple access is a crucial component of many wireless systems. Multiple-packet reception (MPR) schemes that use interference cancellation techniques to receive and decode multiple packets that arrive simultaneously are known to be very efficient. However, the MPR schemes proposed in the literature require complex receivers capable of performing advanced signal processing over significant amounts of soft undecodable information received over multiple contention steps. In this paper, we show that local channel knowledge and elementary received signal strength measurements, which are available to many receivers today, can actively facilitate multi-packet reception and even simplify the interference canceling receiver's design. We introduce two variants of a simple algorithm called dual power multiple access (DPMA) that use local channel knowledge to limit the receive power levels to two values that facilitate successive interference cancellation. The resulting receiver structure is markedly simpler, as it needs to process only the immediate received signal without having to store and process signals received previously. Remarkably, using a set of three feedback messages, the first variant, DPMA-Lite, achieves a stable throughput of 0.6865 packets per slot. Using four possible feedback messages, the second variant, turbo-DPMA, achieves a stable throughput of 0.793 packets per slot, which is better than all contention algorithms known to date.

In many wireless applications, it is highly desirable to have a fast mechanism to resolve or select the packet from the user with the highest priority. Furthermore, individual priorities are often known only locally at the users. In this paper we introduce an extremely fast, local-information-based multiple access algorithm that selects the best node in 1.8 to 2.1 slots, which is much lower than the 2.43 slot average achieved by the best algorithm known to date. The algorithm, which we call Variable Power Multiple Access Selection (VP-MAS), uses the local channel state information from the accessing nodes to the receiver, and maps the priorities into the receive power. It is inherently distributed and scales well with the number of users. We show that mapping onto a discrete set of receive power levels is optimal, and provide a complete characterization for it. The power levels are chosen to exploit packet capture that inherently occurs in a wireless physical layer. The VP-MAS algorithm adjusts the expected number of users that contend in each step and their respective transmission powers, depending on whether previous transmission attempts resulted in capture, idle channel, or collision.

Contention-based multiple access is a crucial component of many wireless systems. It is known that using interference cancellation techniques to receive and decode multiple packets that arrive simultaneously can improve the efficiency of multiple access. However, such multi-packet reception (MPR) schemes proposed in the literature require complex receivers capable of performing advanced signal processing over significant amounts of soft undecodable information received over multiple contention steps. In this paper, we show that local channel knowledge and elementary received signal strength measurements, which are made by many receivers today, can actively facilitate multi-packet reception and even simplify the interference canceling receiver's design. We introduce a simple algorithm called turbo-dual power multiple access (turbo-DPMA) that uses local channel knowledge to limit the receive power levels to two discrete values that are carefully chosen to facilitate successive interference cancellation. As we shall see, limiting the receive power in such a manner not only facilitates the simultaneous reception of up to two packets, but it also enables the receiver to derive additional useful information about the contending users from its received signal strength indicator. The resulting receiver structure is markedly simpler, as it needs to process only the immediate received signal, without having to store and process signals received previously. Even more remarkably, the turbo-DPMA is stable for packet arrival rates as high as 0.793 packets/slot, which is significantly better than all the contention algorithms known to date.

This paper considers a multi-hop network in which relay nodes cooperate to minimize the total energy consumed in transmitting a (unicast) packet from a source to a destination. We propose the Progressive Accumulative Routing (PAR) algorithm, which progressively performs relay discovery, relay ordering and relay power allocation in a distributed manner, such that each relay node only needs local information. We assume Destination Energy Accumulation, in which the destination accumulates the energy of multiple received copies of a packet, each of which is too weak to be reliably decoded by itself, while the lower complexity relay nodes use a decode-and-forward approach. We also provide a closed-form analysis of the energy-savings achieved by the PAR when a relay node is added to an already existing DEA route. Simulations verify that the algorithm considerably reduces the total energy consumption, and can be implemented efficiently.

We propose a set of distributed rate control algorithms for the reverse-link of CDMA systems using a pricing mechanism. In the derivation, we assume that the base station broadcasts a real-valued feedback in order to control the reverse activity level. In addition, we assume that the access terminals are able to transmit data at any rate within a finite range, and that the transmission power is a linear function of the transmission rate. For a specific utility function, we show that the proposed algorithm achieves social optimality, satisfies an interference power constraint, and exhibits desirable short- and long-term fairness behaviors. We then modify this algorithm so that it can be applied to the case when the transmission power is a convex function of the transmission rate. Next, we consider the case that the feedback parameter is a single reverse activity bit, and the underlying rates are elements of a discrete set of admissible rates. This scenario is similar to that of the IS-856 standard. We further modify our algorithms so that they can be applied to this system setup, and verify the performance using numerical simulations. It is demonstrated that our algorithms exhibit short- and long-term fairness behavior for this realistic scenario.

This paper considers a sensor network where relay nodes cooperate in order to minimize the total energy consumption for the unicast transmission of a message from a single source to a single destination. We assume Destination Energy Accumulation, i.e., the destination can accumulate the energy of multiple copies of the message, each of which is too weak to be reliably decoded by itself, while the relay nodes use a decode-and-forward approach. We propose the Progressive Accumulative Routing (PAR) algorithm, which performs relay discovery, relay ordering and power allocation in a distributed manner so that each relay node only needs information about its neighboring nodes. Simulations verify that the algorithm considerably reduces the total energy consumption, and can be implemented efficiently. Furthermore, it performs close to the optimal DEA route with high probability.

We propose a new distributed rate control algorithm for the reverse link of CDMA systems. Specifically, when the statistics of packet arrivals are known locally to each access terminal (AT), this new algorithm aims to provide a means to control the relative delay that each AT experiences. For this algorithm, assuming that the arrival process is Poisson and stationary, it is shown through simulations that all ATs experience an equal amount of average delay when the system is underloaded, and the same packet drop probability when the system is over-loaded. Furthermore, we propose a modification to the algorithm that gives priority to some desired ATs, and reduces their relative average delay. Finally, simulation results indicate that the algorithm achieves similar short-term average delay even when the packet arrival process is not stationary.

We consider an online, processor sharing system with a single server in a packet-switched network where the processor multiplexes packets from multiple input ports onto the same output link. Under a fluid model, in which incoming data is treated as infinitely divisible, the multiplexer allocates its output capacity to serve fractions of packets from all input ports simultaneously (which we call a fluid policy). However, due to the packet nature of the network traffic, a multiplexer scheduler must approximate this fluid policy by a schedule in which only whole packets are sent (which we call a packetized policy). We assume that at each time instant, the aggregate service rate demanded by a fluid policy is no greater than the output link capacity. Then, for a single server with N input ports, and a scheduler using speedup s of at least 2 and a lookahead window of L/spl ges/0 time steps, we prove bounds on worst-case maximum additional delay D. In particular, we show that ([Ne/sup -s/]-L-2)/sup +//spl les/D min {([Ne/sup 1-s/]-L)/sup +/, [Ne/sup -s/]}. In the case when no lookahead is used (L=0), a tighter bound can be obtained: ([Ne/sup -s/]-2)/sup +//spl les/D/spl les/[Ne/sup -s/}.

Optimum and suboptimum scheduling schemes are proposed in the uplink of array antenna systems. We assume that once a user is permitted to transmit the data, the user transmits the data using the maximum power, and adjusts the transmission bit rate so that the energy-per-bit-to-interference-plus-noise-density ratio should be equal or higher than a threshold. In this system model, we consider an optimization problem: How many and which users should be selected to transmit their data at a time in order to maximize the throughput? Based on the analysis on the complexity of the optimum scheme, we propose another optimum scheme having reduced complexity. To reduce the complexity further, we also propose three suboptimum scheduling schemes by limiting the number of users simultaneously transmitting, by choosing the users with higher channel gains, and by partitioning a cell into multiple parts. In circular and linear arrays, the performance results of all the proposed schemes are presented and compared.