Bastian Katz
email: bastian.katz@kit.edu

Markus Völker
email: markus.voelker@kit.edu

Dorothea Wagner
email: dorothea.wagner@kit.edu

Energy Efficient Scheduling with Power Control for Wireless Networks

Scheduling of transmissions is one of the most fundamental problems in the context of wireless networks. In this article, we consider the problem of computing power efficient schedules with high throughput. We answer the open question concerning the complexity of scheduling with power control in the SINRG model of interference. Based on a novel scheme for dynamic computation of optimum transmission powers in feasible schedules, we introduce a new and efficient heuristic for finding good schedules along the tradeoff between throughput and energy efficiency in the physical SINR model. Since our algorithms do not rely on simplistic assumptions about path loss, they are suited for realistic scenarios with attenuation and shadowing effects. We compare our approach to a broad selection of state-of-the-art approaches in indoor and outdoor scenarios. In all situations, our approach outperforms the existing approaches with respect to schedule length and power consumption, i. e., yields paretosuperior schedules including schedules that significantly improve the throughput.

I. INTRODUCTION

The scheduling problem in wireless networks has received a lot of attention in recent years. Given a set of transmission requests, one has to find a schedule that satisfies all interference constraints. If wireless nodes can individually adjust transmission powers on a per-transmission base, a schedule must also include power levels for each transmission, adding a powerful degree of freedom. The quality of a schedule then substantially determines throughput and power efficiency of the wireless communication. Obviously, distribution of transmissions to a small number of time slots is desirable to decrease the time to complete the request, i. e., to improve the throughput. On the other hand, less interference between concurrent transmissions allows for lower transmission powers and can hence reduce energy consumption. Especially in wireless sensor networks, where energy is a limited and valuable resource, the computation of good time-division multipleaccess (TDMA) schedules can help to extend the lifetime of the whole network. Since schedules admissible without power control are also solutions if power control is possible, power control can be exploited to reduce the energy consumption of such schedules in a subsequent and largely orthogonal step. However, solving both problems simultaneously helps to compute schedules with higher throughput (i. e. shorter span) and less energy consumption: power control admits schedules that would otherwise violate interference constraints, since reducing transmission powers can also reduce interference between concurrent transmissions.

Considering the importance of the scheduling problem, it is not surprising that it has been studied intensely. Originally, most algorithmic approaches to scheduling problems were graph-based. This made it possible to reduce the problem to variants of independent set, matching, or coloring problems. Some examples are [START_REF] Pond | A distributed time-slot assignment protocol for mobile multi-hop broadcast packet radio networks[END_REF]- [START_REF] Sharma | On the complexity of scheduling in wireless networks[END_REF]. Graph-based methods were especially popular in theoretical computer science, as they allow a thorough theoretical analysis. Unfortunately, graph-based models are too simplistic as they do not model distance-dependance of link quality and accumulation of interference [START_REF] Grönkvist | Comparison between graph-based and interference-based STDMA scheduling[END_REF]- [START_REF] Moscibroda | Protocol Design Beyond Graph-Based Models[END_REF]. In contrast, researchers in information, communication, or network theory usually apply the physical signal-to-interference-plus-noise-ratio (SINR), which reflects the physical reality more precisely. In this model, a transmission is successful if and only if the ratio of the useful signal to interference plus background noise exceeds some threshold. Signal strength and interference depend on path loss between sender and receiver. This path loss is determined by the distance between sender and receiver, as well as by environmental conditions such as obstacles. One simplification of this model is the geometric SINR model (SINR G model), where one assumes that path loss is fully determined by the sender-receiver distance. Here, path loss is modeled by a power law and different environments by different path loss exponents. Scheduling in the general SINR model is NPhard [START_REF] Goussevskaia | Complexity in Geometric SINR[END_REF]. The NP-hardness of scheduling with fixed powers in the more restricted geometric SINR G model has been shown in [START_REF] Goussevskaia | Complexity in Geometric SINR[END_REF]. Power control has originally been studied in the context of channelized cellular systems [START_REF] Zander | Distributed cochannel interference control in cellular radio systems[END_REF], [START_REF] Foschini | A simple distributed autonomous power control algorithm and its convergence[END_REF] and code-division multiple-access (CDMA) systems [START_REF] Ulukus | Stochastic power control for cellular radio systems[END_REF]. The joint problem of scheduling and power control was first addressed by ElBatt and Ephremides [START_REF] Elbatt | Joint scheduling and power control for wireless ad-hoc networks[END_REF], [START_REF]Joint scheduling and power control for wireless ad hoc networks[END_REF], followed by others including [START_REF] Wang | A Distributed Joint Scheduling and Power Control Algorithm for Multicasting in Wireless Ad Hoc Networks[END_REF]- [START_REF] Kozat | A Framework for Crosslayer Design of Energy-efficient Communication with QoS Provisioning in Multi-hop Wireless Networks[END_REF].

The complexity of scheduling with power control in the SINR G model is considered an important open problem [START_REF] Goussevskaia | Complexity in Geometric SINR[END_REF], [START_REF] Locher | Sensor Networks Continue to Puzzle: Selected Open Problems[END_REF]. In this work, we answer this question by proving NPhardness.

More recently, several approximation algorithms have been proposed for scheduling with and without power control [START_REF] Goussevskaia | Complexity in Geometric SINR[END_REF], [START_REF] Moscibroda | How Optimal are Wireless Scheduling Protocols?[END_REF]- [START_REF] Halldórsson | Wireless Scheduling with Power Control[END_REF] in this simplified model of interference.

Today, there exists a wide range of algorithms for scheduling in the SINR model, mostly aiming solely at maximizing the throughput, i. e., at minimizing the span of computed schedules. An algorithm also taking energy efficiency into account is, e. g., given by Lu and Krishnamachari [START_REF] Lu | Energy efficient joint scheduling and power control for wireless sensor networks[END_REF]. The authors also consider the problem to minimize the energy that is needed to schedule a given set of transmissions within a predefined number of time slots. We discuss some relevant algorithms more detailed in Section VI. The algorithms we contribute also allow both, maximizing the throughput and minimizing the energy consumption for a given throughput. They are based on a novel dynamic scheme for maintaining optimum powers for a changing feasible set of transmissions. The proposed data structure supports more sophisticated scheduling decisions without a penalty on the worst-case running time. To evaluate our algorithms, we compare them experimentally to several other state-of-the-art algorithms. In our simulations, we consider three scenarios: randomly distributed sender-receiver pairs, a given network topology, and a scenario that models effects that occur within buildings. In all three scenarios, our algorithms outperform the other approaches in two ways: First, they yield higher throughput. Second, our algorithms can realize any other algorithm's throughput with significantly less energy. Moreover, the algorithms can be used to find a good compromise between throughput and energy consumption.

The rest of the paper is organized as follows. The used models and notations are described in Section II. Subsequently, in Section III, we prove the NP-hardness of scheduling with power control in the SINR G model. Our approach to the problem of power control is described in Section IV. Based on the new power control algorithm, we describe our scheduling heuristics in Section V. The simulation results are shown in Section VI. Section VII concludes this paper.

II. MODELS AND NOTATIONS

We assume a network of wireless nodes. In this network, we are given a set {l 1 , l 2 , . . . , l n } of n links. Every link l i = (s i , r i ) is defined by its sender s i and its receiver r i . We say that a link l i is active if s i transmits data to r i . The transmission power that s i uses is denoted by P i . The path loss between sender s i and receiver r j is denoted by γ ij . It defines how much the signal strength decreases on the way from sender s i to receiver r j and can depend on the distance between sender and receiver, as well as on environmental conditions and obstacles. When a sender s j sends with power P j then receiver r i receives the signal with power P j γ ji . In the case of i = j the signal a useful signal, otherwise we call it interference. Additionally to the interference due to concurrent transmissions, every receiver r i experiences some background noise η i . A transmission t i = (s i , r i , P i ) is defined by senderreceiver-pair (s i , r i ) and transmission power P i that s i uses.

In this paper, we use the physically motivated SINR model (signal-to-interference-plus-noise-ratio model). In the SINR model, a transmission t i is assumed to be feasible if the ratio of the useful signal to accumulated interferences plus background noise at receiver r i exceeds some minimum SINR β i . This SINR condition is expressed by the following equation:

P i γ ii j =i P j γ ji + η i ≥ β i (1)
A set of transmissions {t 1 , t 2 , . . . , t k } is said to be feasible if SINR condition (1) of every receiver r i , 1 ≤ i ≤ k, is fulfilled when all senders s i , 1 ≤ i ≤ k, transmit concurrently with their associated transmission power P i .

Only in Section III we deal with the more restricted geometric SINR model (SINR G model). In the SINR G model, a close relationship between distance and path loss is assumed. Let d(s i , r j ) denote the distance between nodes s i and r j . The path loss between s i and r j is then given by γ ij = d(s i , r j ) -α , with path loss exponent α. The path loss exponent α depends on the environment and defines how fast the signal decays with distance. Usually, α is assumed to be about 2 in free space and between 3 and 5 in buildings.

In the scheduling problem, one is given a set L of links and transmission powers P i to be used by the senders. Usually, only the case of uniform transmission powers P i ≡ P is considered. The problem is to find a partition of L into transmission sets such that all sets are feasible. The single transmission sets are called slots, and we refer to the number of slots in a schedule as the schedule's span. The goal is to find a schedule with minimum span in order to maximize the communication throughput.

A somehow dual problem to the scheduling problem is the power control problem: given a set of links L and a partition into transmission sets, find transmission powers P i ∈ (0, P max ] such that each transmission set is feasible. In order to extend the lifetime of the network, the optimization goal is to find minimum such transmission powers. As we will see in Section IV, the notion of minimum transmission powers is welldefined and independent of the metric applied.

A generalization of both problems, the scheduling and the power control problem, is the problem of scheduling with power control, in which one has to compute a partition of a set of links and proper transmission powers. Again, the computation of a feasible schedule with minimum span is an important problem, but one can also be interested in minimizing the energy consumption for a given span. Note that pure energy minimization trivially leads to solutions where time slot contains exactly one single link. This paper addresses both relevant problems, pure throughput maximization and the bicriterial problem. Particularly, the algorithms proposed in Section V can be used to find a good compromise between power consumption and throughput.

III. COMPLEXITY OF SCHEDULING WITH POWER CONTROL

In the following, we sketch an NP-hardness proof for minimizing a schedule's span with power control in the SINR G model. The proof is an extension of the NP-hardness proof for scheduling without power control given in [START_REF] Goussevskaia | Complexity in Geometric SINR[END_REF]. Due to space limitations, we restrict ourselves to the main ideas. The technical details of the proof can be found in [START_REF] Völker | On the Complexity of Scheduling with Power Control in Geometric SINR[END_REF].

Our proof requires that we know minimum and maximum transmission powers P min > 0 and P max < ∞. This is no real restriction, as the hardware usually dictates an upper bound on the transmission power and due to the background noise there exists a power beneath which no transmission can be successful. As P min and P max are arbitrary, all practically relevant cases are covered. In particular, this proof contains the situation where every sender has a finite set of available transmission powers from which it can choose. For the sake of simplicity, we ignore the influence of background noise in this section. This makes the equations clearer but has no significant effect on the results. In order to show the NP-hardness of scheduling with power control (SCHEDPC), we will give a polynomial time reduction of the well-known PARTITION problem to SCHEDPC. The PARTITION problem has been shown to be NP-complete in [START_REF] Karp | Reducibility Among Combinatorial Problems[END_REF]. It is defined as follows: Given a set

I = {i 1 , . . . , i n } of integers, find I 1 , I 2 ⊂ I such that I 1 ∩ I 2 = ∅ and ij ∈I1 i j = ij ∈I2 i j = 1 2 ij ∈I i j .
Let I = {i 1 , . . . , i n } be an instance of PARTITION. Without loss of generality, we assume that all elements are distinct and positive and we define σ := n j=1 i j . In order to solve the PARTITION problem for I, we construct an instance L I = {l 1 , . . . , l n+2 } of SCHEDPC with n + 2 links such that there exists a schedule of length 2 if and only if the PARTITION instance I has a solution. The construction is depicted in Figure 1: For every integer i j ∈ I we introduce a link l j = (s j , r j ). Every sender s j is placed at position pos(s j ) = ((P min /i j ) 1/α , 0). The position is chosen such that the interference caused at the origin (0, 0) of the coordinate system equals i j when s j sends with power P min . Next, we place the corresponding receivers such that every transmission l j can be executed successfully, even if s j sends with power P min and every other sender sends with power P max . For this, every sender-receiver-pair has to be placed sufficiently close together. One can show that distance

d min = P 1/α min • 1 (imax-1) 1/α -1 i 1/α max 1 + ( Pmax Pmin nβ) 1 α
, where i max is the maximum value in I, is sufficient. Thus, we place every receiver r i , 1 ≤ i ≤ n, at position pos(r i ) = pos(s i ) + (d min , 0).

Finally, we have to place l n+1 and l n+2 . We positioned the senders s 1 , . . . , s n such that the interference which they cause at the origin is proportional to i 1 , . . . , i n . In order to take advantage of this property, we place r n+1 and r n+2 at the origin, pos(r n+1 ) = pos(r n+2 ) = (0, 0). Last, we place their senders s n+1 and s n+2 perpendicular to the x-axis at distance (2P max /βσ) 1/α , i.e., pos(s n+1 ) = 0, 2Pmax

β•σ 1/α and pos(s n+2 ) = 0, -2Pmax β•σ 1/α .
As the receivers r n+1 and r n+2 share the same position, transmissions t n+1 and t n+2 cannot be active concurrently. Thus, one needs at least two slots in order to schedule all transmissions. The senders s j , 1 ≤ j ≤ n, have to send at least with power P min while they are active. Thus, together they produce at least the interference σ = n j=1 i j at the position of r n+1 and r n+2 . The senders s n+1 and s n+2 , at the same time, cannot transmit with more power than P max . Thus, they cannot tolerate more interference than σ 2 . It follows that a schedule with only two slots is possible if and only if s n+1 and s n+2 send with P max , all other senders send with P min , and the senders s j , 1 ≤ j ≤ n, can be partitioned into two sets I 1 and

I 2 such that ij ∈I1 i j = ij ∈I2 i j = σ 2 .
This, in turn, implies a solution to the original PARTITION problem.

IV. COMPUTATION OF OPTIMUM TRANSMISSION POWERS

Solving the power control problem, i. e., finding minimum transmission powers for a given schedule, is a common subproblem of many algorithms for scheduling problems with power control. Since minimizing transmission powers for a given schedule trivially reduces to minimizing transmission powers for each slot separately, we restate the power control problem in a simplified form: Given a set L = {l 1 , . . . , l n } of links, find the minimum transmission powers P 1 , . . . , P n , P i ∈ (0, P max ] (possibly with P max = ∞), such that the resulting transmission set is feasible, or decide that no such powers exist.

As this problem is very fundamental, several approaches have been proposed in the literature. For example, one can express the problem as a linear program and use an LP solver to compute optimum powers, e. g., as

min! 1≤i≤n P i s. t. P i ≥ j =i P j β i γ ji γ ii + η i β i γ ii for 1 ≤ i ≤ n (2) P i ≥ 0 and P i ≤ P max for 1 ≤ i ≤ n .
In this form, we also observe that minimizing the sum of powers yields the same result as minimizing any function f (P 1 , . . . , P n ) that is (not necessarily strongly) monotonically increasing in the P i (such functions include the maximum, the minimum, or any norm). Explicitly, if the problem is feasible, for any such function f , the optimum solution p := (P 1 , . . . , P n ) T is given by setting P i to the minimum value of P i in any feasible solution p = (P 1 , . . . , P n ) T . This is welldefined since the value of any P i in any feasible solution is bounded from below and the of feasible solutions is closed. Assume P is not feasible (if it is, it is obviously optimal), i. e., assume that Equation ( 2) is violated for some i. By construction, there is a feasible solution p i := (P i 1 , . . . , P i n ) T with P i := P i i . For all j = i, we have P j ≤ P i j by construction and hence Equation (2) holds for i, in contradiction with the assumption.

An approach used by most heuristics for the combined problem of scheduling and power control is to start with small transmission powers and then iteratively increase the powers until the transmission set becomes feasible or until one of the senders exceeds its maximum transmission power. This can be done in such a way that the resulting transmission powers converge to the optimum [START_REF] Elbatt | Joint scheduling and power control for wireless ad-hoc networks[END_REF]. It has also been shown that under certain conditions only a constant number c of iterations is necessary to either get near-optimal transmission powers or to determine that no proper transmission powers exist. Every iteration takes O(n 2 ) time, so a near-optimal power assignment can be computed in O(cn 2 ) time.

If one has to compute such a power assignment only once for a given set of links, one can hardly do better. However, in the combined problem of scheduling and power control, such power assignments have to be computed over and over until the final set of links and powers is found. The usual approach is to start with an empty set and to add links one by one in some order that aims to find a good schedule. This gives an O(cn 3 ) computation time for filling a time slot with n transmissions.

In this work, we go a different way by stating the problem as a system of linear equations and then solving the system stepwise in an advantageous way. This will allow us to use more powerful scheduling heuristics without a penalty on the worst-case running time. As we will see in the experimental section, this intertwining of scheduling and power control allows the computation of substantially better schedules.

We start with the observation that for the optimal solution p , Equation ( 2) is tight, since otherwise, some P i could be reduced without losing feasibility. That is, finding powers minimizing any monotonically increasing function f subject to 0 ≤ P i ≤ P max and

P i = j =i P j β i γ ji γ ii + η i β i γ ii , 1 ≤ i ≤ n (3)
is equivalent to the problem stated above.

Writing Equation (3) as

A • p = b (4)
with

A =       1 -β1γ21 γ11 . . . -β1γn1 γ11 -β2γ12 γ22 1 . . . -β2γn2 γ22 . . . . . . . . . . . . -βnγ1n γnn -βnγ2n γnn . . . 1       , p = (P 1 , . . . , P n ) T , b = (β 1 η 1 /γ 1 1, . . . , β n η n /γ n n) T ,
we obtain the following result, which justifies to drop the optimization criterion:

Proposition 1: If there is any feasible solution to the power control problem, Equation (4) has a unique solution, which is the optimum p .

Proof: Assume that the power control problem has a feasible solution. Then p is an optimum solution to the power control problem and also a solution to Equation (4). Assume another solution p to Equation (4). Then A is not regular and A • p = 0 for p = pp . Then A • (pλp) = b for all λ ∈ R, and taking any non-zero entry Pi and a sufficiently small ∈ R + , we get a feasible solution p s := p -( / Pi )p with P s i = P iand P s j ≥ 0 for all 1 ≤ i ≤ n, which contradicts with the optimality of p .

Hence, from now on, for a given set of links, we are only interested in finding any solution p = (P 1 , . . . , P n ) T to Equation (4). If all P i are nonnegative and smaller than P max , this solution is the optimum (and unique). If there is no solution or any solution with some P i < 0 or P i > P maxwhich is always the case if there is more than one solution-, we can conclude that the problem is infeasible.

In the remainder of this section, we will show how this system of equations can be used to efficiently determine transmission powers.

Dynamic Computation of Optimum Transmission Powers

We now assume that we are given a set T of links that we want to schedule by adding transmissions from T to initially empty, always disjoint sets of active and feasible transmissions. For such a set S, we transform the matrix [A|b] along these additions to maintain a matrix [A S |b S ] with a special structure, but without altering the solution of the underlying equation system.

We start with S = ∅ and A ∅ := A and b ∅ := b. During the execution of our algorithm, we maintain the invariant that after each step it holds that

a ii = 1 ∀l i ∈ S (5) a ij = 0 ∀(l i , l j ) ∈ S × S, i = j . (6)
This obviously holds for S = ∅. Figure 2a shows this for a small example where S = {l 1 , l 2 , l 3 , l 4 }. Let us assume that we want to add some link l i ∈ T to the set S, yielding S = S ∪ {l i }. To preserve the special structure of our data structure, row i of matrix [A S |b S ] (the SINR constraint of link l i ) becomes important. For all l j ∈ S, we have to subtract row j multiplied by a ij from row i to get a ij = 0 (Step A). Next, we divide row i by a ii to get a ii = 1 (Step B). Finally, for every l j in S, we subtract row i multiplied by a ji from row j, resulting in a ji = 0 (Step C). This update can be done in O(kn) time, where k = |S| and n = |T ∪ S|. As stated above, all described matrix operations do not alter the solution of the underlying equation system.

Let us now see why we chose this special structure for matrix [A S |b S ]. First of all, if S is feasible, P i = b S i for all l i ∈ S and P j = 0 for all l j ∈ S immediately gives an optimum power assignment for link set S. More importantly, one can efficiently predict the effect that the addition of some arbitrary link l i ∈ T to S would have (cf. Figures 2b and2c): Looking at [A S |b S ] for active transmissions S = S ∪ {l i }, the optimum power P i of link l i in S is

P i = b S i = b S i -j∈S a S ij b S j 1 -j∈S a S ij a S ji . (7)
Thus, given [A S |b S ], we can compute P i in O(k) time. In similar fashion, with b i known, for every link l j ∈ S we can compute the new optimum power P j in constant time as

P j = b S j = b S j -a S ji b S i ∀j ∈ S . (8)
This means, given matrix [A S |b S ] for some feasible link set S, we can compute optimum powers for link set S ∪ {l i } in O(k) time. This is a significant improvement over the naive approach that starts all over with the initial equation system. So far we did not deal with the case that a set of links cannot be scheduled concurrently when trying to add a link l i . Obviously, this can happen. With the considerations above, closer inspection of the equation system reveals that we can identify an event that indicates and proves infeasibility:

Proposition 2: Let S be a feasible subset of T with corresponding matrix [A S |b S ]. The power control problem has a feasible solution for S ∪ l i for some l i ∈ T \ S if and only if the matrix operations in Step A yield an entry a S ii > 0 and the operations in Step B and C yield only entries b S j ≤ P max for l j ∈ S ∪ {l i }.

Proof: Making an induction over the cardinality of S, we can assume that during the computation of [A S |b S ] the case of a a S ii ≤ 0 never occurred in step A (this trivially holds for S = ∅). Hence, during all preceding matrix operations it is an invariant that (a) entries a ii > 0, (b) entries b i > 0, (c) entries a ij ≤ 0 for i = j. This can be seen by induction over the matrix operations: the invariants hold for the initial matrix [A ∅ |b ∅ ], and if they hold, Step A effectively adds positive multiples of other rows to the changed row. When adding a multiple of row j to row i, the only possible violation of the invariants is exactly the case that a ii becomes non-positive, which, by the outer induction, did not happen so far.

Then, in Step B, we multiply row i by a positive factor (not violating any invariant), and in Step C, we effectively add a positive multiple of row i to the other rows, which by construction cannot violate any invariant either.

If we perform

Step A for a new link l i ∈ T \ S, and we get a ii > 0, then again all invariants hold during all update operations and the relevant blocks of the matrix [A S∪{li} |b S∪{li} ] encode a feasible (and hence optimal) solution for the links in S ∪ {l i }, given by the

P i = b S∪{li} i
, which is feasible if and only if all these powers additionally are below P max . If, on the other hand, in Step A a matrix entry a ii ≤ 0 occurs, then there cannot be a solution to the corresponding subproblem with all P i ≥ 0, since we still have b i > 0, but all a ij ≤ 0.

In summary, given matrix [A S |b S ] of equation system (4) for a set S of active links (|S| = k), this approach allows to compute optimum powers for an arbitrary link set S ∪ {l} in O(k) time and to compute the updated matrix [A S∪{l} |b S∪{l} ] in O(kn) time. In the next section, we propose two heuristics that use this data structure to compute very good schedules efficiently.

V. SCHEDULING WITH POWER CONTROL

Two obvious optimization criteria for good schedules are the length of the schedule and the power that is needed to process all transmissions. At the first glance, those two objectives seem to contradict each other. In shorter schedules, the number of transmissions per slot is higher. This results in higher interference which in turn means that more power is needed. And surely, the most power efficient schedule would be the one where every transmission has its own slot. However, there is also some synergy. In order to compute short schedules, the interference between concurrent transmissions has to be kept small. And smaller interference also means less power consumption. Therefore, power minimization seems to be a good greedy strategy for both objectives. Based on this observation, we propose two greedy heuristics for the scheduling problem. The first one fills the slots one by one, iteratively adding the most power efficient transmission. The second one fills the slots in parallel and makes it possible to find a good compromise between schedule length and power consumption.

A. Filling Slots Sequentially

Many scheduling heuristics fill slots greedily one-by-one, i. e., a new slot is populated with links by adding links greedily. Usually, the order in which the links are processed is precomputed and depends on node degree, sender-receiver distance, or similar criteria. In contrast, we propose to select links depending on the effect that the decision has on the resulting transmission powers. For example, we pick the link that minimizes the maximum power that some transmission in the time slot requires. This way, links are picked which either can tolerate a lot of interference or fit well to the links that are already in the slot. Another good choice is to pick the link that minimizes the combined power used by all links in the slot, thus extending the overall lifetime of the whole network. We refer to these selection strategies as Greedy-Least-Maximum-Power (GLMP) and Greedy-Least-Additional-Power (GLAP), respectively.

Both approaches require to compute the new optimum transmission powers of the resulting link set S ∪ {l} for every link l ∈ T . Using the iterative power control algorithm that is used by most existing heuristics, this takes O(ck 2 ) time for each of the O(n) possible links, where k = |S| is the number of links that are already assigned to the repective slot. At this point, our power control algorithm from Section IV comes into play. It allows us to compute updated transmission powers for S ∪{l} in O(k) time. This makes it possible to find the best link in O(kn) time. As soon as we have determined the optimum link, we can add it in another O(kn) time to the set of active links.

In summary, the sequential approach works as follows: Start with an empty set S of active links. While the set T of links is non-empty, find the link l ∈ T that fits best to the set of active links. Depending on the objective, this can either be the link that minimizes the maximum transmission power (GLMP) or the one that minimizes the combined transmission power (GLAP). If such a link exists, add it to S and continue with the set T = T \ {l}. If no more link fits to the set of active links, continue with a new time slot. This process is repeated until T is empty. The overall running time is in O(k max n 2 ), where k max is the maximum number of concurrently active transmissions. Note that the worst case occurs when k max ∈ O(n). In this case, the running time is O(n 3 ). This is quite good as the size of the input, given by the gain matrix, is already in Θ(n 2 ). And even if one had an optimum assignment of links to slots given as input, the computation of optimum powers using equation system (4) and common approaches such as Gaussian elimination would already require O(n 3 ) time. Thus, the selection of good links does not affect the worst-case run time.

B. Filling Slots Simultaneously

As stated in the introduction, the schedule length is not the only optimization criterion. In this section, we deal with the problem of finding a good compromise between schedule length and power consumption. Given a set of links and a number of slots, we want to distribute the links to the available slots in a power-efficient manner.

For this purpose, we process the links in order of increasing sender-receiver-gain so that we deal with the most sensitive links first. For every link, we greedily determine the best slot, again measuring goodness by power consumption, and either choose the slot that minimizes the maximum occurring transmission power, or the slot that minimizes the additional power consumption. We refer to the former approach as Balanced-Least-Maximum-Power (BLMP) and to the latter as Balanced-Least-Additional-Power (BLAP). As before, this means that we have to precompute for every open link the powers that its addition would cause. Again, we use the method from Section IV to compute the new powers for a slot with k transmissions in O(k) time. Fortunately, it is not necessary to maintain the complete matrix [A|b] for every single slot. Instead, it is sufficient to maintain only the rows that correspond to SINR constraints of links that are assigned to the slot. Thus, for a slot with k active links we only need O(kn) matrix cells, giving the algorithm O(n 2 ) space complexity. This is optimal as the gain matrix in the input already needs Θ(n 2 ) space.

In comparison to the sequential approach, the parallel approach aims at significantly more balanced schedules, since all slots are expected to have a similar number of active links.

With a fixed number of slots, it may happen that a link does not fit in any of the available slots. In this case, we assume that a new slot is added to the set of available slots.

When the desired number of slots is not clear from the application, one can for example start with a single slot, which still yields more balanced schedules, since to links with high gain, which are scheduled latest, all opened slots are available.

However, if there is a need to create more than the initial number of slots, balancing is imperfect, since links scheduled early do not have all slots of the final schedule at choice. Hence, when interested in a balanced schedule with low span, it is best to find the minimum number of slots that is sufficient for this approach, e. g., by binary search. A reasonable result with only a single restart can also be produced taking the schedule returned for a single initial slot and take its span to make a good guess for a restart. For example, 80% of the returned schedules span as initial number of slots should already be a good choice.

VI. SIMULATIONS

A. Scenarios and Model Parameters

For our experiments, we used three different scenarios. The first one assumes that the sender-receiver pairs are randomly distributed in the Euclidean plane. There is no connected network structure. The signal strength is computed according to the SINR G model with path-loss exponent α = 3. This scenario resembles a sensor network with high number of nodes where only some of the nodes want to send concurrently. This kind of scenario was for example used in [START_REF] Goussevskaia | Capacity of Arbitrary Wireless Networks[END_REF]. An example is shown in Figure 3a. The second scenario is based on a network topology. The nodes are placed randomly in the Euclidean plane. Every pair of nodes that can communicate according to the SINR G model (α = 3) is connected by two links, one in each direction. This scenario represents a network in which all nodes try to communicate frequently. Similar models were used in [START_REF] Elbatt | Joint scheduling and power control for wireless ad-hoc networks[END_REF], [START_REF]Joint scheduling and power control for wireless ad hoc networks[END_REF]. We assume that all links have the same traffic demands. This prevents that single links dominate the length of the computed schedules. Of course, all algorithms can just as well be used in situations with arbitrary link demands.

Our last scenario aims at recreating effects that occur in buildings with walls and obstacles. We assume that the signal strength falls of with path-loss exponent α = 2.5 as long as there is no wall. Additionally, every wall that crosses the line of sight between a sender-receiver-pair results in normally distributed attenuation. Finally, the random effects that are caused by reflections and self-interference are represented by adjusting the signal strength of every link with a zero-mean, normally distributed random attenuation with σ = 2dB. An example is shown in Figure 3c. One can see that this leads to some kind of cluster formation within rooms, a feature that does not show up in the other scenarios.

In all scenarios, we assume an omnipresent background noise η and minimum SINR β = 10dB. The other model parameters are normalized such that the maximum transmission radius d max with power P max = 1 equals distance 100 if there are no walls, and if we assume α = 2 for the path loss exponent. For α = 3, this gives d max = 21.54.

B. Input Generation

In the first scenario, we distributed between 100 and 2500 links randomly in an area with dimensions 400 × 400. First, the senders were placed randomly. Subsequently, the receivers were placed within a radius of 0.9d max around their senders. In the second scenario, we placed between 25 and 250 nodes randomly in an 200×200 area. All pairs of nodes with distance less than 0.9d max were connected. In this scenario, every node can act both as sender and receiver and be part of many links. However, in every time slot every node can only take part in one transmission.

In the indoor scenario, between 20 and 200 nodes were randomly distributed in an 200 × 200 area. Additionally, wall segments were placed on a regular 8 × 8 grid. On each of the 112 inner grid segments, a wall was put with probability 60%. The attenuation of each wall segment was determined by a normally distributed random value with µ = 5dB and σ = 2dB. Finally, links were added for all nodes that were able to communicate with each other according to the general SINR model.

C. Examined Algorithms

In order to evaluate our algorithms, we implemented several existing algorithms for the scheduling problem. For the sake of fairness, we chose algorithms that are especially designed and optimized for the physical SINR model. This section gives a short overview on the selected algorithms. In case an algorithm was not named by the authors, we gave a name based on author names and year of publication. Some of the examined algorithms do not include power control. In this cases, we computed optimum powers for the generated schedules.

ElBatt04 [START_REF]Joint scheduling and power control for wireless ad hoc networks[END_REF] was the first algorithm for scheduling with power control in the SINR model. The algorithm alternates between scheduling and power control and defers transmissions with minimum SINR until an admissible set of powers can be found. In contrast, LiEph05 [START_REF] Li | Joint Scheduling, Power Control, and Routing Algorithm for Ad-Hoc Wireless Networks[END_REF] starts with empty slots and adds links according to some scheduling metric that takes into account queue sizes and number of blocked links. Every time a slot is filled, a new slot is opened. A similar approach is used by GreedyPhysical [START_REF] Brar | Computationally efficient scheduling with the physical interference model for throughput improvement in wireless mesh networks[END_REF]. Instead of the scheduling metric, an interference number is used to sort the links in the beginning. The links are processed according to their order and added to the first possible time slot. DiGreedy [START_REF] Lu | Energy efficient joint scheduling and power control for wireless sensor networks[END_REF] is another approach to find a good compromise between schedule length and power consumption. The underlying principle is similar to the one in ElBatt04. Links with high interference are deferred until a feasible link set is found. Additionally, every feasible set is rated based on schedule length and power consumption. In order to optimize the relation of throughput and power consumption, the remaining links are removed one by one from the set of active links. In the end, from all feasible link sets the one with the best rating is chosen. Using a parameter, one can decide whether throughput or power efficiency is more important. ApproxLogN [START_REF] Goussevskaia | Capacity of Arbitrary Wireless Networks[END_REF] was the first algorithm which guaranteed a O(log n) approximation for the problem of minimizing the number of time slots needed to schedule a given set of requests. The authors showed that their algorithm is superior to the algorithm ApproxDiversity which was proposed in [START_REF] Goussevskaia | Complexity in Geometric SINR[END_REF]. However, the algorithm needs to know the sender-receiver distances and it relies on the special properties of the SINR G model, thus it cannot be used in realistic scenarios with obstacles and random effects. Hall09 [START_REF] Halldórsson | Wireless Communication is in APX[END_REF] is a simplified version of ApproxLogN. The authors showed that the algorithm computes a constant factor approximation for the scheduling problem in the SINR G model. Just as ApproxLogN, this algorithm relies on the properties of the SINR G model.

D. Throughput

We start with an examination of the schedule lengths. The schedule length determines the communication throughput and all considered algorithms are intended for computing short schedules. Figure 4 shows how the schedule length increases with increasing link density. It is not surprising that the relation between schedule length and link density is almost linear. Apparently, not all algorithms perform equally well in all scenarios. Moreover, in the indoor scenario, the differences between the algorithms seem to diminish. However, in all scenarios the heuristics BLMP and BLAP compute the best schedules, with BLMP being marginally better. Table I compares average schedule lengths for certain inputs. For the random links scenario, the input consisted of 1500 random links. For the network and building scenarios, the input consisted of 200 and 120 random nodes, resulting in 1081 links and 797 links on average, respectively.

For the heuristics BLMP and BLAP two values are given. For the first value, the algorithm was initially started with only one open slot. Then, 80% of the length of the computed schedule was used as a better start value for a second iteration

E. Power Consumption

In some situations, for example in wireless sensor networks, the available energy is limited and one might be interested in energy efficient schedules. Figure 5 shows the dependence between average power consumption and link density. For every algorithm, the average transmission power in throughput optimal schedules is given as a fraction of P max . Moreover, a lower bound P req on the average transmission power is shown. P req is defined as the average power that is used when all transmission are scheduled one by one, thus avoiding interference. One can see that the curves become flat for large numbers of links. A direct comparison of the algorithms is given for certain input sizes in Table II. This time, the powers are given relative to P req , thus highlighting the overhead that one has to accept for the higher throughput.

F. Throughput vs. Power Consumption

In this section, we try to make a fairer comparison regarding power consumption by also taking into account the throughput of the considered schedules. For this purpose, we randomly selected schedules and plotted them in Figure 6. The further left a point is, the higher is the throughput of the corresponding schedule, and the lower a point is, the less energy needs the schedule. In the random scenario, the algorithms are separated very nicely. Again, it becomes apparent that the algorithms BLMP and BLAP achieve the highest throughput. At the same time, BLAP also is highly competitive with respect to required energy. GLMP also computes short schedules. However, the slot-by-slot approach makes it much harder to distribute the transmissions beneficially, thus the energy demand is much higher. We already mentioned that BLMP and BLAP allow the computation of energy efficient schedules by using more slots than necessary. This compromise is visualized by the curves in Figure 6. For example, one can deduce that with an average power of about 1.2P req one can schedule all 1000 links of the random link scenario within 70 slots. In all scenarios, the curve of BLAP is way below all other algorithms. Thus, given the same number of slots, the schedules computed by BLAP are significantly more economical. Compared to the first scenario, in the network scenarios the differences between the single algorithms are not so distinct. Especially in the indoor scenario, the random effects lead to much scatter. However, in all scenarios BLAP is evidently superior.

G. Network Lifetime

Energy aware schedules increase the lifetime of the network. We will examine this exemplary for the network scenario with 200 randomly distributed nodes. For this purpose, we consider the time that passes until 10%, 20%, 30%, 50%, and 75% of the nodes run out of battery, assuming that all links are active for about the same time and that all nodes have the same initial battery charge. The lifetime improvement that can be achieved by using the BLAP heuristic is shown in Table III. For example, when using BLAP instead of ElBatt04, using the same number of time slots, it takes 29.3% longer until 10% of the nodes run out of battery. The last row of Table III shows the advantage of a throughput optimized schedule using BLAP in comparison to scheduling without power control. It is obvious that even in short schedules with high throughput a lot of energy can be saved by using good power control.

VII. CONCLUSION

In this article, we considered several aspects of scheduling with power control in wireless networks. First, we showed that the problem is NP-hard in the SINR G model. Subsequently, we described a power control algorithm that is optimized for situations where transmissions are added one by one. Thus, it can be used to improve several existing heuristics. However, the algorithm's main advantage is that it allows to look efficiently one step ahead. Given the solution for a set of active links, it is Based on this property, we proposed scheduling heuristics that gradually assign links to slots, taking into account all entailed effects. In order to evaluate our heuristics, we compared them to several existing approaches. For this purpose, we considered three different scenarios. In all scenarios, our algorithms outperformed the existing approaches in terms of throughput and power efficiency. Moreover, the algorithms can be used to find a good compromise between throughput and energy efficiency and they are also useful in situations where the number of available slots is predefined.

S = β σ 2 Fig. 1 .

 21 Fig. 1. Polynomial-time reduction of PARTITION to SCHEDPC

Fig. 2 .

 2 Fig. 2. Matrix [A|b] of the system of linear equations. (a) Partial solution for S = {l 1 , l 2 , l 3 , l 4 }. (b) Computation of optimum power for link l 6 in S ∪ {l 6 }. (c) Computation of updated powers for already active links.

Fig. 3 .

 3 Fig. 3. Simulation scenarios. (a) Random links in free space. (b) Network in free space. (c) Network in building with wall attenuation and random effects.

Fig. 4 .

 4 Fig. 4. Average schedule length. (a) Random links in free space. (b) Network in free space. (c) Network in building.

Fig. 5 .

 5 Fig. 5. Power consumption (random links in free space).

Fig. 6 .

 6 Fig. 6. Throughput vs. power consumption. (a) 1500 random links. (b) Network with 200 random nodes. (c) Network in building with 120 random nodes.

  One can see that this resulted in slightly better schedules. However, the difference is rather small. Obviously, the approximation algorithms ApproxLogN and Hal09 give significantly worse throughput than the other algorithms. The reason is that they are mainly of theoretical interest. The focus was not on computing the best schedule possible, but on showing that one can give approximation guarantees. It would be easy to use those algorithms to compute an initial schedule and then to use the ideas proposed in this paper to improve the schedule, thus getting a competitive algorithm with approximation guarantees. However, it is unlikely that this would result in significantly better schedules.

				of the algorithm.
		TABLE I
		AVERAGE SCHEDULE LENGTH
		Random	Network	Building
	Algorithm	(∅ 1500 links)	(∅ 1081 links) (∅ 797 links)
	ElBatt04	84.0	207.6	229.4
	LiEph05	80.2	193.9	179.1
	GreedyPhy	89.6	184.6	160.2
	ApproxLogN	531.4	826.0	-
	Hal09	1288.9	1051.9	-
	GLMP	58.4	155.8	164.6
	BLMP	57.1 / 53.0	141.6 / 140.1	149.4 / 149.4
	BLAP	56.4 / 54.8	143.7 / 141.4	150.2 / 150.9

  However, when interpreting this numbers, one has to keep in mind that at this point we compare schedules of different lengths. It is no miracle that schedules with lower throughput need less power. Extreme examples are ApproxLogN and Hal09, as they only schedule transmissions together that hardly interfere with each other.

TABLE II AVERAGE

 II POWER CONSUMPTION RELATIVE TO PREQ [%] very cheap to see what would happen if another link is added.

			Random		Network		Building
	Algorithm	(∅ 1500 links) (∅ 1081 links) (∅ 797 links)
	ElBatt04		163.4		151.8		129.4
	LiEph05		182.6		182.8		155.5
	GreedyPhy		145.7		160.0		146.7
	ApproxLogN		100.0		100.0		-
	Hal09		100.0		100.0		-
	GLMP		201.4		176.3		141.3
	BLMP		190.1 / 178.4	178.9 / 175.3	139.6 / 145.4
	BLAP		164.9 / 153.6	156.5 / 149.0	126.4 / 121.7
			TABLE III
	LIFETIME IMPROVEMENT BY HEURISTIC BLAP [%]
	compared to	10%	20%	30%	50%	75%
	ElBatt04		29.3	32.5	35.1	40.2	48.9
	LiEph05		45.0	51.4	57.8	67.7	85.7
	GreedyPhy		42.2	38.7	36.6	33.5	29.9
	GLMP		26.4	31.2	35.4	43.1	56.0
	Fixed Power		157.6	214.6	270.9	406.4	738.2

ACKNOWLEDGMENT

This work was partially supported by the German Research Foundation (DFG) within the Research Training Group GRK 1194 "Self-organizing Sensor-Actuator Networks".


M Böyükata

P Van Isacker

İ Uluer

Description of nuclei in the A∼100 mass region with the interacting boson model

Keywords: numbers: 21.60.Ev, 21.10.Re, 21.60.Fw nuclear level energies, E2 transitions, interacting boson model

Even-even nuclei in the A ∼ 100 mass region are investigated within the framework of the interacting boson model-1 (IBM-1). The study includes energy spectra and electric quadrupole transition properties of zirconium, molybdenum, ruthenium and palladium isotopes with neutron number N ≥ 52. A global parametrization of the IBM-1 Hamiltonian is found leading to a description of about 300 collective levels in 30 nuclei with a root-mean-square deviation from the observed level energies of 120 keV. The importance of the d 5/2 subshell closure at neutron number N = 56 is pointed out. The geometric character of the nuclei can be visualized by plotting the potential energy surface V (β, γ) obtained from the IBM-1 Hamiltonian in the classical limit. The parametrization established on the basis of known elements is used to predict properties of the unknown, neutron-rich isotopes 106 Zr, 112 Mo, 116 Ru and 122 Pd.

Introduction

The production and use of radioactive beams is a rapidly developing new field in nuclear physics. Pioneering experiments are taking place, dedicated facilities are commissioned and new ones are planned. The primary aim of this research activity is the study of so-called exotic nuclei, that is, short-lived nuclei far removed from the line of stability because of an unusual ratio of numbers of neutrons N over protons Z. Parallel with the rapid developments of experimental techniques to observe exotic nuclei, there has been a surge in the interest in their theoretical description.

The main motivation for these studies is the possibility that wide variations in N/Z may have a profound influence on shell structure, which constitutes the basis of our understanding of nuclei. There exist currently two standard theoretical approaches for the description of exotic nuclei, namely energy density functional theory [1] and the nuclear shell model [2]. In this paper we explore the use of a third approach, namely the interacting boson model (IBM) of Arima and Iachello [3,4,5], to predict properties of exotic nuclei.

The IBM is a semi-microscopic model of nuclei, positioned intermediately between single-particle and collective models. The model contains a vibrational and a rotational limit (as well as one which can be considered as intermediate)-which connects well with the phenomenology of nuclei-and can be brought into relation with the nuclear shell model. In the original version of the IBM, applicable to even-even nuclei, the basic building blocks are s and d bosons with angular momenta L = 0 and L = 2, respectively. The s and d bosons can be interpreted as correlated Cooper pairs formed by two nucleons in the valence shell coupled to angular momenta L = 0 and L = 2. This interpretation constitutes the basis of the connection between the IBM and the nuclear shell model, and leads in a natural way to a version of the model where a distinction is made between neutron and proton bosons, the so-called IBM-2 [6].

If one restricts oneself to configurations that are symmetric in the neutron and proton bosons, the simplest version of the model arises, known as IBM-1. The standard IBM-1 Hamiltonian has 1 single-particle energy and 5 two-body interactions if only relative (excitation) energies are considered, increasing to 2 + 7 if absolute binding energies are included in the analysis. These coefficients enter as free parameters in the model and must be adjusted to the data. However, because of the connection with the nuclear shell model, the dependence of the energies and interactions on the number of valence neutrons and protons is known qualitatively [7]. The long-term aim of this work is to develop a systematic IBM-1 parametrization (that is, to determine the functional dependence of the various coefficients on the number of valence neutrons and protons) for entire regions of nuclei, and to do so on the basis of a fit to the data, guided by microscopic arguments. Once the appropriate functional dependence has been determined, it will be possible to make spectroscopic predictions by extrapolation to unknown regions of nuclei. The predictive power of this procedure will depend crucially on the counting of the valence nucleons and hence on the shell structure of nuclei and its evolution in exotic regions.

The idea to use the IBM to extrapolate from known to unknown regions of the nuclear chart is not new. In fact, in the late 1970s and early 1980s, long before any talk of exotic nuclei, this technique was applied on many isotope series in the context of the IBM-2. For a review of the literature, see Iachello and Arima [START_REF] Iachello | The Interacting Boson Model[END_REF]. Occasionally also isotone series have been considered [START_REF] Gómez | [END_REF] and recently also a combination of isobars and isotones [10]. However, to our knowledge a comprehensive and systematic description with the IBM of entire regions of nuclei has not yet been tried. The closest related study is due to Casten et al. [11] who elaborated a multi-nucleus IBM-1 parametrization based on the N ν N π scheme [12]. Our intention is to develop this idea further with more refined Hamiltonians that better reproduce observed nuclear properties. We also mention that our investigation has similar aims as those of the recent work of the Tokyo group [13], (i.e., the use of the IBM in the description of exotic nuclei); in the latter studies the connection of the IBM with mean-field models is exploited to arrive at a suitable parametrization while here the long-term aim is to draw inspiration from its connection with the shell model.

In this paper we present a first calculation of this type and apply the IBM-1 to an entire region of the nuclear mass chart, namely the even-even Zr, Mo, Ru and Pd nuclei with A ∼ 100. Section 2 gives a description of the parametrization of the Hamiltonian used. The application to the A ∼ 100 region is discussed in section 3. In the final section 4 the conclusions and outlook are presented. Preliminary versions of this work were presented in references [START_REF] Böyükata | AIP Conf. Proc[END_REF][START_REF] Böyükata | AIP Conf. Proc[END_REF].

Parametrization of the Hamiltonian

The Hamiltonian used in this paper is of the form

Ĥ = ǫ nd + κ Q • Q + κ ′ L • L + κ ′′ P+ • P-+ λ n2 d , (1)
where nd , P+ , L and Q are the boson-number, pairing, angular momentum and quadrupole operators, defined as

nd = √ 5[d † × d] (0) 0 , P+ = [s † × s † + √ 5 d † × d † ] (0) 0 , P-= P+ † , Lµ = √ 10[d † × d] (1) µ , Qµ = [d † × s + s † × d] (2) µ + χ[d † × d] (2) µ . (2)
Equation ( 1) defines an IBM-1 Hamiltonian in terms of the six parameters ǫ, κ, κ ′ , κ ′′ , λ and χ. If one is interested in the properties of a single nucleus, this is a possible form of the most general Hamiltonian with the advantage that the first four terms have been used extensively in phenomenological fits to nuclear spectra [START_REF] Iachello | The Interacting Boson Model[END_REF]. The last term n2 d gives rise to a so-called 'τ -compression' which increases the moment of inertia with increasing angular momentum (or with increasing d-boson seniority τ ) [START_REF] Pan | [END_REF]. In addition to measured energy spectra, also electric quadrupole transition rates are considered in the fit. These are calculated in IBM-1 using the E2 operator Tµ (E2) = e b Qµ where e b is the effective charge of a boson and with a quadrupole operator which is consistent with the one used in the Hamiltonian, following the consistent-Q formalism (CQF) [17].

Although reasonable results are obtained with a constant Hamiltonian, they are considerably improved if parameters are allowed to vary with the number of nucleons in the valence shell, as suggested by the shell-model interpretation of the IBM-1. We propose here a dependence of the generic form

x = ij x ij (f ν ) i (f π ) j , (3)
where x is a parameter of the Hamiltonian, that is, x = ǫ, κ, κ ′ , κ ′′ or λ, and f ρ is the fractional filling of the neutron (ρ = ν) or the proton (ρ = π) valence shell, that is, f ρ ≡ n ρ /Ω ρ with n ρ the number of valence neutrons or protons and Ω ρ the size of the corresponding valence shell. Note that in the parametrization (3) neutrons and protons are always counted as particles and never as holes. While microscopic arguments suggest a dependence on F ρ ≡ nρ /Ω ρ rather than on f ρ (where nρ is the number of particles or holes, whichever is smaller counted from the nearest closed shell), the latter parametrization has the drawback of yielding spectra that are symmetric around mid-shell. Since this particle-hole symmetry is broken in the nuclei considered here, especially in the Pd isotopes, we prefer the parametrization (3).

Application to the A ∼ 100 region

In the present application to the A ∼ 100 region a linear dependence on the fractional fillings is assumed for the parameters κ, κ ′ and λ while ǫ and κ ′′ are kept constant. First, energy levels in the known nuclei 100-104 Zr, 94-110 Mo, 98-114 Ru and 102-120 Pd are selected and fitted with the IBM-1 Hamiltonian (1) by minimizing the root-mean-square (rms) deviation. In this first step an initial choice is made for χ, and ǫ, κ, κ ′ , κ ′′ and λ are fitted to the energy spectra of all nuclei considered in the fit with no dependence on the number of neutrons or protons. Next, the linear dependence on the fractional filling of the parameters κ, κ ′ and λ is determined again by minimizing the rms deviation. The minimization in this case involves 11 parameters, three for each coefficient in the Hamiltonian with a fractional-filling dependence together with ǫ and κ ′′ . Once the wave functions of all states have been determined in this unified fit, the E2 transition rates are fitted by adjusting the value of the boson effective charge e b but keeping to the same value of χ. Since B(E2) properties depend rather strongly on χ, it is at this point that it can established whether its value is appropriate or not. The entire procedure is repeated for a new value of χ, until a reasonable compromise is found between the results of the energy and E2 fits. This procedure is illustrated in table 1. The rms deviations in the energies and B(E2) values are quantified with following definitions:

∆(E) = 1 N E i (E i ex -E i th ) 2 ,
∆ 1 (E2) = 1 N E2 i (B(E2) i ex -B(E2) i th ) 2 , ∆ 2 (E2) = 1 N E2 i B(E2) i ex -B(E2) i th B(E2) i ex 2 , (4)
where the sums are over the available data points, N E and N E2 in number, respectively. Note that the first rms deviation for the E2 data, ∆ 1 (E2), is rather insensitive to small E2 transitions while ∆ 2 (E2) probably assigns too much weight to them. The rms deviations vary rather weakly except for small values of χ, but both energies and E2 transitions are optimized for χ ≈ -0.20. This value of χ and the parameters given in table 2 determine all spectra shown below.

In the above procedure care has been taken to undertake a gradual release of the parameters, instead of immediately attempting a full 11-parameter fit. This method has proven to be numerically stable but it offers no guarantee that the global minimum of the 11-dimensional parameter space will be reached, instead of a local one. Finding the global minimum is all the more problematic since some of the parameters, especially those that account for the fractional-filling dependence, offer little intuitive insight and are thus entirely unknown a priori. The character of the minimum corresponding to the parameters of table 2 has been checked by choosing different starting values for the x 01 and x 10 parameters, leading always to final parameter sets that are close to the one shown, within numerical errors. While this is not a proof of the global character of the minimum, it is a good indication of it.

The experimental and calculated energy spectra are compared in figures 1 and 2. The experimental energies are taken from the National Nuclear Data Center [18] with additional information concerning the nuclei 108 Pd and 112,118,120 Pd from the references [19,20]. Some of the spin assignments are uncertain (brackets in NNDC); these are not shown on the figure to avoid overcrowding. In the even-even Mo, Ru and Pd isotopes with N ≥ 52, all known levels of the ground-state, quasi-γ and quasi-β bands with angular momentum up to J = 10 are considered in the fit while for Zr only isotopes with N ≥ 60 are included. Figure 1 nevertheless also shows the experimental levels for 92-98 Zr (not included in the fit) merely to indicate that these strongly deviate from what is predicted from systematics. To give an illustration of the deviations, the 2 + 1 level in 96 Zr is observed at 1751 keV while it is calculated at 444 keV. These differences are indicative of the closure of the 1d 5/2 shell at N = 56, resulting in a nearly doublymagic behaviour of 96 Zr. These considerations can be made quantitative by including the ground-state bands of some of the lighter Zr isotopes in the energy fit. As illustrated in table 3 even the inclusion of just one isotope, 98 Zr, yields a dramatic increase in the rms deviation of the fit to the entire region. Effects of 1d 5/2 shell persist in 100 Zr which exhibits a low-lying K π = 0 + band at 331 keV. This clearly cannot be the collective first-excited K π = 0 + band of the IBM-1 and therefore the band is not included in the fit. The next-excited K π = 0 + band at 829 keV is possibly the quasi-β band of the IBM-1, which is calculated at 682 keV. We emphasize that the IBM-1 parametrization (3) depends on the counting of the number of valence nucleons and hence on the definition of shell closures and magic numbers. Since N = 56 is not included as a magic number, it is therefore no surprise that the structural features associated with this shell closure are absent from the present calculations. The inclusion of all Zr isotopes in a successful fit would necessarily require a refined parametrization that takes account of the N = 56 closure. However, even at the present level of approximation, we believe to have illustrated with this example that the unified fits of the type used here are sensitive to nuclear shell effects. This feature could be of use to detect precursor effects of shell closures in extrapolations toward unknown regions of the nuclear chart.

In the present application excluding Zr isotopes with N < 60, we arrive at a description of 335 collective levels in 31 nuclei with a rms deviation from the observed level energies of 120 keV. The most notable systematic discrepancies are found for (i) the spectra of N ∼ 56 Mo isotopes due to some remnant effect of the N = 56 closure, (ii) the energy of the γ band in 102 Zr which is predicted lower than it is observed, and (iii) some mid-shell nuclei like 100 Ru and 102 Pd which behave less collectively than predicted by IBM-1 systematics.

On the basis of the parametrization thus established it is now possible to make predictions for more exotic nuclei for which up to now no spectroscopic information is available. This is illustrated in figures 1 and 2 where systematically the predictions for the next (unknown) even-even isotopes are shown, that is, for 106 Zr, 112 Mo, 116 Ru and 122 Pd. Clearly, predictions further away from stability are possible as well but become increasingly uncertain.

Once the wave functions of all states have been determined in this unified fit, one can also calculate the E2 transition rates with an overall effective charge e b = 0.097 eb, adjusted to reproduce the 2 + 1 → 0 + 1 and 4 + 1 → 2 + 1 transitions. The results for the B(E2; 2 + 1 → 0 + 1 ) and B(E2; 4 + 1 → 2 + 1 ) values are shown in figures 3 and 4, respectively. These are a measure of the collective behaviour of the nucleus and our calculation generally follows the observed trends. A glaring exception to this overall agreement is the 2 + 1 → 0 + 1 transition in the Zr isotopes with N < 60 where the observed B(E2) value is only fraction from what is expected from systematics. This again is due to the neglect in the calculation of the 1d 5/2 closure at N = 56. There is also a mid-shell mismatch for the Pd isotopes which is calculated at N = 66 but observed at N = 64. Figure 5 shows the B(E2; 0 + 2 → 2 + 1 ) values. In the vibrational U(5) limit this transition corresponds to one from a two-phonon to a one-phonon state which is allowed while in the more deformed limits SO (6) and SU(3) this B(E2) value is much smaller. This argument gives a qualitative understanding of the theoretical results shown in figure 5.

As a further illustration of the kind of accuracy obtained for the B(E2) values in this overall fit, we show in table 4 the results for three nuclei, 100 Ru, 104 Pd and 108 Pd, for which extensive E2 data is known.

The geometric character of all nuclei can be visualized by plotting the potential energy surface V (β, γ) obtained from the IBM-1 Hamiltonian in the classical limit [21,

V (β, γ) = N 1 + β 2 a (1) 00 + a (1) 10 β 2 + N(N -1) (1 + β 2 ) 2 a (2) 00 + a (2) 10 β 2 + a (2) 01 β 3 cos 3γ + a (2) 20 β 4 , (5)
where the coefficients a

10 = ǫ + (1 + χ 2 )κ + 6κ ′ + λ, a (1)
= 1 4 κ ′′ , a (2) 00
10 = 4κ -

1 2 κ ′′ , a (2)
01 = -4

2 7 χκ, a (2) 20
= 2 7 χ 2 κ + 1 4 κ ′′ + λ. (6)
Since the parameters in this potential depend on the fractional fillings of the valence shells, we arrive at a geometry for each nucleus which changes with neutron and proton numbers and which has been obtained in an unbiased and straightforward way from the observed excitation spectra. This is illustrated in figures 6 and 7, where the potentials are shown for all nuclei included in the fit as well as for some which are predicted. For the sake of a correct interpretation of these potential surfaces, we recall that γ is identical to the corresponding parameter in the Bohr-Mottelson geometric model [START_REF] Bohr | Nuclear Structure. II Nuclear Deformations[END_REF] while β is only proportional to it, the proportionality factor depending on the ratio of the valence over the total nucleon numbers [START_REF] Ginocchio | [END_REF]. The potential energy surface of the nucleus 108 Ru has recently been calculated in variety of ways. Möller et al. [26] showed that deviations from axial symmetry can be important and, in the specific case of 108 Ru, obtained a potential energy surface with triaxial minimum. With the simple parametrization of the IBM-1 Hamiltonian as proposed here which is limited to two-body interactions, no triaxial minimum can be obtained [27], a result confirmed by the surfaces shown in figures 6 and 7. It is also seen, however, that the specific potential for 108 Ru is rather soft in γ. Triaxial minima can be obtained when cubic terms are added to the IBM-1 Hamiltonian [28,29]. In comparison with the results obtained in reference [29] for the nuclei 108,110,112 Ru, we observe that the potential surfaces shown here show less variation with neutron number since they are derived from a global fit to many nuclei while in the former study the fits were carried out nucleus by nucleus. Also shown in figures 6 and 7 are the potential energy surfaces for the predicted neutron-rich nuclei. As can be seen from the figures, their geometry varies from strongly deformed in the neutron-rich Zr isotopes to spherical in 122 Pd.

Conclusions

We have suggested in this paper the use of IBM-1 for global calculations of large regions of the nuclear chart and have illustrated the idea with an application to the A ∼ 100 region. The present work calls for several features to be studied in more detail. The first concerns the technical issue of finding the set of parameters that corresponds to the global minimum of the rms deviation. The minimization algorithm that has been used here is a straightforward linearization procedure of the eigenvalue problem associated with the Hamiltonian (1) which has no trouble in finding a local minimum. We have found no dependence of the converged parameters on various choices of their initial values but it would be of interest to confirm the global character of the minimum using a different algorithm which samples large parameter regions. Secondly, the dependence of the parameters on the fractional fillings f ρ of the valence neutron and proton shells requires further study. We have proposed here a dependence on n ρ /Ω ρ but other choices should be investigated as well, such as a dependence on N ρ /Ω ρ (where N ρ is the boson number) or on Casten's factor P = N ν N π /(N ν +N π ) [12]. Furthermore, a possible dependence on subshells must also be studied. A proper treatment of these effects and their dependence on valence nucleon number must draw inspiration from the microscopic foundation of the IBM. For example, in this study we have taken a constant value of χ, the parameter appearing in the quadrupole operator. This is possibly a reasonable approximation for the restricted set of nuclei considered here but it will certainly be inadequate if large regions of the nuclear chart are fitted simultaneously. This inadequacy might be satisfactorily resolved by a proper estimate of this parameter based on the shell-model interpretation of the IBM. An alternative strategy is to adopt a functional dependence of χ on valence-particle number suggested by microscopy, containing a few parameters that are fitted to the data. Finally, we point out that the type of calculation described here opens up the possibility for a simultaneous and global treatment of nuclear groundstate properties (such as masses and radii) in addition to the excited-state properties discussed in this paper. A possible strategy for merging the calculations of groundand excited-state energies in the framework of the interacting boson model was outlined in reference [30] with preliminary results for even-even nuclei in the major shell with 82 < N < 126 and 50 < Z < 82 but further investigations of this approach are required.

Figure 1 .Figure 2 .

 12 Figure 1. The experimental (symbols) and calculated (lines) energy spectra for the Zr isotopes with 52 ≤ N ≤ 66 (left) and the Mo isotopes with 52 ≤ N ≤ 70 (right): (a) ground-state, (b) quasi-γ and (c) quasi-β bands. Only levels in Zr isotopes with N ≥ 60 are fitted. All experimental levels shown for Mo are included in the fit.

Figure 3 .

 3 Figure 3. The experimental (full symbols) and calculated (open symbols) B(E2; 2 + 1 → 0 + 1 ) values in the Zr, Mo, Ru and Pd isotopes.

Figure 4 .Figure 5 .

 45 Figure 4. The experimental (full symbols) and calculated (open symbols) B(E2; 4 + 1 → +) values in the Zr, Mo, Ru and Pd isotopes.

Table 1 .

 1 Root-mean-square deviations ∆ in the energies and B(E2) values as a function of the quadrupole parameter χ.

	χ	-0.05 -0.1 -0.2 -0.3 -0.4 -0.6 -0.8 -1.0
	∆(E) (keV)	126	122	120	122	125	129	131	133
	∆ 1 (E2) (e 2 b 2 )	0.26 0.13 0.10 0.11 0.14 0.17 0.15 0.16
	∆ 2 (E2)	3.44 2.29 2.02 2.12 2.34 2.54 2.20 2.21

Table 2 .

 2 Parameters of the Hamiltonian (1) in units of keV.

	ǫ	κ 00	κ 10	κ 01	κ ′ 00	κ ′ 10	κ ′ 01	κ ′′	λ 00	λ 10	λ 01
	695 -35.8 -72.4 47.9 18.3 12.8 -15.8 1.4 -115.9 -166.1 161.2

Table 3 .

 3 Root-mean-square deviations ∆(E) when Zr isotopes with neutron number N ≥ N 0 are included in the fit.

	N 0	60	58	56	54	52
	∆(E) (keV) 120 158 214 215 217

Table 4 .

 4 Experimental and calculated B(E2; J π i → J π f ) values in units of 10 2 e 2 fm 4 in 100 Ru, 104 Pd and 108 Pd.

		100 Ru		104 Pd		108 Pd
	J π i → J π f	Expt IBM-1	Expt IBM-1	Expt IBM-1
	2 + 1 → 0 + 1 4 + 1 1 → 2 + 6 + 1 1 → 4 + 8 + 1 1 → 6 + 0 + 1 2 → 2 + 2 + 2 → 0 + 1 2 + 1 2 → 2 + 4 + 2 → 2 + 1 4 + 2 2 → 2 + 4 + 2 → 4 + 1	9.8 (0.1) 14 (1.1) < 47 -9.7 (1.4) 0.52( +0.11 -0.14 ) 8.5 (0.11) 0.52( +0.22 -0.06 ) -7.4 (4.7)	7.1 11 13 12 8.6 0.004 11 0.003 6.7 6.0	11 (0.6) 14 (2) --3.8 (0.4) 0.38 (0.03) 6.3 (4.9) 0.17 (0.17) 7.3 (7.3) 2.9 (2.9)	7.1 11 13 12 8.5 0.004 11 0.003 6.7 6.0	15 (0.5) 23 (2.8) 33 (3.4) 45 (6.1) 16 (1.5) 0.25 (0.02) 22 (1.5) 0.04 (0.04) 17 (1.8) 9.2 (1.8)	14 21 24 25 10 0.10 19 0.04 12 10
	22, 23]. The classical limit of the IBM-1 Hamiltonian (1) is

Acknowledgements

This work was supported by the Scientific and Technological Research Council of Turkey (TUBITAK) under project nr 107T557, and by the Agence Nationale de Recherche, France, under contract nr ANR-07-BLAN-0256-03.